hdu 3639 Hawk-and-Chicken

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

强连通分量 + 反向建图

题意:给出一个有向图,表示点与点之间的支持关系,支持关系可以传递,A支持B,B支持C,那么A支持C,C获得两个支持。找出哪些人获得最多支持,输出获得支持票数,然后升序点的标号

步骤

  1. 对图求一次强连通分量,得到一个DAG,因为一个强连通分量内,一个点可以得到其余所有点的支持。
  2. 得到DAG后,问题就变成了,一个点能被多少个点去到,那么就能获得多少票数。要知道一个点能被多少个点去到,一般就是反向建图。原图中一个点能被多少个点去到就变成了该点能去到多少个点,这个是很容易办到的,从这个点出发遍历,走过多少个点就是多少
  3. 因为要知道哪些点获得最高票数,可知这些点一定是入度为0的点里面选(这个最优性很容易证明不累述),所以每次只要从入度为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
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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
#define N 5010
#define M 30010
#define INF 0x3f3f3f3f
#define cl memset
#define pb push_back

int n,tot,head[N];
struct edge{
int v,next;
}e[M];
int dfn[N],low[N],belong[N],stack[N],ins[N],dcnt,bcnt,top;
int inde[N],num[N],vis[N];
vector<int>ver[N];
vector<int>scc[N];
vector<int>node,list;
int res;

inline void add(int u,int v){
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] = 1;
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],low[v]);
}
if(dfn[u] == low[u]){
++bcnt;
scc[bcnt].clear();
while(true){
int x = stack[top--];
ins[x] = 0;
belong[x] = bcnt;
scc[bcnt].pb(x);
if(x == u) break;
}
}
}
void SCC(){
dcnt = bcnt = top = 0;
cl(dfn,0,sizeof(dfn));
cl(ins,0,sizeof(ins));
for(int i = 0; i < n; i++)
if(!dfn[i])
tarjan(i);
}

void rebuild(){
for(int i = 0; i <= bcnt; i++){
inde[i] = 0;
ver[i].clear();
}
for(int i = 0; i < n ; i++)
for(int j = head[i]; j != -1; j = e[j].next){
int u = belong[i];
int v = belong[e[j].v];
if(u == v) continue;
ver[v].pb(u); //建逆图
inde[u]++;
}
}

void dfs(int u,int &sum){
vis[u] = 1; sum += scc[u].size();
for(int i = 0; i < ver[u].size(); i++)
if(!vis[ver[u][i]])
dfs(ver[u][i],sum);
}
void solve(){
res = -INF;
node.clear();
for(int i = 1; i <= bcnt; i++)
if(inde[i] == 0){
int sum = 0;
cl(vis,0,sizeof(vis));
dfs(i,sum);
if(sum > res){
res = sum;
node.clear();
node.pb(i);
}
else if(sum == res)
node.pb(i);
}
list.clear();
for(int i = 0; i < node.size(); i++){
int index = node[i];
for(int j = 0; j < scc[index].size(); j++)
list.pb(scc[index][j]);
}
sort(list.begin(),list.end());
}

int main(){
int cas,m;
scanf("%d",&cas);
for(int c = 1; c <= cas; c++){
tot = 0;
cl(head,-1,sizeof(head));
scanf("%d%d",&n,&m);
while(m--){
int u,v;
scanf("%d%d",&u,&v);
add(u,v);
}
SCC();
rebuild();
solve();
printf("Case %d: %d\n",c,res - 1);
for(int i = 0; i < list.size(); i++)
if(i == 0) printf("%d",list[i]);
else printf(" %d",list[i]);
printf("\n");
}
return 0;
}