poj2240 Floyd

雨点打透心脏的1/2处 2021-11-29 17:38 263阅读 0赞

这题也是求正权回路的，但和之前那题用Bellman-ford的不一样，因为这个是不知道源点的。所以用Floyd可以求出所有节点的最短路径，然后判断a\[i\]\[i\]是否大于1即可。反之，如果知道了确定的源节点，那么我们用Bellman-ford的话会更方便。具体他们的区别，[请看这里][Link 1]。

![2012042421145448.png][]

//Floyd
    #include <iostream>
    #include <fstream>
    #include <map>
    #include <string>
    
    using namespace std;
    #define LEN 35
    #define INF 10000
    
    double a[LEN][LEN],rate;
    int n,m;
    map<string,int>name;
    
    void Floyd()
    {
        int k,i,j;
        for(k=1; k<=n; k++)
        {
            for(i=1; i<=n; i++)
            {
                for(j=1; j<=n; j++)
                {
                    if(a[i][j]<a[i][k]*a[k][j])
                        a[i][j]=a[i][k]*a[k][j];
                }
            }
        }
    }
    
    int main()
    {
        int i,k=1;
        char str[50],str1[50],str2[50];
        freopen("acm.txt","r",stdin);
      while( scanf("%d",&n)!=EOF && n)
      {    
        memset(a,1,sizeof(a));
        for(i=1; i<=n; i++)
        {
            cin>>str;
            name[str]=i;
        //    a[i][i]=1;
        }
        scanf("%d",&m);
        for(i=1; i<=m; i++)
        {
            cin>>str1>>rate>>str2;
            int m,n;
            a[name[str1]][name[str2]]=rate;
        }
        Floyd();
        for(i=1; i<=n; i++)
        {
            if( a[i][i]>1 )
            {
                printf("Case %d: Yes\n",k);
                break;
            }
        }
        if(i>n)
            printf("Case %d: No\n",k);
        k++;
      }
        return 0;
    }

转载于:https://www.cnblogs.com/Jason-Damon/archive/2012/04/24/2468885.html

[Link 1]: http://www.cnblogs.com/mengxm-lincf/archive/2012/02/11/2346288.html
[2012042421145448.png]: /images/20211129/73c3812711a64b44b6d7add40a9eeb63.png