题解：P12088 [RMI 2019] 还原 / Restore Arrays

· · 题解

此题使用差分约束，想要 \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;
}