HDU 3289 Cat VS Dog （二分匹配 求 最大独立集）

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<iostream>
 5 #include<cstdlib>
 6 #include<string>
 7 #include<cmath>
 8 #include<vector>
 9 #define clc(a,b) memset(a,b,sizeof(a))
10 using namespace std;
11 const double eps=1e-8;
12 const double pi=acos(-1);
13 const int maxn=1505;
14 int linker[maxn];
15 bool used[maxn];
16 int n,m,p;
17 char cat[maxn][10];
18 char dog[maxn][10];
19 vector<int>vec[maxn];
20 int uN;
21 
22 bool dfs(int u)
23 {
24     for(int i=0;i<vec[u].size();i++)
25     {
26         if(!used[vec[u][i]])
27         {
28             used[vec[u][i]]=true;
29             if(linker[vec[u][i]]==-1||dfs(linker[vec[u][i]]))
30             {
31                 linker[vec[u][i]]=u;
32                 return true;
33             }
34         }
35     }
36     return false;
37 }
38 
39 int hungary(int n)
40 {
41     //int u;
42     int res=0;
43     clc(linker,-1);
44     for(int u=0;u<n;u++)
45     {
46         clc(used,0);
47         if(dfs(u))
48             res++;
49     }
50     return res;
51 }
52 
53 int main()
54 {
55     while(~scanf("%d%d%d",&n,&m,&p))
56     {
57         clc(vec,0);
58         for(int i=0;i<p;i++)
59         {
60             scanf("%s%s",cat[i],dog[i]);
61         }
62         for(int i=0;i<p;i++)
63         {
64             for(int j=i+1;j<p;j++)
65             {
66                 if(!strcmp(cat[i],dog[j])||!strcmp(dog[i],cat[j]))
67                 {
68                     vec[i].push_back(j);
69                     vec[j].push_back(i);
70                 }
71             }
72         }
73         uN=hungary(p)/2;
74         //cout<<uN<<endl;
75         printf("%d
",p-uN);
76     }
77     return 0;
78 }