uva 12017 Imitation

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

强连通分量 + 传递闭包相关知识

题意:给出一个有向图,求它的传递闭包的边数(也就是要求输出的最大值),另外消掉一些边,但是不影响整个图的传递关系,也就是消掉一些传递边,图剩下多少条边,输出边数(即输出的那个最小值)。例如1->2,2->3,1->3,1->3这条边可以消掉,它是一条传递边,且消掉它不影响整个图的传递关系

步骤

  1. 求最大值即传递闭包,比较容易,用类似floyd的方法一直递归下去即可
  2. 求最小值:先求一次强连通分量,然后缩点重新建图,得到一个DAG(为什么要求scc是因为一个scc以内的点的传递关系比较特殊,而不同scc内的传递关系要另外处理),对于一个scc,有n个点(n>1),那么这个scc内部只保留n条边就行了,就能表达这个scc内的传递关系了(原图中,一个scc内至少有n条边的,或者更多,但是更多的边是多余的,消掉它并不影响传递关系);如果特殊点,scc内只有1个点,那么这个scc内部的边数是0
  3. 在DAG上显然还需要消掉一些边,例如sample 1中就是一个DAG,对于这类情况要怎么做。做法比较直接,就是减去那些传递边,什么是传递边呢?如果DAG中已知x—>y,y—>z,但还存在一条边x—->z那么这条边就要消掉,所以我们的问题转变为找到这些边。做法是,对重新建图的这个DAG,又做一次传递闭包,做这次传递闭包,是为了知道任意两点间的传递关系。得到DAG的传递闭包后,枚举DAG中的每条边<u,v>,看看是否存在一个点vv,使得u->vv,vv->v,只要能找到一个vv,那么说明<u,v>就是一条传递边,要消掉

PS:UVA还是有很多好题的,已经半年没去过UVA了

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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <utility>
using namespace std;
#define N 1010
#define M 10010
#define cl memset
#define pb push_back
#define mp make_pair
#define pii pair<int,int>

int n;
vector<int>e[N],re[N];
bool g[N][N],ins[N],used[N];
int dfn[N],low[N],belong[N],num[N],stack[N],dcnt,bcnt,top;
vector<pii>list;

void floyd(int u , int v){
g[u][v] = true;
for(int i = 0; i < e[v].size(); i++){
int vv = e[v][i];
if(!g[u][vv])
floyd(u,vv);
}
}

int DFS(){
cl(g,false,sizeof(g));
for(int u = 1; u <= n ; u++)
for(int i = 0; i < e[u].size(); i++)
floyd(u,e[u][i]);
int res = 0;
for(int i = 1 ; i <= n; i++)
for(int j = 1; j <= n ; j++)
if(i != j && g[i][j])
res++;
return res;
}

void tarjan(int u){
dfn[u] = low[u] = ++dcnt;
stack[++top] = u; ins[u] = true;
for(int i = 0; i < e[u].size(); i++){
int v = e[u][i];
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--];
ins[x] = false;
belong[x] = bcnt;
num[bcnt]++;
if(x == u) break;
}
}
}

void scc(){
dcnt = bcnt = top = 0;
cl(dfn,0,sizeof(dfn));
cl(ins,false,sizeof(ins));
cl(num,0,sizeof(num));
for(int i = 1; i <= n ; i++)
if(!dfn[i])
tarjan(i);
}

void rebuild(){
list.clear();
cl(g,false,sizeof(g));
for(int i = 1; i <= bcnt; i++)
re[i].clear();
for(int i = 1 ; i <= n; i++)
for(int j = 0; j < e[i].size(); j++){
int u = belong[i];
int v = belong[e[i][j]];
if(u != v) g[u][v] = true;
}

for(int i = 1; i <= bcnt; i++)
for(int j = 1; j <= bcnt; j++)
if(g[i][j]){
re[i].pb(j);
list.pb(mp(i,j));
}
}

void dfs(int u, int v){
used[v] = true;
if(u != v) g[u][v] = true;
for(int i = 0; i < re[v].size(); i++)
if(!used[re[v][i]])
dfs(u,re[v][i]);
}

int solve(){
int res = list.size();

for(int i = 1; i <= bcnt; i++){
cl(used,false,sizeof(used));
dfs(i,i);
}

for(int i = 0; i < list.size(); i++){
int u = list[i].first , v = list[i].second;
for(int j = 1; j <= bcnt; j++)
if(g[u][j] && g[j][v]){
res--; break;
}
}
for(int i = 1; i <= bcnt; i++)
res += (num[i] == 1 ? 0 : num[i]);
return res;
}

int main(){
int cas,m;
scanf("%d",&cas);
for(int c = 1; c <= cas; c++){
scanf("%d%d",&n,&m);
for(int i = 1; i <= n ;i++)
e[i].clear();
while(m--){
int u,v;
scanf("%d%d",&u,&v);
e[u].pb(v);
}
int res2 = DFS(); //dfs找传递闭包
scc();
rebuild();
int res1 = solve();
printf("Case #%d: %d %d\n",c,res1,res2);
}
return 0;
}