http://acm.hdu.edu.cn/showproblem.php?pid=1054
这个题如果用邻接矩阵存储树结构的话，会TLE，因此要用邻接表表示，增加了一个数组来存储每项的表长。
#include <iostream>
using namespace std;
const int M=1505;
int g[M][11]; //邻接表表示树结构,用向量数组表示更好，连num数组都可以省去
int num[M]; //存储每项的长度
bool visit[M];
int link[M];
int n,k;
bool find(int i)
{
int j,temp;
for(j=0;j<num[i];j++) //对比之前用邻接矩阵表示，发现效率更高，复杂度O(V*11)
{
temp=g[i][j];
if(!visit[temp])
{
visit[temp]=true;
if(link[temp]==-1 || find(link[temp]))
{
link[temp]=i;
return true;
}
}
}
return false;
}
int main()
{
int i,j,res,t,m;
char a,b;
while(scanf("%d",&n)!=EOF)
{
memset(g,0,sizeof(g));
memset(num,0,sizeof(num));
memset(link,-1,sizeof(link));
res=0;
for(t=0;t<n;t++)
{
cin>>i>>a;
cin>>a>>m>>b;
while(m--)
{
cin>>j;
g[i][num[i]++]=j;
g[j][num[j]++]=i;
}
}
if(n==1) //因为该题说明是树，所以是连通的，当n为1时，一个点当做一对匹配
{
cout<<1<<endl;
continue;
}
for(i=0;i<n;i++)
{
memset(visit,0,sizeof(visit));
if(find(i))
res++;
}
cout<<res/2<<endl;
}
return 0;
}
posted on 2011-09-13 20:35
大大木马 阅读(229)
评论(0) 编辑 收藏 引用