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

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條評論
主站蜘蛛池模板: 在线视频亚洲 | 国产成人一区二区三区 | 国产日韩一区二区三区在线观看 | 亚欧aⅴ天堂在线 | 国产毛片毛片精品天天看 | 国产成人精品一区二区不卡 | 久久亚洲国产欧洲精品一 | 国产成人一区二区三区视频免费 | 奇米888888| 欧美丰满大乳大屁股毛片 | 日韩一区二区在线视频 | 久久精品一区二区三区不卡 | 国产成人性毛片aaww | 奇米4色| 一级在线视频 | 精品久久一区二区三区 | 国产剧情一区二区三区 | 激情亚洲 | 亚洲码和乱人伦中文一区 | 国产中文久久精品 | 看欧美毛片一级毛片 | 一级特黄aaa大片免色 | 亚洲操 | 色福利视频 | 久久综合九色综合欧美狠狠 | 国产伦码精品一区二区三区 | 欧美色图偷窥自拍 | 一级有奶水毛片免费看 | 日韩欧美亚洲精品 | 天天操操操操 | 伊人伊网 | 久久免费高清视频 | 久久不射视频 | 一级日本高清视频免费观看 | 欧美一区二区三区东南亚 | 亚洲国产精品网站久久 | 国产成人免费网站在线观看 | 久久精品视频免费播放 | 日韩精品一区二区三区免费视频 | 亚洲国产香蕉视频欧美 | 国产乱仑|