自动搬运

查看原文

来自洛谷，原作者为

	L_M_ **

搬运于2025-08-24 21:23:02，当前版本为作者最后更新于2019-03-14 20:19:40，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

萌新刚学会差分约束，看楼下各位大佬讲的都好简略根本看不懂，就写一篇详细点儿证明差分约束的题解

众所周知，差分约束有m个不等式，要找到一组解（本题中是非负解）满足所有约束，因为不等式都是差分形式，又要满足所有约束，所以叫差分约束。

我们采取这样的方式建边：对于ai - aj <= b,从j向i连一条边权为b的边

原因：ai - aj <= b十分形似 dis[i] - dis[j] <= b,即dis[i] <= dis[j] + b，在一个有最短路的图中，对于每一个点均满足这个等式，所以我们想把ai转化为i的最短路，最后求出的最短路就是答案

关于无解：当图中存在负环即无解

一方面，如果有负环，原图中没有最短路，因此无解。从另一个角度考虑，如果有负环，则意味着永远不可能满足不等式（dis[i]和dis[j]都可以无穷小），所以无解（不懂的话可以画一个有两个点的图试一试

细节：防止图不联通的情况，我们建一个超级源点S，由S向其他点连一条边权为0的边，图即联通

spfa判负环已有说明，不再赘述

上代码：

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
inline int read()
{
    int ans = 0,op = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-') op = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        (ans *= 10) += ch - '0';
        ch = getchar();
    }
    return ans * op;
}
const int maxn = 2005;
struct egde
{
	int to,next,cost;
}e[maxn * 10];
int fir[maxn],alloc;
inline void adde(int u,int v,int w)
{
	e[++alloc].next = fir[u];
	fir[u] = alloc;
	e[alloc].to = v;
	e[alloc].cost = w;
}
int n,m;
int dis[maxn],popst[maxn],minm;
bool instack[maxn];
void spfa(int s)
{
	queue<int> q;
	memset(dis,0x3f,sizeof(dis));
	dis[s] = 0;
	q.push(s);
	instack[s] = 1;
	while(q.size())
	{
		int u = q.front();
		q.pop();
		popst[u]++;
		if(popst[u] > n - 1) { printf("NO SOLUTION"); return;}
		instack[u] = 0;
		for(int i = fir[u];i;i = e[i].next)
		{
			int v = e[i].to,w = e[i].cost;
			if(dis[v] > dis[u] + w)
			{
				dis[v] = dis[u] + w;
				if(!instack[v]) q.push(v),instack[v] = 1;
			}
		}
	}
	for(int i = 1;i <= n;i++) minm = min(minm,dis[i]);
	for(int i = 1;i <= n;i++) printf("%d\n",dis[i] - minm);
}
int main()
{
	n = read(),m = read();
	for(int i = 1;i <= m;i++)
	{
		int u = read(),v = read(),w = read();
		adde(v,u,w);	
	}
	for(int i = 1;i <= n;i++) adde(n + 1,i,0);
	spfa(n + 1);
}