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

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條評論
主站蜘蛛池模板: 亚洲欧美婷婷 | 成人性色生活片免费看爆迷你毛片 | 97在线观看免费版 | 中文一区二区视频 | 国产乱叫456在线 | 日韩一级一片 | 怡红院成人永久免费看 | 特黄一级大片 | 久久免费精彩视频 | 欧美一区二区三区在线播放 | 秘密影院久久综合亚洲综合 | 国产综合亚洲欧美日韩一区二区 | 国产欧美一区二区精品仙草咪 | 一级毛片无毒不卡直接观看 | 麻豆精品国产免费观看 | 国产一区二区三区久久精品小说 | 射婷婷| 97精品福利视频在线 | 欧美日韩一区二区不卡三区 | 欧美e片成 人 在线播放乱妇 | 亚洲综合色网 | 50-60岁老妇女一级毛片 | 日本老妇成熟 | 久久精品亚洲日本波多野结衣 | 欧美日韩专区 | 大狠狠大臿蕉香蕉大视频 | 日本特黄在线观看免费 | 中文字幕亚洲色图 | 亚洲视频一区二区三区四区 | 国产91精品久久久久久久 | 国产成人综合网 | 国产一级一国产一级毛片 | 成人精品久久 | 午夜精品久久久久久毛片 | 久久在草 | 亚洲国产成人成上人色 | 天天干夜夜欢 | 久久综合狠狠综合久久 | 99爱视频免费高清在线观看 | 狠狠色噜噜狠狠狠8888米奇 | 天天天天躁天天天天碰 |