P4819 中山市選 殺人遊戲 Tarjan

2022-09-22 22:36:48 字數 954 閱讀 4766

有\(n\)個人,他們通過\(m\)條單向的認識關係形成了一張圖,其中有一個人是殺手,若遇到殺手則你會死亡,若遇到平民,ta會告訴你,ta認識的人中每個人的身份,求保證自身安全的情況下查到殺手的概率最大是多少?

範圍&性質:\(1\le n\le 10^5,q\le m\le 3\times 10^5\)

什麼情況下會遇到殺手,那就是查一個不清楚身份的人時(好像是一句廢話)

所以只需要查詢所有入度為0的點就可以了,但本題點數過大,直接\(o(n^2)\)會被卡,那麼我們考慮怎麼優化,我們發現對於一個強聯通分量,裡面的點都是互相認識的,所以我們先縮點,對於入度為0的強連通分量查詢

tips:在實際情況中還可以利用排除法,所以當一個入度為0且大小為1的點,他的所有兒子入度都大於1,那麼意味著這個點可以不用查,因為最後我們可以通過排除法確定他的身份

#includeusing namespace std;

namespace zzc

e[maxn<<2];

void add(int u,int v)

void tarjan(int u)

else if(ins[v]) low[u]=min(low[u],dfn[v]);

} if(low[u]==dfn[u])

while(st[top--]!=u);

} }void work()

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

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

}pre[belong[u]]++;

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

}if(!ok) flag=true;}}

}} if(flag) ans--;

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

} int main()

洛谷 P4819 中山市選 殺人遊戲

洛谷 題目就是讓我們在dag中找到一些點,覆蓋所有點。 因為是dag,可以想到tarjan縮一下點。假設我們需要找x個點,那麼答案就是 n...