差分约束

前言

没啥好说的，存个板子，感觉这东西这辈子都不会考到。

update 2021省选Day1T2矩阵游戏。

讲解

保留环节：百度百科自学时间

差分约束系统是用于求包含n个未知数，m个不等式，形如：

[egin{cases} x_{c_1}-x_{c_1'}le y_1\ x_{c_2}-x_{c_2'}le y_2\ ...\ x_{c_m}-x_{c_m'}le y_m end{cases}]

的方程组的解的一种算法

试图大喘气

我们提出一个式子来观察：

(x_{i}-x_{j}le y)

将其转换一下：

(x_ile y+x_j)

诶！这是不是跟最短路的更新有点像，这可以转换成什么？

(j)到(i)的最短路要小于等于(y)！(感叹号，不是阶乘...)

这相当于什么？直接对于(j)向(i)连一条权值为(y)的边

然后跑最短路即可

什么，有可能出现负环？

我们思考一下负环意味着什么

(x_ile y+x_i(y<0))

这不是显然无解？

当然，我们根据这种方法构造出来的图有可能不是连通的，只需要构建一个超级源点(0)，对其向(1)到(n)每个点连一条权值为(0)的边即可

当然由于存在负边权，我们不能使用Dijkstra，只能使用SPFA

因为我不会Bellman-Ford

拓展

(x_i-x_jge y)的形式可以两边同乘(-1)改变符号

(x_i-x_j=y)的形式可以转换为：(x_i-x_jle y)和(x_i-x_jge y)两个条件

练习

板题(洛谷)

代码

板题代码

int head[MAXN],tot;
struct edge
{
	int v,w,nxt;
}e[MAXN << 1];
void Add_Edge(int x,int y,int z)
{
	e[++tot].v = y;
	e[tot].w = z;
	e[tot].nxt = head[x];
	head[x] = tot;
}

int dis[MAXN],cnt[MAXN];
bool vis[MAXN];
void spfa()
{
	queue<int> q;
	q.push(0); vis[0] = 1;
	for(int i = 1;i <= n;++ i) dis[i] = INF;
	while(!q.empty())//正常SPFA
	{
		int t = q.front(); q.pop();
		cnt[t]++;
		vis[t] = 0;
		if(cnt[t] > n) {printf("NO");return;}//存在负环
		for(int i = head[t]; i ;i = e[i].nxt)
			if(dis[e[i].v] > dis[t] + e[i].w)
			{
				dis[e[i].v] = dis[t] + e[i].w;
				if(!vis[e[i].v])
					q.push(e[i].v),vis[e[i].v] = 1;
			}
	}
	for(int i = 1;i <= n;++ i) Put(dis[i],' ');
}

int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	n = Read(); m = Read();
	for(int i = 1;i <= m;++ i)
	{
		int u = Read(),v = Read();
		Add_Edge(v,u,Read());//注意连边顺序与权值
	}
	for(int i = 1;i <= n;++ i) Add_Edge(0,i,0);//建立超级源点与边
	spfa();
	return 0;
}