狡猾的商人（多么社会的题目名）,听周*涛说是水题
看了一眼题目,确让过眼神,我遇上对的题,这题是一道用差分约束系统来判断是否存在环的情况
P3385[模板]负环：我不要面子的？？？
题目所给条件是a时间到b时间之内赚的钱数
a-b==c
所以建立关系
b->a的权值为c
a->b的权值为-c
因为可能出现负环也可能出现正环
再跑spfa判断是否成环
这题找最长路找最短路都可以，因为这无关紧要，只需要判断是否存在环
拙劣の代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn=10000;
struct lk
{
int up;
int zd;
int vis;
}w[maxn*2];
int h[maxn],top,bj[maxn],n,ans[maxn],bns[maxn],flag;
void pop(int next,int end,int viss)
{
w[++top].up=h[next];
w[top].zd=end;
w[top].vis=viss;
h[next]=top;
}
queue<int>mp;
void spfa(int l)
{
memset(bj,0,sizeof(bj));
memset(ans,-127,sizeof(ans));
ans[l]=0;
bj[l]=1;
mp.push(l);
while(!mp.empty())
{
//cout<<"1"<<endl;
int x=mp.front();
bj[x]=0;
mp.pop();
for(int i=h[x];i!=0;i=w[i].up)
{
int v=w[i].zd;
if(ans[x]+w[i].vis>ans[v])
{
ans[v]=ans[x]+w[i].vis;
bns[v]=bns[x]+1;
if(bns[v]>n)
{
flag=1;
return ;
}
if(bj[v]==0)
{
bj[v]=1;
mp.push(v);
}
}
}
}
}
int main()
{
int m,k,a,b,viss;
cin>>k;
while(k)
{
top=0;
flag=0;
memset(h,0,sizeof(h));
memset(bns,0,sizeof(bns));
k--;
cin>>n>>m;
for(int i=1;i<=m;i++)
{
cin>>a>>b>>viss;
pop(a-1,b,-viss);
pop(b,a-1,viss);
}
for(int i=1;i<=n;i++)//保证所有点联通而走一遍代替虚拟节点
{
if(!bns[i])
spfa(i);
if(flag==1)
break;
}
if(flag==1)
cout<<"false"<<endl;
else
cout<<"true"<<endl;
}
return 0;
}
这里应该可以也做一个虚拟节点将所有的点链接起来,权值为0