hdu1150

[ Reprinted ]最小点覆盖=最大二分匹配数

url: http://zhidao.baidu.com/link?url=ZMzk27V8P99KQN63DpVsE2fd1YBIk7Jg83E4iHAW-OI1eU9E9FlT9knnZNqSAJk65mv894xLjd3qYSyLSvlwcK

比如最大匹配是M。为了求最少的点让每条边都至少和期中一个点关联。
M个点是足够的。就是说他们覆盖最大匹配的那M条边后，假设有某边e没被覆盖，那么把e加入后会得到一个更大的匹配，出现矛盾。
M个点是必需的。匹配的M条边，由于他们两两无公共点，就是说至少有M个点才能把他们覆盖。

warnning:::: At the beginning they are both work at mode_0.

 1 #include <stdio.h>
 2 #include <string.h>
 3 
 4 
 5 int already[110];
 6 int in[110];
 7 int gr[110][110];
 8 int n,m;
 9 
10 int find(int a){
11     int i;
12     for(i=0;i<m;++i){
13         if(gr[a][i]&&!in[i]){
14             in[i]=1;
15             if(already[i]==-1||find(already[i])){
16                 already[i]=a;
17                 return 1;
18             }
19         }
20     }
21     return 0;
22 }
23 int main(){
24     int c;
25     int i,j;
26     int t1,t2,t3;
27     int res;
28     while(~scanf("%d",&n)&&n){
29         scanf("%d%d",&m,&c);
30         res=0;
31         memset(gr,0,sizeof(gr));
32         while(c--){
33             scanf("%d%d%d",&t1,&t2,&t3);
34             /* !!!!!!!! */
35             if(t2==0||t3==0) continue;
36             gr[t2][t3]=1;
37         }
38         for(i=0;i<110;++i)    already[i]=-1;
39 
40         for(i=0;i<n;++i){
41             memset(in,0,sizeof(in));
42             if(find(i))
43                 res++;
44         }
45         printf("%d
",res);
46     }
47     return 0;
48 }