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
題目給我們一個2*N個頂點的2分圖，并且給了一個完美匹配(Perfect Matching)以及每個頂點可以連接的其他的頂點。
題目要求是否可以確定某2個頂點連邊后，其他2*(N - 1)個頂點的2分圖是否可以構(gòu)成完美匹配。
分析：題目給了你一個
初始的最大匹配 怎樣用好這個匹配是非常關鍵的
首先把圖轉(zhuǎn)化成有向圖(因為后面我們要用到連通性判定)
現(xiàn)在令王子為A集合，公主為B集合
原圖中所有的邊轉(zhuǎn)化成A->B的邊 然后對原來的每一個匹配Ai->Bj 添加一條從Bj到Ai的邊
結(jié)論： 如果Ai，Bj能夠互訪 我們則認為Ai, Bj作為一條匹配邊仍然不會影響其他王子和自己心愛的人匹配
證明如下：
現(xiàn)在有一個匹配Ai->Bj 我們知道Ai和Bj可以互訪
我們要驗證其是否可以成立時對其他王子找MM沒有影響
1。如果題目中給的初始匹配包含這條邊 則題目給出的初始匹配就證明了這位王子的公德心
2。如果題目沒有給出這條邊 給出的是Ai -> Bk 由于Ai與Bk也可互訪 所以存在Bj->Ai->Bk的增廣路 也就是說可以建立另外一個匹配A?->Bk
所以同一個連通分量內(nèi)部是可以換匹配的 呵呵
關于求極大連通子圖的方法 具體如下:
求有向圖的極大強連通分支 1.對圖進行DFS遍歷 遍歷中記下所有的結(jié)束時間A[i].遍歷的結(jié)果是構(gòu)建的一座森林W1
我們對W1中的每棵樹G進行步驟2到步驟3的操作
2.改變圖G中每一條邊的方向 構(gòu)造出新的有向圖Gr
3.按照A[i]由小到大的順序?qū)r進行DFS遍歷.遍歷的結(jié)果是構(gòu)建了新的樹林W2.
W2中每棵樹上的頂點構(gòu)成了有向圖的極大強連通分支
如果對DFS的相關算法不熟悉 請參考我的另一篇文章
圖的DFS信息構(gòu)建+割點，橋，極大連通子圖三大法寶http://www.shnenglu.com/sicheng/archive/2007/01/19/17767.html如果覺得上面的方法
太麻煩 還有一種
簡單的方法(呵呵), 具體步驟如下:
我們定義定點U的標值函數(shù) LOW(U) = min { dfn(U), dfn(W) };
其中W是U或者U的后代點通過反向邊或者橫叉邊能夠到達的
同一個連通分量的定點
dfn()是指一個點第一次被訪問的時間
由此可以看出 LOW(U)正是U所處的強連通分支中從U出發(fā)先通過樹枝邊(組成DFS樹的邊),前向邊,最后用后向邊或者橫叉邊到達的dfn的最小的定點的標值.而對于強分支的根Ri,顯然LOW(Ri) = dfn(Ri). 因此當深度有限搜索從一個使dfn = LOW的定點U返回時,從樹中移去根為U的所有頂點.每一個這種的集合是一個強分支.
算法的主要思路是逐步迭代算出LOW值:
當?shù)谝淮卧L問定點U時: LOW(U) = Min(LOW(U), dfn(U))
后向邊(U,W)被檢查時: LOW(U) = Min(LOW(U), dfn(W))
處于同一強分支的橫叉邊被檢查時: LOW(U) = MIN(LOW(U), dfn(W))
檢查了U的兒子S的所有關聯(lián)邊后返回頂點U時: LOW(U) = Min(LOW(U), LOW(S))
這樣就可以用
一個DFS解決啦~
foj的一個"
信與信封"的題目也可以用強連通來做 不過那個題目數(shù)據(jù)弱多了 枚舉+2分圖最大匹配也能過
下面這個程序是用第二種求法解決的:
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é)點的時間
9int love[N][N]; // love[i][j]代表i王子愛上j公主 即i向j連接一條邊
10int scc[N]; //scc代表強連通分量id (Strongly Connected Component ID)
11bool inS[N]; //inS代表是否在棧中(已被壓入且為被彈出) 注意 表示一個節(jié)點沒有被訪問過應該是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; //標記入棧
21 int y = back[x], z; //找到相應王子
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的所有關聯(lián)邊后返回頂點x
30 }
31 else if(dfn[j] < dfn[x] && inS[j]) //處于同一強分支的后向邊或者橫叉邊被檢查
32 low[x] = Min(low[x], dfn[j]);
33 }
34 }
35
36 if(low[x] == dfn[x]) { //找到一個新的強連通分支
37 do {
38 z = S.back();
39 scc[z] = sccId; //標記連通分值
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); //對每個公主作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]]) //如果在同一個連通分量內(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; //標記連通分支
28 for(i = 0; i < head2[y].size(); ++i) {
29 int j = go[head2[y][i]]; //找到對應的公主
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); //對王子作DFS 確定i到達的點
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); //再對公主做DFS 確定連通分支(對王子和對公主其實是一樣的 寫法有點不同而已:)
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)簡單的方法寫出來的程序還長一點點。。暈