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

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條評論
主站蜘蛛池模板: 国产成版人视频网站免费下 | 亚洲国内自拍愉拍20页 | 国产特级毛片aaaaaaa高清 | 久久免费看视频 | 天天色天天操天天 | 香蕉精品高清在线观看视频 | 中文字幕在线播放 | 玖玖精品视频在线 | 四虎永久精品免费网址大全 | 奇米第九色 | 九九在线精品视频xxx | 91视频香蕉视频 | 日本3p视频在线看高清 | 牛牛影院成人免费网页 | 乱子伦xxx欧美 | 国产一区二区三区不卡免费观看 | 国产成人高清在线观看播放 | 99热久久久久久久免费观看 | 26uuu欧美| 九九视频免费在线观看 | 在线观看中文字幕一区 | 五月婷婷色网 | 狠狠色噜噜狠狠狠狠米奇777 | 91一区二区在线观看精品 | 国产精品公开免费视频 | 性久久久久久久久久 | 草草影院国产第一页 | 99成人精品 | 国产69精品久久久久99不卡 | 99综合在线| 久久精品中文字幕不卡一二区 | 欧美成人aa大片拍拍拍 | 水蜜桃网站| 99精品影视 | 97在线免费观看视频 | 极品精品国产超清自在线观看 | 久久国产精品国产精品 | 国产精品中文字幕在线 | 久久国产加勒比精品无码 | 天天夜夜人人 | www.欧美激情 |