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