Blog

图论建模解决不等关系的经典例题。

首先不等关系可以用有向边来刻画，一条边 $u\overset{w}\rightarrow v$ 表示 $u$ 比 $v$ 至少大了 $w$。对于每一条限制，都这样进行建边，最后跑拓扑排序，钦定入度为 $0$ 的所有点的值为 $10^9$，转移求得每个点合法的最大值即可。

最后无解需要判断如下边界：

• 拓扑排序过程中出现环。
• 无法满足赋值条件。
• 无法满足 $val \ge 1$ 的条件。

这是最朴素的暴力，直接连边显然是会爆炸的，我们考虑逐步优化：

• 注意到一次操作是 $k$ 个点向一个固定的点集连边，所以我们可以建立一个虚点，将虚点向点集里的点连边，再用这 $k$ 个点直接向虚点连边即可。
• 这样建边还是有可能会炸，例如我每次都是对 $1\sim n$ 操作，而每次 $k$ 都是 $1$，就会建 $O(n^2)$ 条边。
• 注意到最后连边的段只有 $\bm{O(\sum k)}$ 个，而 $\sum k \le 3\times 10^5$，所以我们可以对每个连边的段进行整体连边。这个可以使用线段树优化建图实现。

优化完后本题即可通过。时间复杂度 $O((n+m)\log n)$。

#include <bits/stdc++.h>
#define fi first
#define se second
#define eb(x) emplace_back(x)
#define pb(x) push_back(x)
#define lc (p << 1)
#define rc ((p << 1) | 1)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
using pi = pair<int, int>;
const int xN = 100005, N = 600005, M = 7000005, MXV = 1000000000;
int n, s, m, orival[xN], ks[xN], kcnt, idx, ans[N];
int pid[N], yid[N], rd[N];
int h[N], eidx;
struct Edge{
    int v, ne, w;
}e[M];
void add(int u, int v, int w)
{
    e[++eidx] = {v, h[u], w};
    rd[v]++;
    h[u] = eidx;
}
struct Node{
    int l, r, id;
};
struct Segtree{
    Node tr[4 * N];
    void build(int p, int ln, int rn)
    {
        tr[p] = {ln, rn, ++idx};
        if(ln == rn)
        {
            pid[tr[p].id] = ln;
            yid[ln] = tr[p].id;
            return;
        }
        int mid = (ln + rn) >> 1;
        build(lc, ln, mid);
        build(rc, mid + 1, rn);
        add(tr[p].id, tr[lc].id, 0);
        add(tr[p].id, tr[rc].id, 0);
    }
    void link(int p, int ln, int rn, int x)
    {
        if(ln <= tr[p].l && tr[p].r <= rn)
        {
            add(x, tr[p].id, 0);
            return;
        }
        int mid = (tr[p].l + tr[p].r) >> 1;
        if(ln <= mid) link(lc, ln, rn, x);
        if(rn >= mid + 1) link(rc, ln, rn, x);
    }
}tr1;
void Topo()
{
    queue<int> q;
    for(int i = 1; i <= idx; i++)
    {
        if(rd[i] == 0)
        {
            q.push(i);
            ans[i] = MXV;
        }
    }
    int ncnt = 0;
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        if(pid[u]) ncnt++;
        for(int i = h[u]; i ; i = e[i].ne)
        {
            int v = e[i].v, w = e[i].w;
            ans[v] = min(ans[v], ans[u] - w);
            rd[v]--;
            if(rd[v] == 0) q.push(v);
        }
    }
    if(ncnt != n)
    {
        cout << "NIE\n";
        exit(0);
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> s >> m;
    memset(orival, -1, sizeof(orival));
    memset(ans, 0x3f, sizeof(ans));
    tr1.build(1, 1, n);
    for(int i = 1; i <= s; i++)
    {
        int p, d;
        cin >> p >> d;
        orival[p] = d;
        ans[yid[p]] = d;
    }
    for(int i = 1; i <= m; i++)
    {
        int l, r;
        cin >> l >> r >> kcnt;
        int tmp = ++idx, pre = l - 1;
        for(int j = 1; j <= kcnt; j++)
        {
            cin >> ks[j];
            if(ks[j] - 1 >= pre + 1)
                tr1.link(1, pre + 1, ks[j] - 1, tmp);
            pre = ks[j];
        }
        if(r >= pre + 1)
            tr1.link(1, pre + 1, r, tmp);
        for(int j = 1; j <= kcnt; j++)
            add(yid[ks[j]], tmp, 1);      
    }
    Topo();
    for(int i = 1; i <= n; i++)
    {
        if(orival[i] != -1 && ans[yid[i]] != orival[i])
        {
            cout << "NIE";
            return 0;
        }
        if(ans[yid[i]] < 1)
        {
            cout << "NIE";
            return 0;            
        }
    }
    cout << "TAK\n";
    for(int i = 1; i <= n; i++) cout << ans[yid[i]] << " ";
    return 0;
}