题解：CF2245D2 Construct an Array (Hard Version)

zsjaaaxy · 2026-08-09 10:10:59 · 题解

preface

这个构造太神了，一下子没有想到。

solution

我们注意到 a_{i}+a_{j}\ge 0 等价于 -a_{i}\le a_{j},-a_{j}\le a_{i}，a_{i}+a_{j}<0 等价于 a_{i}<-a_{j},a_{j}<-a_{i}。考虑建 2n 个点分别表示 a_{x},-a_{x}，从小的连一条边到大的。注意我们这边放缩掉了等于号。

然后我们注意无解当且仅当有两点强连通。如果有解即是若干的个有向无环图，考虑求出每点的拓扑序 pos_{x}。

然后非常神的一个构造是另 a_{x}=pos_{x}-pos_{x+n}。这边解释一下这个构造为什么是合法的。不妨考虑第一类限制 a_{i}+a_{j}\ge 0，此时也就是 pos_{i}+pos_{j}-pos_{i+n}-pos_{j+n} \ge 0，注意到此条件在图中的意义有 pos_{i}>pos_{j+n},pos_{j}>pos_{i+n}。所以上式成立。另一个限制同理。

code

#include<bits/stdc++.h>
using namespace std;
const int N=1000000;
int T,n,m,pos[N],cnt,in[N];
vector<int> v[N];
queue<int> q;
void solve()
{
    cin>>n>>m;
    cnt=0;
    for(int i=1;i<=2*n;i++)
    {
        v[i].clear();
        pos[i]=in[i]=0;
    }
    for(int i=1;i<=m;i++)
    {
        int op,x,y;
        cin>>op>>x>>y;
        if(op==1)
        {
            v[x+n].push_back(y);
            v[y+n].push_back(x);
            in[y]++,in[x]++;
        }
        else
        {
            v[x].push_back(y+n);
            v[y].push_back(x+n);
            in[x+n]++,in[y+n]++;
        }
    }
    for(int i=1;i<=2*n;i++)
    {
        if(!in[i])
        {
            q.push(i);  
        }   
    }
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        cnt++;
        pos[x]=cnt;
        for(auto i:v[x])
        {
            in[i]--;
            if(!in[i])
            {
                q.push(i);
            }
        }
    }
    if(cnt<2*n)
    {
        cout<<"NO\n";
        return;
    }
    cout<<"YES\n";
    for(int i=1;i<=n;i++)
    {
        cout<<pos[i]-pos[i+n]<<" ";
    }
    cout<<"\n";
    return;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>T;
    while(T--)
    {
        solve();
    }
    return 0;
}