自动搬运

查看原文

来自洛谷，原作者为

	Le0Chan 我们都有光明的未来。

搬运于2025-08-24 22:26:15，当前版本为作者最后更新于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;
}