「USACO 2005 Dec. Gold/poj3169」Layout - 差分约束系统

题目大意

---

题目分析

很明显的差分约束系统。
对于互相爱慕的奶牛，题目要求$d_b-d_a\le x$，移项得到$d_a+x\ge d_b$，这就是松弛的不等式啊，因此从$a$向$b$建边，边权为$x$。

对于互相仇视的奶牛，题目要求$d_b-d_a\ge x$，移项得到$d_b-x\ge d_a$，因此从$b$向$a$建边，边权为$-x$。

然后跑一次Spfa，若存在负环，说明无法满足限制条件，输出$-1$，若$dist[n]=inf$，说明存在可以无限大的方案，输出$-2$，否则输出$dist[n]$。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num;
}
const int maxn=10005;
int n,m1,m2,dist[maxn],inque[maxn],used[maxn];
struct Edge {
	int from,to,dist;
};
vector<Edge>edges[maxn];
void AddEdge(int x,int y,int v) {
	edges[x].push_back((Edge) {
		x,y,v
	});
}
bool Spfa() {
	for(int i=1; i<=n; i++)dist[i]=0x7fffffff/2;
	dist[1]=0;
	queue<int>Q;
	Q.push(1);
	while(!Q.empty()) {
		int Now=Q.front();
		Q.pop();
		inque[Now]=0;
		for(Edge& e:edges[Now]) {
			int Next=e.to;
			if(dist[Next]>dist[Now]+e.dist) {
				dist[Next]=dist[Now]+e.dist;
				if(!inque[Next]) {
					used[Next]++;
					if(used[Next]>=n)return false;
					inque[Next]=1;
					Q.push(Next);
				}
			}
		}
	}
	return true;
}
int main() {
	n=Get_Int();
	m1=Get_Int();
	m2=Get_Int();
	for(int i=1; i<=m1; i++) {
		int x=Get_Int(),y=Get_Int(),v=Get_Int();
		AddEdge(x,y,v);
	}
	for(int i=1; i<=m2; i++) {
		int x=Get_Int(),y=Get_Int(),v=Get_Int();
		AddEdge(y,x,-v);
	}
	if(!Spfa())puts("-1");
	else if(dist[n]==0x7fffffff/2)puts("-2");
	else printf("%d\n",dist[n]);
	return 0;
}