SPFA与差分约束

思考：差分约束

$max(x_1-x_2)$	$min(x_1-x_2)$
求最短路	求最长路
即在满足所有不等式的情况下 松弛所有的边 由于$\leq$ 求max的边界情况	求最长路 松边 由于$\geq$ 求min的边界情况

$min(x_1-x_2) = -max(x_2-x_1)$
其实就是把不等式乘以-1 求
在代码里直接 松弛的时候 dis[es[e].v] < dis[x]+es[e].w 变符号大小就行

题目 POJ 1201 Interval

题目链接
参考

题目内容
三元组（ai，bi，ci）表示在整数区间[ai,bi]上至少有ci个整数属于集合Z。（整数集合Z的元素可以不连续）
问Z最少包含多少个点。

输入描述
第一行一个整数n，表示区间个数.(1 <= n <= 50000)
以下n行，每行是三个整数ai，bi，ci，由空格隔开

输出描述
Z的元素个数

输入样例
5
3 7 3
8 10 3
6 8 1
1 3 1
10 11 1

输出样例
6

#include <iostream>
#define MAX_E 50005
#define INF 0x3f3f3f3f
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
struct edge{
	int next, v, w;
};

int dis[MAX_E], head[MAX_E], vis[MAX_E], num[MAX_E];
int cnt = 0;
int n, minn = INF, maxx = -INF;
edge es[MAX_E];
 
//数组实现邻接表，head提前初始化为-1 head存最后一条起点为u的边的编号 从后往前 
// cnt表示为边的编号 一个点的第一条边next=-1，遇到相同起点的边 
//.next = head[u]也就是(head存最后一条起点为u的边的编号) 然后head[u]存最后一条边(cnt自加前) 
void add(int u, int v, int w)
{
	es[cnt].v = v;
	es[cnt].w = w;
	es[cnt].next = head[u];
	head[u] = cnt++; 
}

void SPFA(int s){
	for(int i = minn; i <= maxx; i++)
		dis[i] = -INF;
	dis[s] = 0;
	queue<int> q;
	q.push(s);
	while(!q.empty()){
		int x = q.front(); q.pop();
		vis[x] = 0;//判断此点是否在队列中
		for(int e = head[x]; e != -1; e=es[e].next)
			if(dis[es[e].v] < dis[x]+es[e].w)//只有松弛的 才可能继续松弛 
			{
				dis[es[e].v] = dis[x]+es[e].w;	
				if(!vis[es[e].v])
				{
					if(cnt == ++num[es[e].v]) //最多经过其他所有点松弛，超过证明有环 
						cout << "存在负环";
					q.push(es[e].v);
					vis[es[e].v] = 1;
				}
			}			 
	} 
}

int main(){
	cin >> n;
	memset(dis, INF, sizeof(dis));
	memset(head, -1, sizeof(head));
	memset(num, 0, sizeof(num));
	while(n--){
		int u, v, w;
		cin >> u >> v >> w;
		add(u, v+1, w);
		minn = min(minn, u);
		maxx = max(maxx, v+1);
	} 
	for(int i = minn; i < maxx; i++)
	{
		add(i, i+1, 0);
		add(i+1, i, -1);
	}
	/*
	Sbi - Sai >= ci
	Si - Si-1 >= 0
	Si-1 - Si >= -1
	可以看做在一条线上 区间上的数 数量不同 0至8的数>=0至6的数 但 1>=(0至8)-(0至7)>=0 
	*/ 
	SPFA(minn);//传源点 	
	cout << dis[maxx] << endl;
	return 0;
}

赏

请作者喝养乐多

支付宝

微信