POJ 1860 Currency Exchange + 2240 Arbitrage + 3259 Wormholes 解题报告
三道题都是考察最短路算法的判环。其中1860和2240判断正环，3259判断负环。难度都不大，可以使用Bellman-ford算法，或者SPFA算法。也有用弗洛伊德算法的，笔者还不会SF-_-……
直接贴代码。
1860 Currency Exchange:
#include <cstdio>
#include <cstring>
int N,M,S;
double V;
const int maxn=101;
int first,vv,nxt;
double ww,cc;
double d;
int count;
int stack;
bool vis;
bool SPFA()
{
for(int i=1;i<=N;i++)
vis=count=d=0;
int top=0;
stack[++top]=S;
d=V;
vis=true;
count++;
while(top)
{
int a=stack;
vis=false;
for(int e=first;e;e=nxt)
{
if(d]<(d-cc)*ww)
{
d]=(d-cc)*ww;
if(!vis])
{
stack[++top]=vv;
count]++;
if(count]>=N)
return false;
vis]=true;
}
}
}
}
return true;
}
int main()
{
//freopen("in.txt","r",stdin);
int e=2;
scanf("%d%d%d%lf",&N,&M,&S,&V);
for(int i=1;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=first,vv=v,ww=w1,cc=c1,first=e++;
nxt=first,vv=u,ww=w2,cc=c2,first=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=31;
map<string,int> mp;
int first,vv,nxt;
double ww;
int stack;
double d;
int count;
bool vis;
int n;
int SPFA(int sta)
{
int top=0;
stack[++top]=sta;
memset(vis,0,sizeof(vis));
memset(d,0,sizeof(d));
memset(count,0,sizeof(count));
count++;
d=1;
while(top)
{
int a=stack;
vis=false;
for(int e=first;e;e=nxt) if(d]<d*ww)
{
d]=d*ww;
if(!vis])
{
stack[++top]=vv;
count]++;
if(count]>=n)
return false;
vis]=true;
}
}
}
return true;
}
int main()
{
//freopen("in.txt","r",stdin);
int cas=1;
string str,str2;
while(scanf("%d",&n) && n)
{
mp.clear();
for(int i=1;i<=n;i++)
{
cin>>str;
mp=i;
}
memset(first,0,sizeof(first));
int e=2;
int m;
scanf("%d",&m);
while(m--)
{
cin>>str>>ww>>str2;
int u=mp;
int v=mp;
nxt=first,vv=v,first=e++;
}
bool flag=false;
for(int i=1;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<=d+w) return false;
d=d+w;
return true;
}
bool bellman_ford(int n)
{
memset(d,0,sizeof(d));
bool flag;
for(int i=1;i<=n;i++)
{
flag=true;
for(int u=1;u<=n;u++)
for(int e=first;e;e=nxt)
if(relax(u,vv,ww))
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=2;
int u,v,w;
memset(first,0,sizeof(first));
for(int i=0;i<M;i++)
{
scanf("%d%d%d",&u,&v,&w);
nxt=first,vv=v,ww=w,first=e++;
nxt=first,vv=u,ww=w,first=e++;
}
for(int i=0;i<W;i++)
{
scanf("%d%d%d",&u,&v,&w);
nxt=first,vv=v,ww=-w,first=e++;
}
if(bellman_ford(N))
printf("NO\n");
else
printf("YES\n");
}
}
页:
[1]