题意:
货币转换,看一圈下来有没有货币能够升值。。。
题解:
仍需要floyd来算关系。bellman来看有没有正权值回路并通过此点能够到达v0.
#include<stdio.h>
#include<string.h>
struct point
{
int u,v;
double w;
}eg[1100];
int cas=1,k,pos,n,m,map[50][50];
double dist[50];
char name[50][100];
int change(char s[])
{
for(int i=1;i<pos;i++)
if(!strcmp(name[i],s))
return i;
strcpy(name[pos++],s);
}
int bellman(int v0)
{
for(int i=1;i<=n;i++)
dist[i]=0;
dist[v0]=1;
for(int i=0;i<n-1;i++)
for(int j=0;j<k;j++)
if(dist[eg[j].u]>0&&dist[eg[j].u]*eg[j].w>dist[eg[j].v])
{
dist[eg[j].v]=dist[eg[j].u]*eg[j].w;
if(dist[v0]>1)
return 1;
}
for(int i=0;i<k;i++)
if(dist[eg[i].u]*eg[i].w>dist[eg[i].v])
if(map[eg[i].u][v0])
return 1;
return 0;
}
int main()
{
while(scanf("%d",&n)&&n)
{
memset(map,0,sizeof(map));
k=0;
bool flag=0;
pos=1;
for(int i=0;i<n;i++)
{
char s[100];
scanf("%s",s);
change(s);
}
scanf("%d",&m);
for(int i=0;i<m;i++)
{
char s1[100],s2[100];
scanf("%s%lf%s",s1,&eg[k].w,s2);
int a=change(s1);
int b=change(s2);
map[a][b]=1;
eg[k].u=a;
eg[k++].v=b;
}
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
map[i][j]=map[i][j]||(map[i][k]&&map[k][j]);
for(int i=1;i<=n;i++)
if(map[i][i])
if(bellman(i))
{
printf("Case %d: Yes\n",cas++);
flag=1;
break;
}
if(!flag)
printf("Case %d: No\n",cas++);
}
return 0;
}