King's Quest
Time Limit:15000MS Memory Limit:65536K
Total Submit:938 Accepted:278
Case Time Limit:2000MS
Description
Once upon a time there lived a king and he had N sons. And there were N beautiful girls in the kingdom and the king knew about each of his sons which of those girls he did like. The sons of the king were young and light-headed, so it was possible for one son to like several girls.
So the king asked his wizard to find for each of his sons the girl he liked, so that he could marry her. And the king's wizard did it -- for each son the girl that he could marry was chosen, so that he liked this girl and, of course, each beautiful girl had to marry only one of the king's sons.
However, the king looked at the list and said: "I like the list you have made, but I am not completely satisfied. For each son I would like to know all the girls that he can marry. Of course, after he marries any of those girls, for each other son you must still be able to choose the girl he likes to marry."
The problem the king wanted the wizard to solve had become too hard for him. You must save wizard's head by solving this problem.
Input
The first line of the input contains N -- the number of king's sons (1 <= N <= 2000). Next N lines for each of king's sons contain the list of the girls he likes: first Ki -- the number of those girls, and then Ki different integer numbers, ranging from 1 to N denoting the girls. The sum of all Ki does not exceed 200000.
The last line of the case contains the original list the wizard had made -- N different integer numbers: for each son the number of the girl he would marry in compliance with this list. It is guaranteed that the list is correct, that is, each son likes the girl he must marry according to this list.
Output
Output N lines.For each king's son first print Li -- the number of different girls he likes and can marry so that after his marriage it is possible to marry each of the other king's sons. After that print Li different integer numbers denoting those girls, in ascending order.
Sample Input
4
2 1 2
2 1 2
2 2 3
2 3 4
1 2 3 4
Sample Output
2 1 2
2 1 2
1 3
1 4
Hint
This problem has huge input and output data,use scanf() and printf() instead of cin and cout to read data to avoid time limit exceed.
Source
Northeastern Europe 2003
題目給我們一個(gè)2*N個(gè)頂點(diǎn)的2分圖，并且給了一個(gè)完美匹配(Perfect Matching)以及每個(gè)頂點(diǎn)可以連接的其他的頂點(diǎn)。
題目要求是否可以確定某2個(gè)頂點(diǎn)連邊后，其他2*(N - 1)個(gè)頂點(diǎn)的2分圖是否可以構(gòu)成完美匹配。
分析：題目給了你一個(gè)
初始的最大匹配 怎樣用好這個(gè)匹配是非常關(guān)鍵的
首先把圖轉(zhuǎn)化成有向圖(因?yàn)楹竺嫖覀円玫竭B通性判定)
現(xiàn)在令王子為A集合，公主為B集合
原圖中所有的邊轉(zhuǎn)化成A->B的邊 然后對(duì)原來的每一個(gè)匹配Ai->Bj 添加一條從Bj到Ai的邊
結(jié)論： 如果Ai，Bj能夠互訪 我們則認(rèn)為Ai, Bj作為一條匹配邊仍然不會(huì)影響其他王子和自己心愛的人匹配
證明如下：
現(xiàn)在有一個(gè)匹配Ai->Bj 我們知道Ai和Bj可以互訪
我們要驗(yàn)證其是否可以成立時(shí)對(duì)其他王子找MM沒有影響
1。如果題目中給的初始匹配包含這條邊 則題目給出的初始匹配就證明了這位王子的公德心
2。如果題目沒有給出這條邊 給出的是Ai -> Bk 由于Ai與Bk也可互訪 所以存在Bj->Ai->Bk的增廣路 也就是說可以建立另外一個(gè)匹配A?->Bk
所以同一個(gè)連通分量內(nèi)部是可以換匹配的 呵呵
關(guān)于求極大連通子圖的方法 具體如下:
求有向圖的極大強(qiáng)連通分支 1.對(duì)圖進(jìn)行DFS遍歷 遍歷中記下所有的結(jié)束時(shí)間A[i].遍歷的結(jié)果是構(gòu)建的一座森林W1
我們對(duì)W1中的每棵樹G進(jìn)行步驟2到步驟3的操作
2.改變圖G中每一條邊的方向 構(gòu)造出新的有向圖Gr
3.按照A[i]由小到大的順序?qū)r進(jìn)行DFS遍歷.遍歷的結(jié)果是構(gòu)建了新的樹林W2.
W2中每棵樹上的頂點(diǎn)構(gòu)成了有向圖的極大強(qiáng)連通分支
如果對(duì)DFS的相關(guān)算法不熟悉 請(qǐng)參考我的另一篇文章
圖的DFS信息構(gòu)建+割點(diǎn)，橋，極大連通子圖三大法寶http://www.shnenglu.com/sicheng/archive/2007/01/19/17767.html如果覺得上面的方法
太麻煩 還有一種
簡單的方法(呵呵), 具體步驟如下:
我們定義定點(diǎn)U的標(biāo)值函數(shù) LOW(U) = min { dfn(U), dfn(W) };
其中W是U或者U的后代點(diǎn)通過反向邊或者橫叉邊能夠到達(dá)的
同一個(gè)連通分量的定點(diǎn)
dfn()是指一個(gè)點(diǎn)第一次被訪問的時(shí)間
由此可以看出 LOW(U)正是U所處的強(qiáng)連通分支中從U出發(fā)先通過樹枝邊(組成DFS樹的邊),前向邊,最后用后向邊或者橫叉邊到達(dá)的dfn的最小的定點(diǎn)的標(biāo)值.而對(duì)于強(qiáng)分支的根Ri,顯然LOW(Ri) = dfn(Ri). 因此當(dāng)深度有限搜索從一個(gè)使dfn = LOW的定點(diǎn)U返回時(shí),從樹中移去根為U的所有頂點(diǎn).每一個(gè)這種的集合是一個(gè)強(qiáng)分支.
算法的主要思路是逐步迭代算出LOW值:
當(dāng)?shù)谝淮卧L問定點(diǎn)U時(shí): LOW(U) = Min(LOW(U), dfn(U))
后向邊(U,W)被檢查時(shí): LOW(U) = Min(LOW(U), dfn(W))
處于同一強(qiáng)分支的橫叉邊被檢查時(shí): LOW(U) = MIN(LOW(U), dfn(W))
檢查了U的兒子S的所有關(guān)聯(lián)邊后返回頂點(diǎn)U時(shí): LOW(U) = Min(LOW(U), LOW(S))
這樣就可以用
一個(gè)DFS解決啦~
foj的一個(gè)"
信與信封"的題目也可以用強(qiáng)連通來做 不過那個(gè)題目數(shù)據(jù)弱多了 枚舉+2分圖最大匹配也能過
下面這個(gè)程序是用第二種求法解決的:
Solution:
//by oyjpArt
1
#include <vector>
2#include <algorithm>
3using namespace std;
4
5const int N = 2010;
6int nv, times, sccId;
7int go[N], back[N]; //匹配的正向和反向
8int low[N], dfn[N]; //low數(shù)組, dfn是第一次訪問某節(jié)點(diǎn)的時(shí)間
9int love[N][N]; // love[i][j]代表i王子愛上j公主 即i向j連接一條邊
10int scc[N]; //scc代表強(qiáng)連通分量id (Strongly Connected Component ID)
11bool inS[N]; //inS代表是否在棧中(已被壓入且為被彈出) 注意 表示一個(gè)節(jié)點(diǎn)沒有被訪問過應(yīng)該是dfn[i] == 0
12vector<int> S; //Stack
13
14#define Min(a, b) ((a) < (b) ? (a) : (b))
15
16void DFS(int x) {
17 int i;
18 dfn[x] = ++times; //第一次訪問
19 S.push_back(x); //壓入棧中
20 inS[x] = 1; //標(biāo)記入棧
21 int y = back[x], z; //找到相應(yīng)王子
22 low[x] = times; //定義low[x]
23
24 for(i = 1; i <= love[y][0]; ++i) {
25 int j = love[y][i];
26 if(j != x) {
27 if(dfn[j] == 0) { //樹枝邊
28 DFS(j);
29 low[x] = Min(low[x], low[j]); //檢查了x的兒子j的所有關(guān)聯(lián)邊后返回頂點(diǎn)x
30 }
31 else if(dfn[j] < dfn[x] && inS[j]) //處于同一強(qiáng)分支的后向邊或者橫叉邊被檢查
32 low[x] = Min(low[x], dfn[j]);
33 }
34 }
35
36 if(low[x] == dfn[x]) { //找到一個(gè)新的強(qiáng)連通分支
37 do {
38 z = S.back();
39 scc[z] = sccId; //標(biāo)記連通分值
40 inS[z] = false; //出棧
41 S.pop_back();
42 }while(z != x);
43 sccId++;
44 }
45}
46
47int main() {
48
49 scanf("%d", &nv);
50 int i, t, j;
51 for(i = 0; i < nv; ++i) {
52 scanf("%d", &love[i][0]);
53 for(j = 1; j <= love[i][0]; ++j) {
54 scanf("%d", &love[i][j]);
55 --love[i][j];
56 }
57 }
58 for(i = 0; i < nv; ++i) {
59 scanf("%d", &t);
60 go[i] = t-1;
61 back[t-1] = i;
62 }
63
64 times = sccId = 0;
65 memset(inS, 0, sizeof(inS));
66 memset(dfn, 0, sizeof(dfn));
67 for(i = 0; i < nv; ++i) if(dfn[i] == 0) {
68 DFS(i); //對(duì)每個(gè)公主作DFS
69 }
70
71 for(i = 0; i < nv; ++i) {
72 vector<int> ans;
73 for(j = 1; j <= love[i][0]; ++j) {
74 if(scc[love[i][j]] == scc[go[i]]) //如果在同一個(gè)連通分量內(nèi)
75 ans.push_back(love[i][j]);
76 }
77 sort(ans.begin(), ans.end());
78 printf("%d", ans.size());
79 for(j = 0; j < ans.size(); ++j)
80 printf(" %d", ans[j]+1);
81 printf("\n");
82 }
83
84 return 0;
85}
下面這種求法是用第一種方法解決的
Solution:
//by oyjpArt
1#include <vector>
2#include <algorithm>
3using namespace std;
4
5const int N = 2010;
6int nv;
7vector<int> head[N], head2[N], S;
8int go[N], back[N];
9int scc[N];
10bool chk[N];
11bool love[N][N];
12
13void DFS(int x) {
14 int i;
15 chk[x] = 1;
16 for(i = 0; i < head[x].size(); ++i) {
17 int j = back[head[x][i]];
18 if(!chk[j])
19 DFS(j);
20 }
21 S.push_back(x); //入棧
22}
23
24void DFS2(int x, int id) {
25 int y = go[x], i;
26 chk[y] = 1;
27 scc[x] = id; //標(biāo)記連通分支
28 for(i = 0; i < head2[y].size(); ++i) {
29 int j = go[head2[y][i]]; //找到對(duì)應(yīng)的公主
30 if(!chk[j])
31 DFS2(head2[y][i], id);
32 }
33}
34
35int main() {
36 scanf("%d", &nv);
37 int i, t, u, j;
38 for(i = 0; i < nv; ++i) {
39 scanf("%d", &t);
40 while(t--) {
41 scanf("%d", &u);
42 love[i][u-1] = 1;
43 head[i].push_back(u-1); //有向邊
44 head2[u-1].push_back(i); //逆轉(zhuǎn)的有向邊
45 }
46 }
47 for(i = 0; i < nv; ++i) {
48 scanf("%d", &t);
49 go[i] = t-1;
50 back[t-1] = i;
51 }
52
53 memset(chk, 0, sizeof(chk));
54 for(i = 0; i < nv; ++i) if(!chk[i]) {
55 DFS(i); //對(duì)王子作DFS 確定i到達(dá)的點(diǎn)
56 }
57
58 memset(chk, 0, sizeof(chk));
59 int sccId = 0;
60 for(i = S.size()-1; i >= 0; --i) {
61 int j = S[i];
62 if(!chk[go[j]]) {
63 DFS2(j, sccId); //再對(duì)公主做DFS 確定連通分支(對(duì)王子和對(duì)公主其實(shí)是一樣的 寫法有點(diǎn)不同而已:)
64 sccId++;
65 }
66 }
67
68 for(i = 0; i < nv; ++i) {
69 vector<int> ans;
70 for(j = 0; j < nv; ++j) if(love[i][j]) {
71 if(scc[i] == scc[back[j]])
72 ans.push_back(j);
73 }
74 sort(ans.begin(), ans.end());
75 printf("%d", ans.size());
76 for(j = 0; j < ans.size(); ++j)
77 printf(" %d", ans[j]+1);
78 printf("\n");
79 }
80
81 return 0;
82}
突然發(fā)現(xiàn)簡單的方法寫出來的程序還長一點(diǎn)點(diǎn)。。暈