POJ 3259 虫洞（Bellman-Ford判断有无负环的问题）
描述：
在探索他的许多农场时，Farmer John发现了许多令人惊叹的虫洞。虫洞是非常奇特的，因为它是一条单向路径，在您进入虫洞之前的某个时间将您带到目的地！每个FJ的农场包括Ñ（1≤ ñ ≤500）字段方便地编号为1 .. Ñ，中号（1≤ 中号 ≤2500）的路径，和w ^（1≤ w ^ ≤200）虫洞。
由于FJ是*的时间旅行爱好者，他想要做以下事情：从一些场地开始，穿过一些路径和虫洞，并在他最初离开前的一段时间返回起跑场。也许他将能够见到自己:)。
为了帮助FJ找出这是否可行与否，他将与完整的地图供你˚F（1≤ ˚F他的农场≤5）。没有路径需要超过10,000秒的旅行时间，没有虫洞可以使FJ及时返回超过10,000秒。
输入：
第1行：单个整数，F。F农场描述如下。
每个农场的第1行：分别为三个以空格分隔的整数：N，M和W
第2行。每个农场的M + 1：三个以空格分隔的数字（S，E，T）分别描述：双向路径在S和E之间需要T秒来遍历。两个字段可能通过多个路径连接。
线中号 2 .. 中号 + w ^每个场的1：三个空间分隔的数字（S，E，T）分别描述：从S到E的单向路径，也将旅行者移回T秒。
每个农场的第1行：分别为三个以空格分隔的整数：N，M和W
第2行。每个农场的M + 1：三个以空格分隔的数字（S，E，T）分别描述：双向路径在S和E之间需要T秒来遍历。两个字段可能通过多个路径连接。
线中号 2 .. 中号 + w ^每个场的1：三个空间分隔的数字（S，E，T）分别描述：从S到E的单向路径，也将旅行者移回T秒。
输出：
第1行...... F：对于每个农场，如果FJ可以达到目标，则输出“YES”，否则输出“NO”（不包括引号）。
//这是一道判断有无负环的题目，主要是为了熟悉bellman-Ford算法，写法也是采用模板题的写法
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std; int f,n,m,w,all_e;
int dis[];
struct node{
int s;
int e;
int t;
} edge[]; bool bellman_ford()
{
bool flag; for(int i=; i<n-; i++)
{
flag=false;
for(int j=; j<all_e; j++)
if(dis[edge[j].e] > dis[edge[j].s] + edge[j].t)
{
dis[edge[j].e] = dis[edge[j].s] + edge[j].t ;
flag=true;
} if(!flag)
break;
} for(int j=; j<all_e; j++)
if(dis[edge[j].e] > dis[edge[j].s] + edge[j].t)
return true; return false;
} int main ()
{
cin>>f;
while(f--)
{
memset(dis, 0x3f, sizeof(dis));
cin>>n>>m>>w;
all_e=;
int u,v,c;
for(int i=; i<m; i++)
{
cin>>u>>v>>c;
edge[all_e].s=edge[all_e+].e=u;
edge[all_e].e=edge[all_e+].s=v;
edge[all_e].t=edge[all_e+].t=c;
all_e=all_e+;
} for(int i=; i<w; i++)
{
cin>>u>>v>>c;
edge[all_e].s=u;
edge[all_e].e=v;
edge[all_e].t=-c;
all_e++;
} if(bellman_ford())
cout<<"YES"<<endl;
else
cout<<"NO"<<endl; }
return ;
}
POJ 1860 兑换货币（判断有无正环）
描述
我们城市有几个货币兑换点在运作。假设每个点专门处理两种特定的货币，并且只对这些货币执行兑换操作。可以有几个点专门针对同一种货币。每个点都有自己的汇率，A到B的汇率是1A的B的数量。另外，每个兑换点都有一定的佣金，你必须为你的兑换业务支付的金额。佣金总是以货币量收取。
例如，如果你想在兑换点将100美元兑换成俄罗斯卢布，汇率为29.75，佣金为0.39，你将得到(100-0.39)*29.75=2963.3975RUR。
你当然知道，在我们的城市里，你可以对付N种不同的货币。让我们为每种货币分配从1到N的唯一整数。然后，每个交换点可以用6个数字来描述：整数A和B-它交换的货币数和实R。AB型、CAB型，R巴和C巴-交换A至B和B至A时的汇率和佣金。
尼克有一些货币S，他想知道他是否可以某种方式，在一些外汇操作后，增加他的资本。当然，他最终想把钱换成S货币。帮助他回答这个难题。尼克在做手术的时候总要有一笔非负的钱。
例如，如果你想在兑换点将100美元兑换成俄罗斯卢布，汇率为29.75，佣金为0.39，你将得到(100-0.39)*29.75=2963.3975RUR。
你当然知道，在我们的城市里，你可以对付N种不同的货币。让我们为每种货币分配从1到N的唯一整数。然后，每个交换点可以用6个数字来描述：整数A和B-它交换的货币数和实R。AB型、CAB型，R巴和C巴-交换A至B和B至A时的汇率和佣金。
尼克有一些货币S，他想知道他是否可以某种方式，在一些外汇操作后，增加他的资本。当然，他最终想把钱换成S货币。帮助他回答这个难题。尼克在做手术的时候总要有一笔非负的钱。
输入
输入的第一行包含四个数字：n-货币数量，M-外汇点数，S-货币尼克的数量，V-他拥有的货币单位的数量。以下M行按上述顺序分别包含6个数字-对应的交换点的描述。数字由一个或多个空格分隔。1<=S<=N<=100，1<=M<=100，V为实数，0<=V<=103.
每一点的汇率和佣金是真实的，小数点之后最多有两位数，即10。-2<=rate<=102，0<=佣金<=102.
如果在这个序列中没有不止一次使用交换点，那么让我们简单地调用交换操作的某些序列。您可以假设，在任何简单的交换操作序列的末尾和开始处的数字值的比率将小于10。4.
每一点的汇率和佣金是真实的，小数点之后最多有两位数，即10。-2<=rate<=102，0<=佣金<=102.
如果在这个序列中没有不止一次使用交换点，那么让我们简单地调用交换操作的某些序列。您可以假设，在任何简单的交换操作序列的末尾和开始处的数字值的比率将小于10。4.
输出量
如果尼克能增加他的财富，产出是肯定的，在其他情况下输出不输出文件。
样本输入
3 2 1 20.0
1 2 1.00 1.00 1.00 1.00
2 3 1.10 1.00 1.10 1.00
样本输出
YES
//该题刚刚写的时候，不知道怎么处理这些数据，把这些数据看成图，其实本质都是一样的，只不给边赋予了性质，处理好这些数据又是一道模板题
#include <iostream>
#include <cstring>
using namespace std; int g1[][]={},g2[][]={};
double dis[]={};
int n,m,s;
double v; struct node{
int a,b;
double ha,hb;
double ya,yb;
}edge[]; bool bellman_ford()
{
bool flag=false; for(int i=; i<n-; i++)
{
flag=false;
for(int j=; j<*m; j++)
{
if((dis[edge[j].a]-edge[j].ya)*edge[j].ha>dis[edge[j].b])
{
dis[edge[j].b]=(dis[edge[j].a]-edge[j].ya)*edge[j].ha;
flag=true;
}
}
if(!flag)
break;
} for(int j=; j<*m; j++)
{
if((dis[edge[j].a]-edge[j].ya)*edge[j].ha>dis[edge[j].b])
{
dis[edge[j].b]=(dis[edge[j].a]-edge[j].ya)*edge[j].ha;
return true;
}
}
return false; } int main()
{
cin>>n>>m>>s>>v;
dis[s]=v;
for(int i=; i<*m; i=i+)
{
cin>>edge[i].a>>edge[i].b>>edge[i].ha>>edge[i].ya>>edge[i].hb>>edge[i].yb;
edge[i+].b=edge[i].a, edge[i+].a=edge[i].b;
edge[i+].ha=edge[i].hb, edge[i+].hb=edge[i].ha;
edge[i+].ya=edge[i].yb, edge[i+].yb=edge[i].ya;
} if(bellman_ford())
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
return ;
}