HDOJ 1217 【Floyd】Arbitrage

【题目描述】

http://acm.hdu.edu.cn/showproblem.php?pid=1217

###【思路】
就是求最长路，因为起点和终点无数并且数据很小，所以用floyd也可以。
因为是倍数关系，所以当两个点不通时，边值就初始化为0，因为任何数乘以0都等于0嘛。
松弛操作完毕后，点i到自身的值即dis[i][i]若是大于1，就说明可以盈利啦。

P.S.1：此题为单向边，我之前建成了双向的orz
P.S.2：原来cin是不会读入回车和空格的，但是会吃掉它。就是说不用像scanf那样读入一个int的m后还得用getchar()吃掉一个回车符号，这里我调了半天才发现，果然还是语言基础太差啊，老是错在细节上面。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
string Name[100];
double dis[110][110];
int main()
{
      int n,m,x,y,Case,flag;
      double num;
      char ch;
      string s1,s2;
      Case=0;
      while (cin>>n && n)
      {
            Case++;
            for (int i=1;i<=n;i++) cin>>Name[i];
            for (int i=1;i<=n;i++)
                  for (int j=1;j<=n;j++) dis[i][j]=0;
            cin>>m;;
            for (int i=1;i<=m;i++)
            {
                  x=y=0;
                  cin>>s1>>num>>s2;
                  for (int j=1;j<=n;j++)
                  {
                        if (Name[j]==s1) x=j;
                        if (Name[j]==s2) y=j;
                        if (x && y) break;
                  }
                  dis[x][y]=num;
            }
            for (int k=1;k<=n;k++)
                  for (int i=1;i<=n;i++)
                        for (int j=1;j<=n;j++)
                        {
                              dis[i][j]=max(dis[i][j],dis[i][k]*dis[k][j]);
                        }
            flag=0;
            for (int i=1;i<=n;i++)
                  if (dis[i][i]>1)
                  {
                        flag=1;
                        break;
                  }
            cout<<"Case "<<Case<<": ";
            if (flag) cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
      }
      return 0;
}
文章目录
  1. 1. 【题目描述】
|