自动搬运

查看原文

来自洛谷，原作者为

	Bill_luogu 我命由我不由天！

搬运于2025-08-24 23:12:41，当前版本为作者最后更新于2025-05-05 20:40:54，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

此题使用差分约束，想要 $\color{#52C41A}{AC}$ 此题，必须经过以下步骤。

STEP 1：什么是差分约束系统？

模板题：P5960 【模板】差分约束

差分约束系统就是由 $n$ 个变量， $m$ 条形式如 $a_{i}-a_{j}\le k$ 不等式组成，求他们的任意解。

STEP 2：用什么算法求解？

观察 $a_{i}-a_{j}\le k$，与最短路最对比： $dis_{y}-dis_{x}\le w_{<x,y>}$，发现大致相同，于是用最短路算法求解，其中的 $dis_{i}$ 就是 $a_{i}$ 的其中一个解。

STEP 3：如何建边？

设 $sum_{i}=sum_{i-1}+a_{i}$，则当 $val_{i}=1$ 时，证明前面最多有 $k-1$ 个 $0$，$sum_{r}-sum_{l-1}\ge r-l+1-(k-1)=sum_{l-1}-sum_{r}\le l+k-2-r$，当 $val_{i}=0$ 时，表示至少有 $k$ 个 $0$，$sum_{r}-sum_{l-1}\le r-l+1-k$。将 $l-1$ 和 $r$ 连边。

STEP 4：从哪个点开始？

建一个超级源节点 $0$，和每个点都连一条权值为 $0$ 的边。
怎么知道这是对的呢？
很简单，设 $a_{0}$ 为 $\infty$，相当于 $n$ 条不等式 $a_{i}\le a_{0}+0$，不影响其他不等式。

STEP 5：用哪个最短路算法？

很多人都会想到用 dijkstra ，当你提交后会发现花花绿绿的，这是因为 dijkstra 判不了无解（即有负环），所以使用 SPFA 或者 Bellman-Ford ，本蒟蒻使用的是 SPFA 。

STEP 6：一些小问题

再次提交，发现又是花花绿绿。再次回到题目，由于是 $01$ 串，所以满足 $a_{i}\le a_{i+1}$ 和 $a_{i+1}\le a_{i}+1$ ，转换分别得到 $a_{i}-a_{i+1}\le 0$ 和 $a_{i+1}-a_{i}\le1$，于是我们又得到了许多差分约束。后来发现 TLE 了，考虑优化。

AC Code：

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
queue<int> q;
vector<int> v[10010];
int dis[100010],cnt[10010];
bool vis[10010];
int n,m;
bool spfa()
{
	while(q.size())
	{
		int x=q.front();
		q.pop();
		vis[x]=0;
		for(int i=0;i<v[x].size();i+=2)
		{
			int y=v[x][i],w=v[x][i+1];
			if(dis[x]+w>=dis[y])continue;
			dis[y]=dis[x]+w;
			cnt[y]=cnt[x]+1;
			if(cnt[y]>=min(n,(int)3e3))//玄学优化
			{
				cout<<"-1";//无解
				return 0;
			}
			if(!vis[y])
			{
				q.push(y);
				vis[y]=1;
			}
		}
	}
	return 1;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int l,r,k,val;
		cin>>l>>r>>k>>val;
		l++,r++;//本蒟蒻习惯下标从 1 开始
		if(val==1)
		{
			v[r].push_back(l-1);
			v[r].push_back(l+k-2-r);
		}
		else
		{
			v[l-1].push_back(r);
			v[l-1].push_back(r-l+1-k);
		}
	}
	for(int i=1;i<=n;i++)dis[i]=2147483647;//初始化
	for(int i=0;i<n;i++)v[i].push_back(i+1),v[i].push_back(1),v[i+1].push_back(i),v[i+1].push_back(0);//加边
	vis[0]=1;
	q.push(0);
	if(spfa())
	{
		for(int i=1;i<=n;i++)
			cout<<(dis[i]>dis[i-1])<<' ';
	}
	return 0;
}