http://acm.hdu.edu.cn/showproblem.php?pid=3829
最大独立集： 在Ｎ个点的图G中选出m个点，使这m个点两两之间没有边，求m最大值。
该题满足二分图条件，可化为二分图最大匹配问题，最大独立集=顶点数-最大匹配数。
#include <iostream>
#include <string>
using namespace std;
struct C
{
string like,dislike;
}catchild[501],dogchild[501];
int m,n,k;
int link[501];
bool g[501][501];
bool visit[501];
bool find(int i)
{
int j;
for(j=1;j<=n;j++)
{
if(g[i][j] && visit[j]==false)
{
visit[j]=true;
if(link[j]==0 || find(link[j]))
{
link[j]=i;
return true;
}
}
}
return false;
}
int main()
{
int i,j,res;
string like,dislike;
while(cin>>i>>j>>k)
{
m=n=res=0;
while(k--)
{
cin>>like>>dislike;
if(like[0]=='C')
{
m++;
catchild[m].like=like;
catchild[m].dislike=dislike;
}
else
{
n++;
dogchild[n].like=like;
dogchild[n].dislike=dislike;
}
}
memset(g,0,sizeof(g));
memset(link,0,sizeof(link));
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
if(catchild[i].like == dogchild[j].dislike || catchild[i].dislike == dogchild[j].like)
g[i][j]=true;
for(i=1;i<=m;i++)
{
memset(visit,0,sizeof(visit));
if(find(i))
res++;
}
cout<<m+n-res<<endl;
}
return 0;
}
posted on 2011-09-13 00:47
大大木马 阅读(344)
评论(0) 编辑 收藏 引用