最大独立点集=最小覆盖路径= 顶点数 - 最大二分匹配/2 (!)
题意是求最少有几组出去,能匹配则匹配,不能的就是自己单独一组。
这个是匈牙利算法,属于模版题。
#include <cstdio> #include <cstring> //using namespace std; #define MAX_M 1001 bool map[MAX_M][MAX_M],use[MAX_M]; int t,m,path[MAX_M]; bool Match(int v){ for(int i=0;i<m;i++){ if(!use[i] && map[v][i]){ use[i]=true; if(path[i]<0 ||Match(path[i])){ path[i]=v; return true; } } } return false; } int Maxmatch(){ int num=0; memset(path,-1,sizeof(path)); for(int i=0;i<m;i++){ memset(use,false,sizeof(use)); if(Match(i)) num++; } return num; } int main(){ while(scanf("%d",&t)!=EOF){ m=t; memset(map,false,sizeof(map)); while(t--){ int v,n; scanf("%d: (%d)",&v,&n); while(n--){ int u; scanf("%d",&u); map[v][u]=true; } } printf("%d\n",m-Maxmatch()/2); } return 0; }