题目 http://acm.hdu.edu.cn/showproblem.php?pid=1068
题意求出男孩和女孩没有暧昧关系的人数哦 刚开始错了数组开的太大了 超内存了。。。
这个是先求出最大匹配数 再用总的人数减掉就是答案了
思路:
最大独立集点数 = N - 最大匹配数
具体代码是
#include<iostream> #include<cstring> #include<cstdio> using namespace std; #define max 1000 bool map[max][max]; bool mark[max]; int n; int cx[max],cy[max],link[max]; int findpath(int u) //找增广路径 { int i,j; for(i=0;i<n;i++) { if(map[u][i]&&!mark[i]) { mark[i]=1; if(!link[i]||findpath(link[i])) { link[i]=u; return 1; } } } return 0; } void maxmatch() //最大匹配 { int i,j,res=0; for(i=0;i<n;i++) { memset(mark,false,sizeof(mark)); res+=findpath(i); } cout<<n-res/2<<endl; //最大独立点 注意要除以2哦 因为我吧这个当做一个集合了。 } int main() { int i,j,k,num; char a,b; while(cin>>n) { memset(map,false,sizeof(map)); memset(link,0,sizeof(link)); for(k=0;k<n;k++) { cin>>i>>a>>b>>num>>b; for(i=0;i<num;i++) { cin>>j; map[k][j]=1; } } maxmatch(); } return 0; }