poj 1719

Shooting Contest

题意：r行c列的矩阵上，每列有两个白色点，用c发子弹打到矩阵上的点，能否使每列有且只有一个白点被击中而每行起码有一个白点被击中（这个题意当初没理解好，纠结一个下午都不知道为什么WA）？若能，则求其中一个白点组合；不能则输出“NO”。

分析：受人指教，这个图可以把行作为一个集合，列作为一个集合，若第i行第j列是白色的，则有边(i,j)，可以保证这样的图是二分图。只要在这个图里求出最大匹配（在匹配的情况下，每列都只会选到一行），匹配数等于r则能满足条件（有匹配的列都直接输出匹配点，注意c可能大于r，因此没匹配到的列里每列随便拿出一个白点就能得出解）。

View Code

 1 #include<cstdio>
 2 #include<vector>
 3 using namespace std;
 4 vector<int> vex[5000];
 5 int r,c,max_match,mat[5000];
 6 bool visited[5000];
 7 int path(int u)
 8 {
 9     int i,v;
10     for(i=0;i<vex[u].size();i++)
11     {
12         v=vex[u][i];
13         if(!visited[v])
14         {
15             visited[v]=true;
16             if(mat[v]==-1 || path(mat[v]))
17             {
18                 mat[v]=u;
19                 mat[u]=v;
20                 return 1;
21             }
22         }
23     }
24     return 0;
25 }
26 int Hungary()
27 {
28     int ans=0,i,j;
29     for(i=1;i<=c+r;i++)
30         mat[i]=-1;
31     for(i=1;i<=c;i++)
32     {
33         for(j=1;j<=c+r;j++)
34             visited[j]=false;
35         ans+=path(i);
36     }
37     return ans;
38 }
39 int main()
40 {
41     int t,i,a,b;
42     scanf("%d",&t);
43     while(t--)
44     {
45         scanf("%d%d",&r,&c);
46         for(i=1;i<=c;i++)
47         {
48             scanf("%d%d",&a,&b);
49             vex[i].push_back(a+c);
50             vex[i].push_back(b+c);
51             vex[a+c].push_back(i);
52             vex[b+c].push_back(i);
53         }
54         max_match=Hungary();
55         if(max_match==r)
56         {
57             printf("%d",mat[1]-c);
58             for(i=2;i<=c;i++)
59             {
60                 if(mat[i]!=-1)
61                     printf(" %d",mat[i]-c);
62                 else
63                     printf(" %d",vex[i][1]-c);
64             }
65             printf("\n");
66         }
67         else
68             printf("NO\n");
69         for(i=1;i<=c+r;i++)
70             vex[i].clear();
71     }
72     return 0;
73 }