szc 不会构造（CF2115B）

· · 题解

link

没见过的构造 trick，输的不冤，高妙，学习。某天赋哥说这是 *1800，果然 szc 不会构造。

直接构造 a 使得操作后 a_i=b_i 非常不好做，考虑放宽条件，构造 a 使得最后 a_i\geqslant b_i，其中每个 a_i 尽可能小（显然初始值尽可能小最后的结果也会趋近于 b_i），最后只要测试一遍构造出的 a 跑出来的结果是否等于 b 即可。

构造出这个 a 是可做的。对于每个操作 (u,v,w)，对 w 建立新点 w'，再连边 u\rightarrow w' 和 v\rightarrow w'。最后给每个 i 最后建立的新点赋值 b_i，反拓扑序跑一遍贪心即可（实现上不必拓扑排序，倒着跑 p 组询问建立的边即可），每个点能取的最小值是指向所有点的最大值。于是最初存在的 n 个点的值即为构造出的 a。

总结的话，主要的启发就是把 构造使得与目标相等 转换成 最小的构造使得大于等于目标。

#include <bits/stdc++.h>
//taskkill /f /im 未命名1.exe
#define ED cerr<<endl;
#define TS cerr<<"I AK IOI"<<endl;
#define cr(x) cerr<<x<<endl;
#define cr2(x,y) cerr<<x<<" "<<y<<endl;
#define cr3(x,y,z) cerr<<x<<" "<<y<<" "<<z<<endl;
#define cr4(x,y,z,w) cerr<<x<<" "<<y<<" "<<z<<" "<<w<<endl;
#define popcnt __builtin_popcount
#define all(s) s.begin(),s.end()
#define bstring basic_string
//#define add(x,y) (x+=y)%=mod
#define pii pair<int,int>
#define epb emplace_back
#define pb push_back
#define mk make_pair
#define ins insert
#define fi first
#define se second
#define ll long long
//#define ull unsigned long long
using namespace std;
const int N=3e5+5,INF=2e9,mod=1e9+7;
int t,n,q;
int f[N+N],a[N],b[N];

struct node {
    int u,v,w;
}_e[N],e[N];
int nw[N];

void sol() {
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;++i) {
        scanf("%d",&b[i]),nw[i]=i;
    }
    int u,v,w;
    for(int i=1;i<=q;++i) {
        scanf("%d%d%d",&u,&v,&w);
        _e[i]={u,v,w},e[i]={nw[u],nw[v],nw[w]=n+i};
    }
    for(int i=1;i<=n+q;++i) f[i]=0;
    for(int i=1;i<=n;++i) f[nw[i]]=b[i];
    for(int i=q;i>=1;--i) {
        u=e[i].u,v=e[i].v,w=e[i].w;
        f[u]=max(f[u],f[w]),f[v]=max(f[v],f[w]);
    }
    for(int i=1;i<=n;++i) a[i]=f[i];
    for(int i=1;i<=q;++i) {
        a[_e[i].w]=min(a[_e[i].u],a[_e[i].v]);
    }
    for(int i=1;i<=n;++i) {
        if(a[i]!=b[i]) {
            puts("-1");return;
        }
    }
    for(int i=1;i<=n;++i) printf("%d ",f[i]);
    puts("");
}

int main()
{
    scanf("%d",&t);
    while(t--) {
        sol();
    }
    return 0;
}