题意：国王有n个儿子，现在有n个美女，每个儿子都有若干个梦中情人，现在已经有一个方案使每个王子都能与自己的梦中情人之一结婚。现在要求的是，对于每个儿子能选择的配偶是谁（最终每个儿子都能结成婚）？
分析：这个题的建图方法很特别。为了充分利用条件，即最后给出的那个完美匹配，将每个王子向他的梦中情人作一条有向边，完美匹配方案中，美女向匹配的王子作一条有向边。求出图中的强连通分量，与王子在同一个强连通分量且该王子喜欢的美女就是答案。
正确性：王子集合{x1,x2,......,xn}，美女集合{y1,y2,......,yn}，假设在原完美匹配方案中每个匹配都是(xi,yi)，显然yi是xi的一个选项。假如xi选了yj(j!=i)，则原先与yj匹配的王子xj要找另一个女人，yi要与另一个王子匹配，假如xj喜欢yi，那么yj就可以是xi的另一个选项了，假如xj不喜欢yi，那么就继续下去拆散现有的完美匹配，直到有个王子喜欢yi。所以这样就相当于要找一条由xi出发到yi的通路（等价于由xi出发回到xi的回路），只要这样的回路存在，王子就可以与回路中任意一个他喜欢的美女匹配了。这样也就相当于求包含xi的强连通分量。（注意：求出强连通分量之后，只有王子喜欢的美女才能匹配）。
View Code
1 #include<cstdio> 2 #include<vector> 3 #include<stack> 4 #include<algorithm> 5 using namespace std; 6 stack<int> s; 7 vector<int> arc[5005],group[5005]; 8 bool visited[5005],instack[5005],matrix[2001][2001]; 9 int counter,low[5005],num[5005],sn,set[5005],n; 10 void tarjan(int u) 11 { 12 int i,v; 13 num[u]=low[u]=++counter; 14 visited[u]=true; 15 instack[u]=true; 16 s.push(u); 17 for(i=0;i<arc[u].size();i++) 18 { 19 v=arc[u][i]; 20 if(!visited[v]) 21 { 22 tarjan(v); 23 low[u]=min(low[v],low[u]); 24 } 25 else if(instack[v]) 26 low[u]=min(low[u],num[v]); 27 } 28 if(num[u]==low[u]) 29 { 30 do 31 { 32 v=s.top(); 33 if(v>n)//v is a girl 34 group[sn].push_back(v); 35 else 36 set[v]=sn; 37 instack[v]=false; 38 s.pop(); 39 }while(u!=v); 40 sort(group[sn].begin(),group[sn].end()); 41 sn++; 42 } 43 } 44 int main() 45 { 46 while(~scanf("%d",&n)) 47 { 48 for(int i=1;i<=n;i++) 49 { 50 for(int j=1;j<=n;j++) 51 matrix[i][j]=false; 52 } 53 for(int i=1;i<=n;i++) 54 { 55 int m; 56 scanf("%d",&m); 57 for(int j=0;j<m;j++) 58 { 59 int v; 60 scanf("%d",&v); 61 matrix[i][v]=true; 62 arc[i].push_back(v+n); 63 } 64 } 65 for(int i=1;i<=n;i++) 66 { 67 int u; 68 scanf("%d",&u); 69 arc[u+n].push_back(i); 70 } 71 for(int i=1;i<=2*n;i++) 72 instack[i]=visited[i]=false; 73 sn=counter=0; 74 for(int i=1;i<=n;i++) 75 { 76 if(!visited[i]) 77 tarjan(i); 78 } 79 for(int i=1;i<=n;i++) 80 { 81 vector<int> ans; 82 for(int j=0;j<group[set[i]].size();j++) 83 { 84 if(matrix[i][group[set[i]][j]-n]) 85 ans.push_back(group[set[i]][j]-n); 86 } 87 printf("%d",ans.size()); 88 for(int j=0;j<ans.size();j++) 89 printf(" %d",ans[j]); 90 printf("\n"); 91 ans.clear(); 92 } 93 for(int i=1;i<=2*n;i++) 94 arc[i].clear(); 95 for(int i=0;i<sn;i++) 96 group[i].clear(); 97 } 98 return 0; 99 }