好贷网好贷款

BZOJ 2438([中山市选2011]杀人游戏-有向图Tarjen缩点-到点为止)

发布时间:2016-12-5 4:31:24 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"BZOJ 2438([中山市选2011]杀人游戏-有向图Tarjen缩点-到点为止)",主要涉及到BZOJ 2438([中山市选2011]杀人游戏-有向图Tarjen缩点-到点为止)方面的内容,对于BZOJ 2438([中山市选2011]杀人游戏-有向图Tarjen缩点-到点为止)感兴趣的同学可以参考一下。

2438: [中山市选2011]杀人游戏 Time Limit: 10 Sec  Memory Limit: 128 MB Submit: 446  Solved: 152 [Submit][Status] Description 一位冷血的杀手潜入 Na-wiat,并假装成平民。警察希望能在 N 个人里面, 查出谁是杀手。  警察能够对每一个人进行查证,假如查证的对象是平民,他会告诉警察,他 认识的人, 谁是杀手, 谁是平民。 假如查证的对象是杀手, 杀手将会把警察干掉。  现在警察掌握了每一个人认识谁。  每一个人都有可能是杀手,可看作他们是杀手的概率是相同的。  问:根据最优的情况,保证警察自身安全并知道谁是杀手的概率最大是多 少? Input 第一行有两个整数 N,M。  接下来有 M 行,每行两个整数 x,y,表示 x 认识 y(y 不一定认识 x,例如胡锦涛同志) 。 Output 仅包含一行一个实数,保留小数点后面 6 位,表示最大概率。 Sample Input 5 4 1 2 1 3 1 4 1 5 Sample Output 0.800000 HINT 警察只需要查证 1。假如1是杀手,警察就会被杀。假如 1不是杀手,他会告诉警 察 2,3,4,5 谁是杀手。而 1 是杀手的概率是 0.2,所以能知道谁是杀手但没被杀的概 率是0.8。 对于 100%的数据有 1≤N ≤  10 0000,0≤M ≤  30 0000 Source 有向图的Tarjen缩点。。。到点为止。。。 详情看代码。。。由于是有向图,可能有返非祖边(到其它子树),要注意特判、、、 #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<functional> #include<iostream> #include<cmath> #include<cctype> #include<ctime> using namespace std; #define For(i,n) for(int i=1;i<=n;i++) #define Fork(i,k,n) for(int i=k;i<=n;i++) #define Rep(i,n) for(int i=0;i<n;i++) #define ForD(i,n) for(int i=n;i;i--) #define RepD(i,n) for(int i=n;i>=0;i--) #define Forp(x) for(int p=pre[x];p;p=next[p]) #define Lson (x<<1) #define Rson ((x<<1)+1) #define MEM(a) memset(a,0,sizeof(a)); #define MEMI(a) memset(a,127,sizeof(a)); #define MEMi(a) memset(a,128,sizeof(a)); #define INF (2139062143) #define F (100000007) #define MAXN (600000+10) #define MAXM (600000+10) long long mul(long long a,long long b){return (a*b)%F;} long long add(long long a,long long b){return (a+b)%F;} long long sub(long long a,long long b){return (a-b+(a-b)/F*F+F)%F;} typedef long long ll; int n,m,edge[MAXM],next[MAXM]={0},pre[MAXN]={0},size=0; void addedge(int u,int v) { edge[++size]=v; next[size]=pre[u]; pre[u]=size; } //void addedge2(int u,int v){addedge(u,v),addedge(v,u); } bool b[MAXN]={0}; int dfs[MAXN],dis[MAXN]={0},s[MAXN]={0},tot=0,numk[MAXN]={0},h[MAXN]={0},kind=0,tim=0; void tar(int x,int fa) { dis[x]=dfs[x]=++tim;b[x]=1;s[++tot]=x; Forp(x) { int v=edge[p]; if (!b[v]) tar(v,x),dfs[x]=min(dfs[x],dfs[v]); else if (!h[v]) dfs[x]=min(dfs[x],dis[v]); } if (dfs[x]==dis[x]) { ++kind; while (tot) { numk[h[s[tot]]=kind]++; if (s[tot--]==x) break; } } } int indegree[MAXN]={0}; int main() { // freopen("bzoj2438.in","r",stdin); // freopen(".out","w",stdout); scanf("%d%d",&n,&m); For(i,m) { int u,v; scanf("%d%d",&u,&v); addedge(u,v); } For(i,n) if (!b[i]) tar(i,0); For(x,n) Forp(x) { int v=edge[p]; if (h[x]^h[v]) indegree[h[v]]++; } int ans=0,s1=0; //s1表示分量内大小为1的单独块 For(i,kind) if (!indegree[i]) {ans++;if (numk[i]==1) s1=1;} if (ans>1) ans-=s1; printf("%.6lf\n",1.000000-(double)ans/n); // For(i,kind) cout<<numk[i]<<' '; return 0; }

上一篇:Java教程-JavaEE的重要性和学习导航
下一篇:互联网产品设计的核心要素

相关文章

相关评论