题意：婚配问题，但是题目并不要求输出最大匹配值，而是让我们输出，一个王子可以与哪些王妃婚配而不影响最大匹配值。
解决办法：先求一次最大匹配，如果有两个已经匹配的王妃，喜欢她们两个的有两个或者以上相同的王子，那她们两个是可以交换的，对于前面的王子来说，他与这两个王妃中的任何一个匹配都不会影响最大匹配值，因为总有人把位置补上。那什么样的王妃才是可以交换的王妃呢？我们在这个王子已经匹配的王妃match[i]与他喜欢的王妃v连一条有向边，那样处在一个强联通分量的两个王妃就是可以相互交换的。
下面处理没有匹配的王妃的情况，假设最大匹配值为res，那我们在左边加上m-res个虚拟点，右边加上n-res个虚拟点，左边的虚拟点喜欢所有的王妃，右边的虚拟点被所有的王子喜欢，再求一次最大匹配，然后把边连上。这种方法很巧妙，因为一个没有匹配的王妃，所有的王子都可以跟她匹配而不影响最大值，把她加到强联通分量中的方法就是加这种虚拟点。
注意：我们在联通分量里建的边还是挺多的，我用的maxn*2就WA了，后来干脆改成maxn*maxn，就AC了。
#include<iostream> #include<cstdio> #include<vector> #include<stack> #include<cstring> using namespace std; #define maxn 2020 int map1[maxn][maxn]; int link[maxn],vis[maxn]; struct Edge { int to,nxt; } edge[maxn*maxn]; int head[maxn],low[maxn],dfn[maxn],id[maxn]; int all,tot,scc; bool hungry(int u,int m) { for(int i = 1; i <= m; i++) { if(map1[u][i] && !vis[i]) { vis[i] = 1; if(link[i]==-1 || hungry(link[i],m)) { link[i] = u; return true; } } } return false; } int slove(int n,int m) { memset(link,-1,sizeof(link)); int ans = 0; for(int i = 1; i <= n; i++) { memset(vis,0,sizeof(vis)); if(hungry(i,m)) ans++; } return ans; } void addedge(int u,int v) { edge[tot].to = v; edge[tot].nxt = head[u]; head[u] = tot++; } stack<int> s; void init() { memset(dfn,0,sizeof(dfn)); memset(low,0,sizeof(low)); memset(id,0,sizeof(id)); all = 0; tot = 0; scc = 0; memset(head,-1,sizeof(head)); while(!s.empty()) s.pop(); } void tarjan(int u) { low[u] = dfn[u] = ++all; s.push(u); for(int i = head[u]; i != -1; i = edge[i].nxt) { int v = edge[i].to; if(!dfn[v]) { tarjan(v); low[u] = min(low[u],low[v]); } else if(!id[v]) low[u] = min(low[u],dfn[v]); } if(low[u] == dfn[u]) { scc++; int num; while(!s.empty()) { num = s.top(); s.pop(); id[num] = scc; if(num == u) break; } } } int main() { int t,a,b,k,n,m,ca = 0; scanf("%d",&t); while(t--) { memset(map1,0,sizeof(map1)); scanf("%d%d",&n,&m); for(int i = 1; i <= n; i++) { scanf("%d",&k); while(k--) { scanf("%d",&a); map1[i][a] = 1; } } int match_num; match_num = slove(n,m); int newn,newm; newn = newm = n+m-match_num; for(int i = n+1; i <= newn; i++) { for(int j = 1; j <= newm; j++) { map1[i][j] = 1; } } for(int i = 1; i <= newn; i++) { for(int j = m+1; j <= newm; j++) { map1[i][j] = 1; } } match_num = slove(newn,newm); int match[maxn]; memset(match,-1,sizeof(match)); for(int i = 1; i <= newm; i++) { match[link[i]] = i; } init(); for(int i = 1; i <= newn; i++) { for(int j = 1; j <= newm; j++) { if(map1[i][j] && match[i] != j) { addedge(match[i],j); } } } for(int i = 1; i <= newm; i++) { if(!dfn[i]) { tarjan(i); } } vector<int>ve; printf("Case #%d: ",++ca); for(int i = 1;i <= n;i++) { ve.clear(); //printf("match[%d] = %d ",i,match[i]); for(int j = 1;j <= m;j++) { //printf("id[%d] = %d ",j,id[j]); if(map1[i][j] && id[j] == id[match[i]]) { ve.push_back(j); } } int len = ve.size(); printf("%d",len); for(int j = 0;j < len;j++) { printf(" %d",ve[j]); } printf(" "); } } return 0; }