HDU 1068
求一个集合最多几个人，其之间任意两人没有暧昧关系。
二分图匹配
最大独立集 = 总点数 - 最大匹配数
匈牙利算法
因为每个同学都在二分图的两侧
当 A与B匹配时，B与A也匹配
所以 所求的最大匹配数要除以2
1 #include <iostream> 2 #include <cstdio> 3 #include <vector> 4 #include <cstring> 5 using namespace std; 6 const int maxn=1000; 7 int n,a,m,b; 8 vector<int>map[maxn]; 9 int link[maxn]; 10 int vis[maxn]; 11 bool dfs(int t) 12 { 13 int size=map[t].size(); 14 for(int i=0;i<size;i++) 15 { 16 int x=map[t][i]; 17 if(!vis[x]) 18 { 19 vis[x]=1; 20 if(link[x]==-1||dfs(link[x])) 21 { 22 link[x]=t; 23 return 1; 24 } 25 } 26 } 27 return 0; 28 } 29 int main() 30 { 31 while(~scanf("%d",&n)) 32 { 33 for(int i=0;i<n;i++) 34 { 35 scanf("%d: (%d)",&a,&m); 36 map[i].clear(); 37 for(int j=0;j<m;j++) 38 { 39 scanf("%d",&b); 40 map[a].push_back(b); 41 } 42 } 43 memset(link,-1,sizeof(link)); 44 int ans=0; 45 for(int i=0;i<n;i++) 46 { 47 memset(vis,0,sizeof(vis)); 48 if(dfs(i)) 49 ans++; 50 } 51 printf("%d ",n-ans/2); 52 } 53 }