infinity

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  36 随笔 :: 0 文章 :: 25 评论 :: 0 Trackbacks
问题可以转换为最小点集覆盖问题,既求二分图的最大匹配。

Source Code


  • Source Code

 1 #include <stdio.h>
 2 #include<stdlib.h>
 3 #include<string.h>
 4 int N=0;
 5 int K=0;
 6 int R=0;
 7 int C=0;
 8 int asteroids[501][501];
 9 int mark[501],match[501];
10 int FindPath(int x){
11     int tmp=0;
12     for (int i=1;i<=N ;i++ )
13     {
14         if(asteroids[x][i] && !mark[i]){
15             mark[i]=1;
16             if(match[i]==0 || FindPath(match[i])){
17                 match[i]=x;
18                 return 1;
19             }
20         }
21         
22     }
23     return 0;
24 }
25 int main()
26 {
27     scanf("%d %d",&N,&K);
28     memset(asteroids,0,sizeof(asteroids));
29     for (int i=1;i<=K ;i++ )
30     {    
31         int row,column;
32         scanf("%d %d",&row,&column);
33         asteroids[row][column]=1;
34     }
35     int count=0;
36     memset(match,0,sizeof(match));
37     for (int i=1;i<=N ;i++ )
38     {
39         memset(mark,0,sizeof(mark));
40         if (FindPath(i)) count++;
41     }
42     printf("%d\n",count);
43 }
posted on 2012-03-20 01:38 infinity 阅读(1154) 评论(0)  编辑 收藏 引用 所属分类: acm

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理