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

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精品国产高清久久久久蜜芽 | 国产精品探花一区在线观看 | 99久久免费视频在线观看 | 久草在线最新视频 | 色综合久久六月婷婷中文字幕 | 人人看97 | 91正在播放极品白嫩在线观看 | 婷婷色网站 | 久久婷婷国产麻豆91天堂 | 日日摸日日碰夜夜爽久久 | 成人国产精品 | 999精品免费视频观看 | 国产激情视频一区二区三区 | 中国女人精69xxxxxx视频 | 久青草视频97国内免费影视 | 欧美xxx午夜免费视频 | 久久影片 | 久久久青青 | 久久99亚洲精品久久 | 国产九九免费视频网站 | 在线日本中文字幕 | 成年女人免费毛片视频永久 | 综合久久久久久中文字幕 | 国产精品久久久久久久久久久威 | 久视频在线 | 免费a级毛片大学生免费观看 | 国产成人一区二区三区 | 色妞ww精品视频7777 | 色婷五月 | 国产色视频一区二区三区 | 香蕉视频国产在线观看 | 四色成人 | 欧美国产激情二区三区 | 91热精品 | 国产一级二级三级 | 亚洲精品美女一区二区三区乱码 | 国产在线欧美精品中文一区 | 很黄很色的免费视频 |