首页 > 代码库 > hdu 1217 Arbitrage (spfa算法)

hdu 1217 Arbitrage (spfa算法)

2024-07-17 16:07:20   221人阅读

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1217

题目大意：通过货币的转换，来判断是否获利，如果获利则输出Yes，否则输出No。

这里介绍一个STL中的map容器去处理数据，map<string,int>V,M;

现在我目前的理解是将字符串转换成数字，然后就是根据spfa的模板找最短路了。。哇哈哈( ⊙o⊙ )哇

 1 #include <iostream> 2 #include <cstdio> 3 #include <map> 4 #include <queue> 5 #include <cstring> 6 using namespace std; 7 int n,a; 8 double Map[35][35]; 9 const int INF=9999;10 map<string,int>V;11 12 int spfa()13 {14     queue<int>q;15     double node[35]= {0};16     int inq[35]= {0};17     node[1]=1;18     inq[1]=1;19     q.push(1);20     while (!q.empty())21     {22         int s=q.front();23         q.pop();24         for (int i=1; i<=n; i++)25         {26             //cout<<Map[s][i]<<" "<<node[i]<<endl;27             if (node[i]<Map[s][i]*node[s])28             {29                 //cout<<node[i]<<" "<<Map[s][i]<<endl;30                 node[i]=Map[s][i]*node[s];31                 if (!inq[i])32                 {33                     q.push(i);34                     inq[i]=1;35                 }36                 if (node[1]>1)37                     return 1;38             }39 40         }41         inq[s]=0;42     }43     return 0;44 }45 int main ()46 {47     char ch[35];48     int cmp=1,q;49     while (scanf("%d",&n),n)50     {51         q=0;52         V.clear();53         for (int i=1; i<=n; i++)54             for (int j=1; j<=n; j++)55                 Map[i][j]=0;56         //memset(Map,INF,sizeof(Map));57         for (int i=1; i<=n; i++)58         {59             scanf("%s",ch);60             if (!V[ch])61                 V[ch]=++q;62         }63         scanf("%d",&a);64         for (int i=1; i<=a; i++)65         {66             double money;67             char ch1[35],ch2[35];68             scanf("%s%lf%s",ch1,&money,ch2);69             if (Map[V[ch1]][V[ch2]]<money)70                 Map[V[ch1]][V[ch2]]=money;71             //cout<<Map[V[ch1]][V[ch2]]<<endl;72         }73         printf ("Case %d: ",cmp++);74         if (spfa())75             printf("Yes\n");76         else77             printf ("No\n");78     }79     return 0;80 }
View Code


联系
我们