ZOJ 2797 ||POJ 2472 floyd变形

记住一定要初始化dis[][]，因为这边wa了几次。

题意：求起点1到终点n不被抓的概率。也就是要是输出的结果最大。只要把floyd状态方程改为*就行了。如下所示：

dis[i][j]=max(dis[i][j],dis[i][k]*dis[k][j]).

切记初始化dis[i][j]=0;

要求最大则初始化为-INF 或者0.不能是INF

View Code

  1 // I'm the Topcoder
  2 //C
  3 #include <stdio.h>
  4 #include <stdlib.h>
  5 #include <string.h>
  6 #include <ctype.h>
  7 #include <math.h>
  8 #include <time.h>
  9 //C++
 10 #include <iostream>
 11 #include <algorithm>
 12 #include <cstdio>
 13 #include <cstdlib>
 14 #include <cmath>
 15 #include <cstring>
 16 #include <cctype>
 17 #include <stack>
 18 #include <string>
 19 #include <list>
 20 #include <queue>
 21 #include <map>
 22 #include <vector>
 23 #include <deque>
 24 #include <set>
 25 using namespace std;
 26 
 27 //*************************OUTPUT*************************
 28 #ifdef WIN32
 29 #define INT64 "%I64d"
 30 #define UINT64 "%I64u"
 31 #else
 32 #define INT64 "%lld"
 33 #define UINT64 "%llu"
 34 #endif
 35 
 36 //**************************CONSTANT***********************
 37 #define INF 0x3f3f3f3f
 38 #define eps 1e-8
 39 #define PI acos(-1.)
 40 #define PI2 asin (1.);
 41 typedef long long LL;
 42 //typedef __int64 LL;   //codeforces
 43 typedef unsigned int ui;
 44 typedef unsigned long long ui64;
 45 #define MP make_pair
 46 typedef vector<int> VI;
 47 typedef pair<int, int> PII;
 48 #define pb push_back
 49 #define mp make_pair
 50 
 51 //***************************SENTENCE************************
 52 #define CL(a,b) memset (a, b, sizeof (a))
 53 #define sqr(a,b) sqrt ((double)(a)*(a) + (double)(b)*(b))
 54 #define sqr3(a,b,c) sqrt((double)(a)*(a) + (double)(b)*(b) + (double)(c)*(c))
 55 
 56 //****************************FUNCTION************************
 57 template <typename T> double DIS(T va, T vb) { return sqr(va.x - vb.x, va.y - vb.y); }
 58 template <class T> inline T INTEGER_LEN(T v) { int len = 1; while (v /= 10) ++len; return len; }
 59 template <typename T> inline T square(T va, T vb) { return va * va + vb * vb; }
 60 
 61 // aply for the memory of the stack
 62 //#pragma comment (linker, "/STACK:1024000000,1024000000")
 63 //end
 64 
 65 int n,m;
 66 const int maxn = 1000+10;
 67 double dis[maxn][maxn];
 68 int s,e;
 69 double w;
 70 void floyd(){
 71     for(int k=1;k<=n;k++){
 72         for(int i=1;i<=n;i++){
 73             for(int j=1;j<=n;j++){
 74                 dis[i][j]=max(dis[i][j],dis[i][k]*dis[k][j]);
 75             }
 76         }
 77     }
 78 }
 79 
 80 int main(){
 81    // int n,m;
 82     while(scanf("%d",&n)!=EOF){
 83         if(n==0)  break;
 84         scanf("%d",&m);
 85         for(int i=1;i<=n;i++){
 86             for(int j=1;j<=n;j++){
 87                 dis[i][j]=0;
 88             }
 89             dis[i][i]=0;
 90         }
 91         for(int i=1;i<=m;i++){
 92             scanf("%d%d%lf",&s,&e,&w);
 93             dis[s][e]=dis[e][s]=(double)(w/100);
 94             //printf("****%lf\n",dis[s][e]);
 95         }
 96         floyd();
 97 
 98         printf("%.6lf percent\n",dis[1][n]*100);
 99     }
100     return 0;
101 }