POJ2472（最长路）图论

POJ2472
题意：求从1到n不被逮捕的概率最大
题解：

Dijkstra算法不能直接求最长路。按照Dijkstra求下面的从1到2的最长路，会发生错误。必须取反再求。1—2 2，1—3 1，3—4 1，4—2 1。（空格后面是边权）
但是这一题可以用Dijkstra求最大值(47ms)。因为概率≤1，所以越乘越小。比如现在到b点的概率p1为最大，就做标记。那么从其它点跑到b的概率一定小于p1。这和加法不同。
也可以用floyd的方法(94ms)

代码：（Dijkstra）

#include #include #include #include using namespace std; int const N = 100 + 10; int const M = 10000 + 10; double d[N][N],dis[N]; int vis[N],n,m; void Dijkstra(){ for(int i=1; i<=n; i++) dis[i] = 0,vis[i] = false; dis[1] = 1; for(int i=1; i MAX) MAX = dis[j], u = j; vis[u] = true; for(int j=1; j<=n; j++) if(!vis[j] && dis[u] * d[u][j] > dis[j]) dis[j] = dis[u] * d[u][j]; } } int main(){ while(~scanf("%d",&n)&&n){ scanf("%d",&m); memset(d,0,sizeof(d)); //没有边逃跑的概率为0 for(int i=1; i<=m; i++){ int x,y,p; scanf("%d%d%d",&x,&y,&p); //至多一条路 d[x][y] = d[y][x] = p/100.0; //必须除100，转化为≤1 } Dijkstra(); printf("%.6f percent\n",dis[n]*100); } }

Floyd代码：

#include #include #include #include using namespace std; int const N = 100 + 10; int const M = 10000 + 10; double d[N][N]; int n,m; void Floyd(){ for(int k=1; k<=n; k++){ for(int i=1; i<=n; i++){ for(int j=1; j<=n; j++) d[i][j] = max(d[i][j],d[i][k]*d[k][j]); } } } int main(){ while(~scanf("%d",&n)&&n){ scanf("%d",&m); memset(d,0,sizeof(d)); //没有边逃跑的概率为0 for(int i=1; i<=m; i++){ int x,y,p; scanf("%d%d%d",&x,&y,&p); //至多一条路 d[x][y] = d[y][x] = p/100.0; //必须除100，转化为≤1 } Floyd(); printf("%.6f percent\n",d[1][n]*100); } }

【POJ2472（最长路）】