#include <iostream>
using namespace std;
int n,map[501][501],re[501],ok[501],x1[501],x2[501];
int numx1,numx2;
int find(int u)
{
     for(int i=1;i<=numx2;i++)
     {
      int v=x2[i];
      if(!ok[v]&&map[u][v])
      {
       ok[v]=1;
       if(!re[v]||find(re[v]))
       {
        re[v]=u;
        return true;
       }
      }
     }
     return false;
}
void dfs(int u,int bel)
{
     ok[u]=1;
     for(int i=0;i<n;i++)
     if(map[u][i]&&!ok[i])
     {
      if(bel==1)x2[++numx2]=i;
      else x1[++numx1]=i;
      dfs(i,3-bel);
     }
}
void rs()
{
     numx1=numx2=0;
     memset(ok,0,sizeof(ok));
     for(int i=0;i<n;i++)
     if(!ok[i])
     {
      x1[++numx1]=i;
      dfs(i,1);
     }
}
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
     memset(map,0,sizeof(map));
     for(int i=0;i<n;i++)
     {
      int u,x;
      scanf("%d: (%d)",&u,&x);
      for(int j=0;j<x;j++)
      {
       int v;
       scanf("%d",&v);
       map[u][v]=map[v][u]=1;
      }
     }
     rs();
     int ans=0;
     memset(re,0,sizeof(re));
     for(int i=1;i<=numx1;i++)
     {
      memset(ok,0,sizeof(ok));
      if(find(x1[i]))ans++;
     }
     cout<<n-ans<<endl;
    }
    return 0;
}
代码：

• Re:为什么这题染色分集合会wa呢 而按点数-匹配数/2就可以过了 不解 分集合求最大匹配有错么 (10) Exky 2011-08-16 07:55:59