poj 1904 King's Quest

本文从WordPress迁移而来, 查看全部WordPress迁移文章

连通分量

题意:有n个男人和n个女人,下面n行依次给出每个男人喜欢那些女人(男人和女人都分别从1到n编号),这些男人最后只能跟他喜欢的女人结婚。另外一行内给出n个数字,表示一种匹配方案,第i个数字m[i],表示m[i]这个女人要嫁给i这个男人。注意,这个方案是一个合法的方案,即一个女人一定对应一个男人,而且这个女人一定是上面给出的,这个男人喜欢的女人之一。问题是,除了这个合法的方案,还没有没其他合法的方案,合法的方案就是,每个男人都可以娶到女人,每个女人只会嫁一个男人

这题一个突破口是那个合法的方案。如果男人u喜欢女人v,就添加一个有向边u->v,在合法方案中,将女人a嫁给了男人b,那么添加一条有向边a->b

我们来考虑一下这个图,这个图至少存在n个小环,因为可行方案产生了n对合法的夫妻,一对夫妻之间形成一个小环。

暂且把这n个小环看做N个点。看看点和点之间有没有边,如果有边,一定是一条男人指向女人的边,因为我们在添加有向边的时候,女人指向男人的边只有n条,就是那个合法方案产生的n条,这n条边都在小环里面了,所以其他边一定是男人指向女人的边。在这N个点中,可不可能形成环内,是可能的。如果这N个点不形成环会怎样?从A这个点出发,最终回不到A这个点!从A出发,指向B,意思就是A里面的那个男人,指向了B里面的女人(大点之间的边一定是男人指向女人的边),那么A里面的女人就没人匹配了,接着如果B指向C,说明B里面的男人指向C里面的女人,那么B里面的女人又没人匹配了………………

说明就很明显了,对于一个大点X,如果X可以指向别的点Y,并且选择了这条边的话,那么说明X里面的男人选择了Y里面的女人,那么X里面的女人必定没人匹配了,并且Y里面的男人也是没人匹配的,那么Y男人一定要到别的点找女人,也必定导致那个点的男人无法匹配,以此类推…..一个点的男人夺走了其他点的女人那么那个点的男人一定要去别处找女人,唯一完满的结局就是某个男人找到了第1个女人,别忘了那个女人还没人匹配。这样才能结束这个死循环。

所以如果大点能形成环,那么环内的大点里面的男人就有了不止一种选择,并且做出不同的选择都会合法。再说得直白一点就是,对于一个连通分量里面的男人,它可能选择这个连通分量里面的任意一个女人(但是这个女人必须是他喜欢的,有的女人他不喜欢但也可以到达),并且保证合法
其实这题给出了一组可行解,就是一个最大的突破口,试想就算没给出这组可行解一样可以问同样的问题,但是恐怕就没那么好想了。如果真的没有给出可行解,可以运行一次最大匹配,那么就找到了一组可行解,就变为了原题

注意最后答案是要排序再输出的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 4010
#define M 202010
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))

int n,tot,head[N];
struct edge{
int u,v,next;
}e[M];
int dfn[N],low[N],belong[N],stack[N],dcnt,bcnt,top;
bool ins[N];
int ans[N>>1][N>>1],cnt[N>>1];

inline void add(int u,int v){
e[tot].u = u; e[tot].v = v;
e[tot].next = head[u]; head[u] = tot++;
}

void tarjan(int u){
dfn[u] = low[u] = ++dcnt;
stack[++top] = u; ins[u] = true;
for(int k = head[u]; k != -1; k = e[k].next){
int v = e[k].v;
if(!dfn[v]){
tarjan(v);
low[u] = min(low[u],low[v]);
}
else if(ins[v])
low[u] = min(low[u],dfn[v]);
}
if(dfn[u] == low[u]){
++bcnt;
while(true){
int x = stack[top--];
belong[x] = bcnt; ins[x] = false;
if(x == u) break;
}
}
}

void scc(){
dcnt = bcnt = top = 0;
cl(dfn,0); cl(ins,false);
for(int i = 1; i <= 2*n; i++)
if(!dfn[i])
tarjan(i);
/*
for(int i = 1; i <= 2*n; i++)
printf("%d[%d] ",i,belong[i]);
printf("\n");
*/
}

int main(){
while(scanf("%d",&n)!=EOF){
tot = 0; cl(head,-1);
for(int u = 1; u <= n; u++){
int m;
scanf("%d",&m);
while(m--){
int v;
scanf("%d",&v);
add(u,v+n);
}
}
for(int u = 1; u <= n; u++){
int v;
scanf("%d",&v);
add(v+n,u);
}
scc();
cl(cnt,0);
for(int u = 1; u <= n; u++){
for(int k = head[u]; k != -1; k = e[k].next){
int v = e[k].v;
if(belong[u] == belong[v]){
int id = cnt[u]++;
ans[u][id] = v-n;
}
}
}
for(int u = 1; u <= n; u++){
sort(ans[u],ans[u]+cnt[u]);
printf("%d",cnt[u]);
for(int i = 0; i < cnt[u]; i++)
printf(" %d",ans[u][i]);
printf("\n");
}
}
return 0;
}