二分图匹配之最小点覆盖 HDU1498&&POJ3041

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 
 5 using namespace std;
 6 
 7 struct edge
 8 {
 9     int fro,to,next;
10 }e[100010];
11 int map[110][110];
12 bool vis[1100];
13 int head[1100];
14 int link[1100];
15 int ans[500];
16 
17 int find(int x)
18 {
19     for(int i=head[x];i!=-1;i=e[i].next)
20     {
21         if(!vis[e[i].to])
22         {
23             int q=link[e[i].to];
24             link[e[i].to]=e[i].fro;
25             vis[e[i].to]=true;
26             if(q==-1||find(q))
27                 return 1;
28             link[e[i].to]=q;
29         }
30     }
31     return 0;
32 }
33 
34 int main()
35 {
36     int n,k;
37     while(scanf("%d%d",&n,&k)!=EOF)
38     {
39         if(n==0&&k==0)
40             break;
41         for(int i=1;i<=n;i++)
42         {
43             for(int j=1;j<=n;j++)
44             {
45                 scanf("%d",&map[i][j]);
46             }
47         }
48         int tol=0;
49         for(int i=1;i<=50;i++)
50         {
51             int tmp=0;
52             int num=1;
53             int flag=0;
54             memset(head,-1,sizeof(head));
55             memset(link,-1,sizeof(link));
56             for(int j=1;j<=n;j++)
57             {
58                 for(int t=1;t<=n;t++)
59                 {
60                     if(map[j][t]==i)
61                     {
62                         flag=1;
63                         e[num].fro=j;
64                         e[num].to=t;
65                         e[num].next=head[j];
66                         head[j]=num;
67                         num++;
68                     }
69                 }
70             }
71             if(!flag)
72                 continue;
73             for(int j=1;j<=n;j++)
74             {
75                 memset(vis,false,sizeof(vis));
76                 tmp+=find(j);
77             }
78             if(tmp>k)
79             {
80                 ans[tol]=i;
81                 tol++;
82             }
83         }
84         if(tol==0)
85             cout<<-1<<endl;
86         else
87         {
88             cout<<ans[0];
89             for(int i=1;i<tol;i++)
90             {
91                 cout<<" "<<ans[i];
92             }
93             cout<<endl;
94         }
95     }
96     return 0;
97 }

View Code

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 
 5 using namespace std;
 6 
 7 struct edge
 8 {
 9     int fro,to,next;
10 }e[10010];
11 int head[510];
12 bool vis[510];
13 int link[510];
14 
15 int find(int x)
16 {
17     for(int i=head[x];i!=-1;i=e[i].next)
18     {
19         if(!vis[e[i].to])
20         {
21             int q=link[e[i].to];
22             link[e[i].to]=e[i].fro;
23             vis[e[i].to]=true;
24             if(q==-1||find(q))
25                 return 1;
26             link[e[i].to]=q;
27         }
28     }
29     return 0;
30 }
31 
32 int main()
33 {
34     int n,k;
35     while(scanf("%d%d",&n,&k)!=EOF)
36     {
37         int ans=0;
38         memset(head,-1,sizeof(head));
39         for(int i=1;i<=k;i++)
40         {
41             scanf("%d%d",&e[i].fro,&e[i].to);
42             e[i].next=head[e[i].fro];
43             head[e[i].fro]=i;
44         }
45         memset(link,-1,sizeof(link));
46         for(int i=1;i<=n;i++)
47         {
48             memset(vis,false,sizeof(vis));
49             ans+=find(i);
50         }
51         cout<<ans<<endl;
52     }
53     return 0;
54 }

View Code

最小点覆盖，用最少的点，使得每条边至少有一个端点在这些点中

最小点覆盖数=最大匹配数