同楼下,
AddEdge(x,y,-z);
得出的结果是0,0,5,4,1
之前貌似也看到过关于“差分约束尽量不要建边权为相反数的反向边”之类的讨论,说是会玄学WA,十分迷惑
代码如下(AC)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int N=10086;
#define reint register int
int n,m,num,head[N],dis[N],tot[N];
bool in[N],flag;
queue<int>q;
struct Edge{
int to;
int next;
int val;
}edge[N];
inline void AddEdge(int x,int y,int z)
{
edge[++num].to=y;
edge[num].next=head[x];
edge[num].val=z;
head[x]=num;
}
inline void SPFA(int u)
{
dis[u]=0;q.push(u);in[u]=true;
while(!q.empty())
{
int fro=q.front();q.pop();in[fro]=false;
if((++tot[fro])==n){flag=true;return;}
for(reint i=head[fro];i;i=edge[i].next)
{
int to=edge[i].to;
if(dis[to]<dis[fro]+edge[i].val)
{
dis[to]=dis[fro]+edge[i].val;
if(!in[to])
{
q.push(to);
in[to]=true;
}
}
}
}
}
inline void starts()
{
memset(head,0,sizeof(head));
memset(dis,-1,sizeof(dis));
memset(tot,0,sizeof(tot));
memset(in,false,sizeof(in));
}
int main()
{
std::ios::sync_with_stdio(false);
cin>>n>>m;
starts();
for(reint i=1;i<=m;++i)
{
int x,y,z;
cin>>x>>y>>z;
if(x==y)
{
cout<<"NO SOLUTION\n";
return 0;
}
AddEdge(x,y,-z);
}
for(reint i=1;i<=n;++i)AddEdge(0,i,0);
SPFA(0);
if(flag)
{
cout<<"NO SOLUTION\n";
return 0;
}
for(reint i=1;i<=n;++i)cout<<dis[i]<<'\n';
return 0;
}
有奆佬知道是为什么吗???