hdu 4635 Strongly connected

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

连通分量

【2013多校联合训练第四场】

题意:给定一个有向简单图(无重边,无自环的有向图,但可以有环),你需要给这个图加有向边,但要保证他依然是有向简单图,并且不会变成一个强连通分量,输出最多能添加多少边。如果这个图一开始就是强连通的,输出-1

  1. 先对有向图求一个SCC,缩点,得到一个DAG。
  2. 如果缩点后只有1个点,即整个图是强连通的,输出-1结束
  3. 若不是要怎么办呢?一个DAG,必定存在至少一个点,它的入度为0,或者出度为0(如果全部点都有入度和出度,那么这个图肯定不是DAG,这个很容易想清楚),那么我们选这些点中的一个,保证它的入度或出度依然是0(如果这个点入度和出度都为0,那么只需要保留一个即可,即保留入度或出度为0即可),然后不停加边,加到不能再加为止。为什么可以这样做?因为只要这个点依然是入度或出度为0,那么它就肯定去不到其他点或者其他点肯定去不到它,这样这个图肯定不是强连通的。

那么我们可以在纸上对着这个DAG画,我们选定了A点,它的入度为0,那么要保证入度为0,不要画边出去。那么对于其他点,每个点都画出了n-1条边,对于其他点而言,画成了几乎是一个完全图的样子。因为点A可以由出度,那么它一指向了其他n-1个点。

这时候要解放大点,从小点来看(即解放缩点,从原图的点来看),缩点A没有入度,其实就是其他连通分支都不能指向A这个连通分支,那么其他连通分支假设有n-cnt个点(cnt是A这个连通分支有的点),那么将少加(n-cnt)*cnt条边(相对于完全图来讲,少加这么多条)。还要减去已经有的边

完全图的边数 n * (n-1)

保证一个连通分量入度或出度为0,这个连通分量点数为cnt,那么少加的边为(n-cnt)* cnt

原来有的边为 tot

那么新加的边为 n (n-1) - (n-cnt) cnt - tot

这个就是答案。

可见这个式子只受cnt影响,要式子和最大,就是要(n-cnt) * cnt最小,不过不必纠结于这个式子,暴力枚举一下所有的cnt即可

这题其实不难的,但是文字上说的还是不太清楚。

整个题的突破口是,缩点后的到一个DAG,在这个DAG中保留一个点的入度或出度为0,其他点能加多少边加多少边

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
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define N 100010
#define M 100010
#define INF 0x3f3f3f3f
#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],cnt[N],in[N],out[N],stack[N],dcnt,bcnt,top;
bool ins[N];
int ANS;
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;
cnt[bcnt]++;
if(x == u) break;
}
}
}

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

inline int cal(int u){
return n*(n-1) - (n-cnt[u])*cnt[u] - tot;
}

void solve(){
cl(in,0); cl(out,0);
for(int i = 0; i < tot; i++){
int u = belong[e[i].u];
int v = belong[e[i].v];
if(u != v){
in[v]++; out[u]++;
}
}
ANS = -INF;
for(int i = 1; i <= n; i++){
int u = belong[i];
if(in[u] == 0 || out[u] == 0){
ANS = max(ANS,cal(u));
}
}
}

int main(){
int T,m;
scanf("%d",&T);
for(int cas = 1; cas <= T; cas++){
scanf("%d%d",&n,&m);
tot = 0; cl(head,-1);
while(m--){
int u,v;
scanf("%d%d",&u,&v);
add(u,v);
}
printf("Case %d: ",cas);
scc();
if(bcnt == 1){
puts("-1");
continue;
}
solve();
printf("%d\n",ANS);
}
return 0;
}