P7056 题解

Le0Chan · 2023-08-26 10:00:58 · 题解

UPD：2023.12.13，被 @realskc hack。修了锅。现在可以通过 hack 数据。

好题无人。

从限制入手，每个限制要求 b_i 出现在 a_i 与 c_i 之间。联想到如果对一个 DAG 拓扑排序，对于每条有向边 u\to v，u 的拓扑序一定小于 v 的拓扑序。

所以我们对每个限制连两条边。a_i\to b_i 和 c_i\to b_i，但是 b_i 的入度只赋为 1，这样使得只要有一条边在拓扑排序中被删掉后，b_i 能立刻入队。

但是如果按照所有的限制连边，是有可能出现环的。我们考虑对一个有向有环图拓扑排序，实际上成环部分的点集不可能加进队列，也就不会更新拓扑序（可以自行造数据模拟）。由于题目保证有解，所以我们忽略环，强行跑拓扑排序。

跑拓扑排序的过程中，我们考虑如何求解。

如果只是将点从左到右加入答案排列，由于每条限制都有两个点向 b_i 连边，所以选择 a_i 在前还是 c_i 在前成了大问题。所以，我们选择从两边向中间填满答案序列，对于队列中的一个点 u，计算其填在左边还是右边的贡献更大，将其贪心地填进贡献大的一边。

如何计算贡献？这需要分类讨论。

首先枚举 u 充当 b 的所有限制。

该限制 a,c 都未确定位置，实际上不存在这种情况，因为不满足在开始所说的拓扑排序的性质。
该限制中 a 或 c 确定了位置。先假设是 a 确定了位置，那么 a,b 必须相同一边。如果 a 在左，那么 b 必然要放在左，否则后面 c 无论如何放都会成为 a,c,b 的非法情况。c 位置确定的情况类似。
该限制中 a 与 c 都确定位置，按上一条分别讨论即可。

其次枚举 u 充当 a 或 c 的所有限制。

如果该限制中 a,c 均未确定位置，则给 b 入队。
如果该限制中 a 或 c 确定了位置（显然不会是 u ），则 u 要和其在不同一边。证明与上述情况类似，注意如果 b 已经确定位置，则该限制能不能满足已经计算过，不能计算贡献。


#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define N 100005

int n,m;

vector<int> mid[N],sid[N],g[N];
//mid存以i为b的限制编号 
//sid存以i为a或c的限制编号
//g是正常的连边 

int ind[N];//入度 
int a[N],b[N],c[N],pos[N],ans[N];

queue<int> q;//拓扑排序用的队列 

int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>a[i]>>b[i]>>c[i];
        mid[b[i]].pb(i);
        sid[a[i]].pb(i);
        sid[c[i]].pb(i);
        ind[b[i]]++; 
    }
    for(int i=1;i<=n;i++) if(!ind[i]) q.push(i);
    int l=1,r=n;//用两个指针从两边向中间填数 
    while(!q.empty()){
        int x=q.front();q.pop();
        int val1=0,val2=0;//分别存将x放左或右的贡献 
        for(int i:mid[x]){//枚举x为b的情况 
            if(pos[a[i]]&&pos[c[i]]) continue;  
            if(pos[a[i]]){
                if(pos[a[i]]<=l) val1++;//判断已填好的在左边还是右边 
                if(pos[a[i]]>=r) val2++;
            }
            if(pos[c[i]]){
                if(pos[c[i]]<=l) val1++;
                if(pos[c[i]]>=r) val2++;
            }
        }
        for(int i:sid[x]){//枚举x为a或c的情况 
            if(pos[a[i]]&&!pos[b[i]]){
                if(pos[a[i]]<=l) val2++;
                if(pos[a[i]]>=r) val1++; 
            }
            if(pos[c[i]]&&!pos[b[i]]){
                if(pos[c[i]]<=l) val2++;
                if(pos[c[i]]>=r) val1++;
            }
            //如果ac都没填过，那就强行给b入读减一 
            if(!pos[a[i]]&&!pos[c[i]]) if(!--ind[b[i]]) q.push(b[i]);
        }
        if(val1<val2) pos[x]=r--;
        else pos[x]=l++;//贪心地填进左边或右 
        if(l>r) break;
    }
    for(int i=1;i<=n;i++) ans[pos[i]]=i;
    for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
    return 0;
}