亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

The Accomodation of Students

系統 1704 0

The Accomodation of Students

Time Limit: 5000/1000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1462????Accepted Submission(s): 716

?

Problem Description
There are a group of students. Some of them may know each other, while others don't. For example, A and B know each other, B and C know each other. But this may not imply that A and C know each other.

?

Now you are given all pairs of students who know each other. Your task is to divide the students into two groups so that any two students in the same group don't know each other.If this goal can be achieved, then arrange them into double rooms. Remember, only paris appearing in the previous given set can live in the same room, which means only known students can live in the same room.

?

Calculate the maximum number of pairs that can be arranged into these double rooms.
?

?

Input
For each data set:
The first line gives two integers, n and m(1<n<=200), indicating there are n students and m pairs of students who know each other. The next m lines give such pairs.

?

Proceed to the end of file.

?

?

?

Output
If these students cannot be divided into two groups, print "No". Otherwise, print the maximum number of pairs that can be arranged in those rooms.
?

?

Sample Input
4 4
1 2
1 3
1 4
2 3
6 5
1 2
1 3
1 4
2 5
3 6
?

?

Sample Output
No
3
?

?

Source
2008 Asia Harbin Regional Contest Online
?

?

Recommend
gaojie

又是一遍AC,雖然還是模板題,但是一個小時4個1a讓我今天下午很愉快啊有木有.

      
        #include<stdio.h>
        
           #include
        
        <
        
          string
        
        .h>


        
          int
        
        
           N,M; 
        
        
          int
        
         color[
        
          300
        
        ],match[
        
          300
        
        
          ]; 
        
        
          bool
        
         visit[
        
          300
        
        ],G[
        
          300
        
        ][
        
          300
        
        
          ],flag; 
        
        
          void
        
         draw(
        
          int
        
         k,
        
          int
        
        
           cc) { 
        
        
          if
        
         (color[k]!=-
        
          1
        
         && color[k]!=
        
          cc) { flag
        
        =
        
          false
        
        
          ; 
        
        
          return
        
        
          ; } 
        
        
          if
        
         (color[k]==cc) 
        
          return
        
        
          ; color[k]
        
        =
        
          cc; 
        
        
          int
        
         c=
        
          1
        
        -
        
          cc; 
        
        
          for
        
         (
        
          int
        
         i=
        
          1
        
        ;i<=N;i++
        
          ) 
        
        
          if
        
         (G[k][i] &&
        
           flag) draw(i,c); } 
        
        
          bool
        
         DFS(
        
          int
        
        
           k) { 
        
        
          int
        
        
           t; 
        
        
          for
        
         (
        
          int
        
         i=
        
          1
        
        ;i<=N;i++
        
          ) 
        
        
          if
        
         (G[k][i] && !
        
          visit[i]) { visit[i]
        
        =
        
          1
        
        
          ; t
        
        =
        
          match[i]; match[i]
        
        =
        
          k; 
        
        
          if
        
         (t==-
        
          1
        
         || DFS(t)) 
        
          return
        
        
          true
        
        
          ; match[i]
        
        =
        
          t; } 
        
        
          return
        
        
          false
        
        
          ; } 
        
        
          int
        
        
           Max_match() { 
        
        
          int
        
         ans=
        
          0
        
        
          ; memset(match,
        
        -
        
          1
        
        ,
        
          sizeof
        
        
          (match)); 
        
        
          for
        
         (
        
          int
        
         i=
        
          1
        
        ;i<=N;i++
        
          ) { memset(visit,
        
        
          0
        
        ,
        
          sizeof
        
        
          (visit)); 
        
        
          if
        
         (DFS(i)) ans++
        
          ; } 
        
        
          return
        
        
           ans; } 
        
        
          int
        
        
           main() { 
        
        
          while
        
         (scanf(
        
          "
        
        
          %d%d
        
        
          "
        
        ,&N,&M)!=
        
          EOF) { memset(G,
        
        
          0
        
        ,
        
          sizeof
        
        
          (G)); 
        
        
          for
        
         (
        
          int
        
         i=
        
          1
        
        ;i<=M;i++
        
          ) { 
        
        
          int
        
        
           u,v; scanf(
        
        
          "
        
        
          %d%d
        
        
          "
        
        ,&u,&
        
          v); G[u][v]
        
        =
        
          1
        
        
          ; G[v][u]
        
        =
        
          1
        
        
          ; } memset(color,
        
        -
        
          1
        
        ,
        
          sizeof
        
        
          (color)); flag
        
        =
        
          true
        
        
          ; 
        
        
          for
        
         (
        
          int
        
         i=
        
          1
        
        ;i<=N;i++
        
          ) 
        
        
          if
        
         (flag && color[i]==-
        
          1
        
        ) draw(i,
        
          0
        
        
          ); 
        
        
          if
        
         (!flag) printf(
        
          "
        
        
          No\n
        
        
          "
        
        
          ); 
        
        
          else
        
         printf(
        
          "
        
        
          %d\n
        
        
          "
        
        ,Max_match()/
        
          2
        
        
          ); } 
        
        
          return
        
        
          0
        
        
          ; }
        
      
    

?

The Accomodation of Students


更多文章、技術交流、商務合作、聯系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯系: 360901061

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!!!

發表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 国内精品免费一区二区观看 | 免费观看一级成人毛片软件 | 国产五月天在线 | 成人在线不卡 | 久久免费资源 | 亚洲一成人毛片 | 欧美亚洲国产成人高清在线 | 成人区精品一区二区不卡亚洲 | 欧美一级网 | 色婷婷777 | 免费视频不卡一区二区三区 | 亚洲欧美日韩中文综合在线不卡 | 色花堂国产精品第二页 | 涩涩一区| 99热这里只有成人精品国产 | 天天躁日日躁狠狠躁黑人躁 | 国产成人国产在线观看入口 | 国产精品亚洲片在线观看麻豆 | 国产国产精品人在线观看 | 五月网婷婷 | 久青草资源福利视频 | 四虎影视精品永久免费 | 欧美三级做爰视频 | 91在线播放免费不卡无毒 | 国产91在线看| 免费一级成人免费观看 | 99久久精品免费看国产交换 | 狠狠色噜狠狠狠狠色综合久 | 天天曰天天干 | 欧美成人天天综合在线视色 | 中文字幕视频免费在线观看 | 大胆国模一区二区三区伊人 | 久久综合综合久久97色 | 欧美毛片基地 | 四虎在线观看免费视频 | 亚洲欧美精品中文字幕 | 国产成人精品视频免费 | 精品国产欧美一区二区三区成人 | 婷婷激情五月综合 | 国产成人在线播放视频 | 久久久亚洲欧洲国产 |