最小覆蓋。。。本題是雙向圖
典型的最小頂點覆蓋！最小頂點覆蓋 == 最大匹配（雙向圖）/2；
此題有個小細節，數據較大，要用鄰接表，不然會超時！
[csharp]
#include"stdio.h"
#include"string.h"
int map[1501][1501],mark[1501];
int link[1501],v[1501];
int n;
int dfs(int k)
{
int i;
for(i=0;i<n;i++)
{
if(map[k][i]==1&&!v[i])
{
v[i]=1;
if(link[i]==0||dfs(link[i]))
{
link[i]=k;
return 1;
}
}
}
return 0;
}
int main()
{
int i,j,t,a,b,count;
while(scanf("%d",&n)!=-1)
{
memset(map,0,sizeof(map));
for(i=0;i<n;i++)
{
scanf("%d:(%d)",&a,&t);
for(j=0;j<t;j++)
{
scanf("%d",&b);
map[a][b]=1;
map[b][a]=1;
}
}
count=0;
memset(link,0,sizeof(link));
for(i=0;i<n;i++)
{
memset(v,0,sizeof(v));
if(dfs(i))
count++;
}
printf("%d\n",count/2);
}
return 0;
}
作者;yyf573462811
