「BZOJ2438」[中山市选2011] 杀人游戏

一位冷血的杀手潜入 Na-wiat，并假装成平民。警察希望能在 N 个人里面，
查出谁是杀手。
警察能够对每一个人进行查证，假如查证的对象是平民，他会告诉警察，他
认识的人，谁是杀手，谁是平民。假如查证的对象是杀手，杀手将会把警察干掉。
现在警察掌握了每一个人认识谁。
每一个人都有可能是杀手，可看作他们是杀手的概率是相同的。
问：根据最优的情况，保证警察自身安全并知道谁是杀手的概率最大是多
少？

第一行有两个整数 N,M。
接下来有 M 行，每行两个整数 x,y，表示 x 认识 y（y 不一定认识 x,例如胡锦涛同志）。

仅包含一行一个实数，保留小数点后面 6 位，表示最大概率。

5 4
1 2
1 3
1 4
1 5

0.800000

警察只需要查证 1。假如1是杀手，警察就会被杀。假如 1不是杀手，他会告诉警
察 2,3,4,5 谁是杀手。而 1 是杀手的概率是 0.2,所以能知道谁是杀手但没被杀的概
率是0.8。

对于 100%的数据有 1≤N ≤ 10 0000,0≤M ≤ 30 0000

倘若存在只有一个点的连通块，它无出边或出边指向的点均能被其它点到达则ans–

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<set>
#include<ctime>
#include<vector>
#include<queue>
#include<algorithm>
#include<map>
#define inf 1000000000
#define pa pair<int,int>
#define ll long long 
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m,scc,cnt,ans,ind,top;
int last[100005],last2[100005],d[100005];
int low[100005],dfn[100005],q[100005],bl[100005],num[100005];
bool inq[100005],mark[100005];
struct edge{
    int to,next,v;
}e[300005],ed[300005];
void insert(int u,int v)
{
    e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;
}
void insert2(int u,int v)
{
    d[v]++;
    ed[++cnt].to=v;ed[cnt].next=last2[u];last2[u]=cnt;
}
void tarjan(int x)
{
    low[x]=dfn[x]=++ind;
    inq[x]=1;q[++top]=x;
    for(int i=last[x];i;i=e[i].next)
        if(!dfn[e[i].to])
        {
            tarjan(e[i].to);
            low[x]=min(low[x],low[e[i].to]);
        }
        else if(inq[e[i].to])
            low[x]=min(low[x],dfn[e[i].to]);
    if(low[x]==dfn[x])
    {
        int now=0;scc++;
        while(x!=now)
        {
            now=q[top];top--;
            bl[now]=scc;
            inq[now]=0;
            num[scc]++;
        } 
    }
}
void rebuild()
{
    cnt=0;
    for(int x=1;x<=n;x++)
    {
        for(int i=last[x];i;i=e[i].next)
            if(bl[x]!=bl[e[i].to]&&!mark[bl[e[i].to]])
                mark[bl[e[i].to]]=1,insert2(bl[x],bl[e[i].to]);
        for(int i=last[x];i;i=e[i].next)
            if(bl[x]!=bl[e[i].to])
                mark[bl[e[i].to]]=0;
    }
}
bool jud(int x)
{
    if(d[x]!=0||num[x]!=1)return 0;
    for(int i=last2[x];i;i=ed[i].next)
        if(d[ed[i].to]==1)return 0;
    return 1;
}
int main()
{
    n=read();m=read();
    for(int i=1;i<=m;i++)
    {
        int u=read(),v=read();
        insert(u,v);
    }
    for(int i=1;i<=n;i++)
        if(!dfn[i])tarjan(i);
    rebuild();
    for(int i=1;i<=scc;i++)
        if(!d[i])ans++;
    for(int i=1;i<=scc;i++)
        if(jud(i))
        {
            ans--;break;
        }
    printf("%.6lf",(double)(n-ans)/n);
    return 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

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<set>

#include<ctime>

#include<vector>

#include<queue>

#include<algorithm>

#include<map>

#define inf 1000000000

#define pa pair<int,int>

#define ll long long

using namespace std;

inline int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n,m,scc,cnt,ans,ind,top;

int last[100005],last2[100005],d[100005];

int low[100005],dfn[100005],q[100005],bl[100005],num[100005];

bool inq[100005],mark[100005];

struct edge{

int to,next,v;

}e[300005],ed[300005];

void insert(int u,int v)

{

e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;

}

void insert2(int u,int v)

{

d[v]++;

ed[++cnt].to=v;ed[cnt].next=last2[u];last2[u]=cnt;

}

void tarjan(int x)

{

low[x]=dfn[x]=++ind;

inq[x]=1;q[++top]=x;

for(int i=last[x];i;i=e[i].next)

if(!dfn[e[i].to])

{

tarjan(e[i].to);

low[x]=min(low[x],low[e[i].to]);

}

else if(inq[e[i].to])

low[x]=min(low[x],dfn[e[i].to]);

if(low[x]==dfn[x])

{

int now=0;scc++;

while(x!=now)

{

now=q[top];top--;

bl[now]=scc;

inq[now]=0;

num[scc]++;

}

void rebuild()

{

cnt=0;

for(int x=1;x<=n;x++)

{

for(int i=last[x];i;i=e[i].next)

if(bl[x]!=bl[e[i].to]&&!mark[bl[e[i].to]])

mark[bl[e[i].to]]=1,insert2(bl[x],bl[e[i].to]);

for(int i=last[x];i;i=e[i].next)

if(bl[x]!=bl[e[i].to])

mark[bl[e[i].to]]=0;

}

bool jud(int x)

{

if(d[x]!=0||num[x]!=1)return 0;

for(int i=last2[x];i;i=ed[i].next)

if(d[ed[i].to]==1)return 0;

return 1;

}

int main()

{

n=read();m=read();

for(int i=1;i<=m;i++)

{

int u=read(),v=read();

insert(u,v);

}

for(int i=1;i<=n;i++)

if(!dfn[i])tarjan(i);

rebuild();

for(int i=1;i<=scc;i++)

if(!d[i])ans++;

for(int i=1;i<=scc;i++)

if(jud(i))

{

ans--;break;

}

printf("%.6lf",(double)(n-ans)/n);

return 0;

}

hzwer.com _ Home | http://hzwer.com

Description

Input

Output

Sample Input

Sample Output

HINT

题解

分类目录

热门文章

Myfriends

近期评论