差分约束系统概念

 

问题转化

 

解决的问题

 

 

 

 例题1：

虽然蒜头君并没有多少钱，但是蒜头君办了很多张银行卡，共有 nn 张，以至于他自己都忘记了每张银行卡里有多少钱了。

他只记得一些含糊的信息，这些信息主要以下列三种形式描述：

银行卡 aa 比银行卡 bb 至少多 cc 元。 
银行卡 aa 比银行卡 bb 至多多 cc 元。 
银行卡 aa 和银行卡 cc 里的存款一样多。 
但是由于蒜头君的记忆有些差，他想知道是否存在一种情况，使得银行卡的存款情况和他记忆中的所有信息吻合。

输入格式

第一行输入两个整数 nn 和 mm，分别表示银行卡数目和蒜头君记忆中的信息的数目。(1\leq n,m\leq 10000)(1≤n,m≤10000)

接下来 mm 行：

如果每行第一个数是 11，接下来有三个整数 a, b, ca,b,c，表示银行卡 aa 比银行卡 bb 至少多 cc 元。

如果每行第一个数是 22，接下来有三个整数 a, b, ca,b,c，表示银行卡 aa 比银行卡 bb 至多多 cc 元。

如果每行第一个数是 33，接下来有两个整数 a, ba,b，表示银行卡 aa 和 bb 里的存款一样多。(1\leq n,m,a,b,c\leq 10000)(1≤n,m,a,b,c≤10000)

输出格式

如果存在某种情况与蒜头君的记忆吻合，输出Yes，否则输出No。

样例输入

3 3 
3 1 2 
1 1 3 1 
2 2 3 2 
样例输出
差分约束+spfa

代码：

#include<bits/stdc++.h>
using namespace std;
const int MAX_N=10010;
const int MAX_M=2*MAX_N;
int ss=0;
int n,m;
struct edge{
	int v,next,w;
}e[MAX_M];
int p[MAX_N],eid;
int dst[MAX_N];
int cnt[MAX_N];
bool inq[MAX_N];
int inf=0x3f3f3f3f;
void init(){
	memset(p,-1,sizeof(p));
	eid=0;
}
void insert(int u,int v,int w){
	e[eid].v=v;
	e[eid].w=w;
	e[eid].next=p[u];
	p[u]=eid++;
}
int spfa(int s){
	memset(dst,inf,sizeof(dst));
	memset(inq,0,sizeof(inq));
	memset(cnt,0,sizeof(cnt));
	dst[s]=0;
	queue<int>q;
	q.push(s);
	cnt[s]++;
	while(!q.empty()){
		int u=q.front();
		q.pop();
		inq[u]=0;
		for(int i=p[u];i+1;i=e[i].next){
			int x=e[i].v;
			if(dst[u]+e[i].w<dst[x]){
				dst[x]=dst[u]+e[i].w;
				if(!inq[x]){
					cnt[x]++;
					q.push(x);
				}
			}
			if(cnt[x]>n){
				return 0;
			}
		}
	}
	return 1;
}
int main(){
	init();
	scanf("%d%d",&n,&m);
	int id,a,b,c;
	for(int i=1;i<=m;i++){
		scanf("%d",&id);
		if(id==1){
			scanf("%d%d%d",&a,&b,&c);
			insert(a,b,-c);
		}else if(id==2){
			scanf("%d%d%d",&a,&b,&c);
			insert(b,a,c);
		}else{
			scanf("%d%d",&a,&b);
			insert(a,b,0);
			insert(b,a,0);
		}
	}
	for(int i=1;i<=n;i++){
		insert(ss,i,0);
	}
	if(spfa(ss)){
		cout<<"Yes"<<endl;
	}else{
		cout<<"No"<<endl;
	}
	return 0;
}