三道题都是考察最短路算法的判环。其中1860和2240判断正环，3259判断负环。
难度都不大，可以使用Bellman-ford算法，或者SPFA算法。也有用弗洛伊德算法的，笔者还不会SF-_-……
直接贴代码。
1860 Currency Exchange:
#include <cstdio>
#include <cstring> int N,M,S;
double V;
const int maxn=;
int first[maxn],vv[maxn*maxn],nxt[maxn*maxn];
double ww[maxn*maxn],cc[maxn*maxn];
double d[maxn];
int count[maxn];
int stack[maxn];
bool vis[maxn]; bool SPFA()
{
for(int i=;i<=N;i++)
vis[i]=count[i]=d[i]=;
int top=;
stack[++top]=S;
d[S]=V;
vis[S]=true;
count[S]++; while(top)
{
int a=stack[top--];
vis[a]=false; for(int e=first[a];e;e=nxt[e])
{
if(d[vv[e]]<(d[a]-cc[e])*ww[e])
{
d[vv[e]]=(d[a]-cc[e])*ww[e];
if(!vis[vv[e]])
{
stack[++top]=vv[e];
count[vv[e]]++;
if(count[vv[e]]>=N)
return false;
vis[vv[e]]=true;
}
}
}
}
return true;
} int main()
{
// freopen("in.txt","r",stdin);
int e=;
scanf("%d%d%d%lf",&N,&M,&S,&V);
for(int i=;i<=M;i++)
{
int u,v;
double w1,c1,w2,c2;
scanf("%d%d%lf%lf%lf%lf",&u,&v,&w1,&c1,&w2,&c2);
nxt[e]=first[u],vv[e]=v,ww[e]=w1,cc[e]=c1,first[u]=e++;
nxt[e]=first[v],vv[e]=u,ww[e]=w2,cc[e]=c2,first[v]=e++;
}
printf(SPFA()?"NO\n":"YES\n");
}
2240 Arbitrage: 起点不确定，需要枚举。map方便一点，hash……应该快一点
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
#include <map>
#include <string> const int maxn=;
map<string,int> mp;
int first[maxn],vv[maxn*maxn],nxt[maxn*maxn];
double ww[maxn*maxn];
int stack[maxn];
double d[maxn];
int count[maxn];
bool vis[maxn];
int n; int SPFA(int sta)
{
int top=;
stack[++top]=sta;
memset(vis,,sizeof(vis));
memset(d,,sizeof(d));
memset(count,,sizeof(count));
count[sta]++;
d[sta]=; while(top)
{
int a=stack[top--];
vis[a]=false; for(int e=first[a];e;e=nxt[e]) if(d[vv[e]]<d[a]*ww[e])
{
d[vv[e]]=d[a]*ww[e];
if(!vis[vv[e]])
{
stack[++top]=vv[e];
count[vv[e]]++;
if(count[vv[e]]>=n)
return false;
vis[vv[e]]=true;
}
}
}
return true;
} int main()
{
// freopen("in.txt","r",stdin);
int cas=;
string str,str2;
while(scanf("%d",&n) && n)
{
mp.clear();
for(int i=;i<=n;i++)
{
cin>>str;
mp[str]=i;
} memset(first,,sizeof(first)); int e=;
int m;
scanf("%d",&m);
while(m--)
{
cin>>str>>ww[e]>>str2;
int u=mp[str];
int v=mp[str2];
nxt[e]=first[u],vv[e]=v,first[u]=e++;
} bool flag=false;
for(int i=;i<=n;i++) if(!SPFA(i))
flag=true;
printf("Case %d: ",cas++);
printf(flag?"Yes\n":"No\n");
}
}
3259 Wormholes:
#include <cstdio>
#include <cstring> int first[],vv[],ww[],nxt[];
int d[]; bool relax(int u,int v,int w)
{
if(d[v]<=d[u]+w) return false;
d[v]=d[u]+w;
return true;
} bool bellman_ford(int n)
{
memset(d,,sizeof(d)); bool flag;
for(int i=;i<=n;i++)
{
flag=true;
for(int u=;u<=n;u++)
for(int e=first[u];e;e=nxt[e])
if(relax(u,vv[e],ww[e]))
flag=false;
if(flag)
return true;
else if(i==n)
return false;
}
return true;
} int main()
{
// freopen("in.txt","r",stdin);
int T;
scanf("%d",&T); while(T--)
{
int N,M,W;
scanf("%d%d%d",&N,&M,&W);
int e=;
int u,v,w; memset(first,,sizeof(first));
for(int i=;i<M;i++)
{
scanf("%d%d%d",&u,&v,&w);
nxt[e]=first[u],vv[e]=v,ww[e]=w,first[u]=e++;
nxt[e]=first[v],vv[e]=u,ww[e]=w,first[v]=e++;
}
for(int i=;i<W;i++)
{
scanf("%d%d%d",&u,&v,&w);
nxt[e]=first[u],vv[e]=v,ww[e]=-w,first[u]=e++;
} if(bellman_ford(N))
printf("NO\n");
else
printf("YES\n");
}
}