?

這個題開始正向拓撲排序，然后各種wa，心灰意冷，找了個題解，和同學(xué)研究了半天，甚至曾經(jīng)一度認為題解是錯的。

這個題正向反向應(yīng)該都無所謂，但是我實在是蒻，打了半天正向都沒打過去，最后跟隨dalao的步伐走向了反向拓撲

#include<iostream> #include<cstring> #include<cstdio> #include<queue> #include<stack> using namespace std; int n,m,x,y,z,head[100010],tail,ru[100010],chu[100010]; bool flag[100010]; double ans[100010]; queue<int>qwq; struct in {int to,ne,co; }ter[200020]; inline void build(int f,int l,int c) {ter[++tail]=(in){l,head[f],c},head[f]=tail; } int main() {memset(head,-1,sizeof(head));scanf("%d%d",&n,&m);for(int i=1;i<=m;i++)scanf("%d%d%d",&x,&y,&z),build(y,x,z),ru[x]++,chu[x]++;//反向建圖，因為從1跑不到的點肯定反向建圖也跑不到1 for(int i=1;i<=n;i++)if(!ru[i])//如果原圖該點，沒有出邊(終點) qwq.push(i);while(!qwq.empty()){int qaq=qwq.front();qwq.pop();//這里可以換成棧，跑的還更快，雖然我不知道為啥 for(int i=head[qaq];i>0;i=ter[i].ne){int t=ter[i].to;double gai=1.0/chu[t];ans[t]+=(ans[qaq]+ter[i].co)*gai;//求期望的必要步驟嘛qwq ru[t]--;if(!ru[t])qwq.push(t);} }for(int i=1;i<=n;i++)printf("%.2lf ",ans[i]);//printf("%.2lf",ans[1]); } /*關(guān)于這個反向拓撲排序可以的原因 因為每一個點都可以到達終點，所以無論正向反向，所有的從1到n的路徑的期望值都不會變 所以正向反向無所謂 為什么要用拓撲排序 因為只有一個點所有到他的邊都被走過，關(guān)于到它的期望值才算真正確定 */ #include<iostream> #include<cstring> #include<cstdio> #include<queue> #include<stack> using namespace std; int n,m,x,y,z,head[100010],tail,ru[100010],chu[100010]; bool flag[100010]; double ans[100010]; queue<int>qwq; struct in {int to,ne,co; }ter[200020]; inline void build(int f,int l,int c) {ter[++tail]=(in){l,head[f],c},head[f]=tail; } int main() {memset(head,-1,sizeof(head));scanf("%d%d",&n,&m);for(int i=1;i<=m;i++)scanf("%d%d%d",&x,&y,&z),build(y,x,z),ru[x]++,chu[x]++;//反向建圖，因為從1跑不到的點肯定反向建圖也跑不到1 for(int i=1;i<=n;i++)if(!ru[i])//如果原圖該點，沒有出邊(終點) qwq.push(i);while(!qwq.empty()){int qaq=qwq.front();qwq.pop();//這里可以換成棧，跑的還更快，雖然我不知道為啥 for(int i=head[qaq];i>0;i=ter[i].ne){int t=ter[i].to;double gai=1.0/chu[t];ans[t]+=(ans[qaq]+ter[i].co)*gai;//求期望的必要步驟嘛qwq ru[t]--;if(!ru[t])qwq.push(t);} }for(int i=1;i<=n;i++)printf("%.2lf ",ans[i]);//printf("%.2lf",ans[1]); } /*關(guān)于這個反向拓撲排序可以的原因 因為每一個點都可以到達終點，所以無論正向反向，所有的從1到n的路徑的期望值都不會變 所以正向反向無所謂 為什么要用拓撲排序 因為只有一個點所有到他的邊都被走過，關(guān)于到它的期望值才算真正確定 */ #include<iostream> #include<cstring> #include<cstdio> #include<queue> #include<stack> using namespace std; int n,m,x,y,z,head[100010],tail,ru[100010],chu[100010]; bool flag[100010]; double ans[100010]; queue<int>qwq; struct in {int to,ne,co; }ter[200020]; inline void build(int f,int l,int c) {ter[++tail]=(in){l,head[f],c},head[f]=tail; } int main() {memset(head,-1,sizeof(head));scanf("%d%d",&n,&m);for(int i=1;i<=m;i++)scanf("%d%d%d",&x,&y,&z),build(y,x,z),ru[x]++,chu[x]++;//反向建圖，因為從1跑不到的點肯定反向建圖也跑不到1 for(int i=1;i<=n;i++)if(!ru[i])//如果原圖該點，沒有出邊(終點) qwq.push(i);while(!qwq.empty()){int qaq=qwq.front();qwq.pop();//這里可以換成棧，跑的還更快，雖然我不知道為啥 for(int i=head[qaq];i>0;i=ter[i].ne){int t=ter[i].to;double gai=1.0/chu[t];ans[t]+=(ans[qaq]+ter[i].co)*gai;//求期望的必要步驟嘛qwq ru[t]--;if(!ru[t])qwq.push(t);} }for(int i=1;i<=n;i++)printf("%.2lf ",ans[i]);//printf("%.2lf",ans[1]); } /*關(guān)于這個反向拓撲排序可以的原因 因為每一個點都可以到達終點，所以無論正向反向，所有的從1到n的路徑的期望值都不會變 所以正向反向無所謂 為什么要用拓撲排序 因為只有一個點所有到他的邊都被走過，關(guān)于到它的期望值才算真正確定 */

?

轉(zhuǎn)載于:https://www.cnblogs.com/Loi-dfkdsmbd/articles/7706082.html

總結(jié)

以上是生活随笔為你收集整理的【codevs2488】绿豆蛙的归宿的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。