LuoguP4819「中山市选2011」题解

发表于

Tarjan缩点

BZOJ2438
LuoguP4819

ps: 建议大家交完Luogu然后去BZOJ看一眼, 会发现一些神奇的东西🐸️

Description

一位冷血的杀手潜入Na-wiat，并假装成平民。警察希望能在N个人里面，查出谁是杀手。警察能够对每一个人进行查证，假如查证的对象是平民，他会告诉警察，他认识的人，谁是杀手，谁是平民。假如查证的对象是杀手，杀手将会把警察干掉。现在警察掌握了每一个人认识谁。每一个人都有可能是杀手，可看作他们是杀手的概率是相同的。

问：根据最优的情况，保证警察自身安全并知道谁是杀手的概率最大是多少？

Samples

Input #1

1
2
3
4
5
5 4 
1 2 
1 3 
1 4 
1 5

Output #1

1
0.800000

Solution

考虑把认识关系连成一条有向的边, 那么所有的关系将会构成一张有向图.

容易发现, 在一个强连通分量里面的节点, 只要查其中一个点, 那么就可以获得其他所有点的信息.

那么我们就可以先来一遍Tarjan缩点.

如果我们发现,调查完除了某个人之外的所有人之后都没有发现目标, 那么此人一定是目标.

这种情况下就不需要再调查了, 那么考虑特判掉这种不在任何一个强连通分量里的节点, 设这种节点有$x$个, 那么答案一定是:

$$1 - \frac {1 - x - [x != 0]}{n}$$

Code

具体细节可以康康代码, 里面有较详细的注释.

ps: 码风又改回来了.

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
145
146
147
148
149
150
151
152
/* Headers */
#include<algorithm>
#include<iostream>
#include<cstring>
#include<climits>
#include<cstdio>
#include<cctype>
#include<vector>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#define FOR(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define ROF(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define FORL(i,a,b,c) for(long long i=(a);i<=(b);i+=(c))
#define ROFL(i,a,b,c) for(long long i=(a);i>=(b);i-=(c))
#define FORR(i,a,b,c) for(register int i=(a);i<=(b);i+=(c))
#define ROFR(i,a,b,c) for(register int i=(a);i>=(b);i-=(c))
#define lowbit(x) x&(-x)
#define LeftChild(x) x<<1
#define RightChild(x) (x<<1)+1
#define RevEdge(x) x^1
#define FILE_IN(x) freopen(x,"r",stdin);
#define FILE_OUT(x) freopen(x,"w",stdout);
#define CLOSE_IN() fclose(stdin);
#define CLOSE_OUT() fclose(stdout);
#define IOS(x) std::ios::sync_with_stdio(x)
#define Dividing() printf("-----------------------------------\n");
namespace FastIO{
    const int BUFSIZE = 1 << 20;
    char ibuf[BUFSIZE],*is = ibuf,*its = ibuf;
    char obuf[BUFSIZE],*os = obuf,*ot = obuf + BUFSIZE;
    inline char getch(){
        if(is == its)
            its = (is = ibuf)+fread(ibuf,1,BUFSIZE,stdin);
        return (is == its)?EOF:*is++;
    }
    inline int getint(){
        int res = 0,neg = 0,ch = getch();
        while(!(isdigit(ch) || ch == '-') && ch != EOF)
            ch = getch();
        if(ch == '-'){
            neg = 1;ch = getch();
        }
        while(isdigit(ch)){
            res = (res << 3) + (res << 1)+ (ch - '0');
            ch = getch();
        }
        return neg?-res:res;
    }
    inline void flush(){
        fwrite(obuf,1,os - obuf,stdout);
        os = obuf;
    }
    inline void putch(char ch){
        *os++ = ch;
        if(os == ot)	flush();
    }
    inline void putint(int res){
        static char q[10];
        if(res == 0) putch('0');
        else if(res < 0){putch('-');res = -res;}
        int top = 0;
        while(res){
            q[top++] = res % 10 + '0';
            res /= 10;
        }
        while(top--)	putch(q[top]);
    }
    inline void space(bool x){
    	if(!x) putch('\n');
    	else putch(' ');
    }
}
inline void read(int &x){
    int rt = FastIO::getint();
    x = rt;
}
inline void print(int x,bool enter){
    FastIO::putint(x);
    FastIO::flush();
    FastIO::space(enter);
}
/* definitions */
const int MAXN = 1e5 + 10;
const int MAXM = 3e5 + 10;
int n, m, EDGE[MAXM][2], head[MAXN], cnt, tot, deg[MAXN];
int low[MAXN], dfn[MAXN], sum[MAXN], indexs, Belong[MAXN];
std::stack<int> sta;
struct Edge{int next, to;}Graph[MAXM << 1];
/* functions */
inline void clear() {
	cnt = 0;
	memset(head, 0, sizeof head);
}
inline void Add_Edge(int from, int to) {
	Graph[++cnt] = (Edge) {head[from], to};
	head[from] = cnt;
}
inline void Tarjan(int u) { //Tarjan缩点
	dfn[u] = low[u] = ++indexs;
	sta.push(u);
	for(int i = head[u]; i; i = Graph[i].next) {
		int v = Graph[i].to;
		if(!dfn[v]) {
			Tarjan(v);
			low[u] = std::min(low[u], low[v]);
		}
		else if(!Belong[v]) low[u] = std::min(low[u], dfn[v]);
	}
	if(low[u] == dfn[u]) {
		Belong[u] = ++tot;
		sum[tot]++;
		while(sta.top() != u) {
			Belong[sta.top()] = tot;
			sum[tot]++; sta.pop();
		}
		sta.pop();
	}
}
double ans;
bool flag;
//flag : 是否存在入度为0的节点
int main(int argc,char *argv[]){
	scanf("%d %d", &n, &m);
	FOR(i, 1, m, 1) {
		scanf("%d %d", &EDGE[i][0], &EDGE[i][1]);
		Add_Edge(EDGE[i][0], EDGE[i][1]);
	}
	FOR(i, 1, n, 1) if(!dfn[i]) Tarjan(i);
	clear(); // 清空
	FOR(i, 1, m, 1) {
		if(Belong[EDGE[i][0]] == Belong[EDGE[i][1]]) continue;
		deg[Belong[EDGE[i][1]]]++; // 统计入度
		Add_Edge(Belong[EDGE[i][0]], Belong[EDGE[i][1]]); // 缩点之后重建图
	}
	FOR(u, 1, tot, 1) {
		if(!flag && !deg[u] && sum[u] == 1) {
			bool vis = false; 
			for(int i = head[u]; i; i = Graph[i].next) {
				int v = Graph[i].to;
				if(deg[v] == 1) vis = true;				
			}
			if(!vis) flag = true; 
		}
		if(!deg[u]) ans++; // 统计有多少入度为0的点
	}
	if(flag) ans--; // 如果存在, 可以少查一次
	ans = 1.0 - (double)ans / (double)n;
	printf("%.6lf\n", ans);	
	return 0;
}

THE END