题解：P7056 [NWRRC 2015] Insider's Information

· · 题解

前言

个人洛谷首黑，模拟赛 T4 未切。

简化题面：

一个 n 的排列 A 满足 m 个约束条件，每个约束条件形如 a，b，c 表示数字 b 在排列中位于数字 a，c 的中间或数字 c，a 的中间，让你构造一个排列，使其满足这些约束条件中的至少 \lceil \frac{m}{2} \rceil 个。

观察题面：

首先想一下简化版，假设每个约束条件为 b 强制在 a 的后面，c 强制在 b 的后面，与原题区别在于强制要求了 a,c 的顺序。那么这道题就变成了拓扑排序的板子题，因为保证存在解，又给定了顺序，因此直接拓扑即可。

现在重新考虑一下这道题，由于每个约束条件 a,c 的地位一模一样,因此我们将他们称为 e，将 b 称为 m，此时一个约束条件的在序列中的出现情况共有 3 种：eem，eme，mee 但是只有第二种情况时该约束条件才会产生 1 的贡献，由于三种条件太复杂，我们又发现 mee 这种情况可以通过类似于刚才的拓扑排序直接跳过不会出现，也就是说我们可以先保证每一个 m 都不会在两个 e 都没出现的时候出现。具体地，我们对于每一个条件，将两个 e 同时向 m 连边，当删除其中一条边时，同时删除另一条，这样虽然图建出来可能有环，但题目保证有解，因此一定存在合法拓扑序，这样删边也就能同时拆环了。

算法设计：

得出填的顺序后，我们开始考虑怎么填数。我们发现如果对于序列，前缀确定，后缀确定，只有中间一段空余，我们可以很轻易的算出已经确定两个点的约束条件是否产生贡献。因此我们考虑从两端填到中间，对于要填的 u，我们只有两种填的选择：将 u 填入当前空余段的最左边或最右边。我们将他带来的贡献分为以下几种情况：

1.u 为 e 且另一个 e 已经确定，m 未定：如果另一个 e 在左段，那么 u 填在右端，m 只能填在中间，一定产生贡献，否则一定不能产生贡献；如果另一个 e 在右段，那么 u 填在左端，m 只能填在中间，一定产生贡献，否则一定不能产生贡献。

2.u 为 m 且其中一个 e 已经确定，另一个 e 未定：如果确定的 e 在左段，那么 u 填在左端，另一个 e 只能填在后面，一定产生贡献，否则一定不能产生贡献；如果确定的 e 在右段，那么 u 填在右端，另一个 e 只能填在前面，一定产生贡献，否则一定不能产生贡献。

以上两种统计方式，对于每一个约束条件，只会在填第二个数的时候统计一次，因此不会算重或算漏。每次我们比较当前 u 填左端的贡献大还是右端大，每次选择贡献大的一边填，这样每次就能保证产生贡献的比浪费的多，因此最后总贡献也大于等于 \lceil \frac{m}{2} \rceil。

代码：

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
int read()
{
    char c=getchar();
    int f=1,x=0;
    while(c<'0'||c>'9')
    {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=(x<<1)+(x<<3)+(c^'0');
        c=getchar();
    }
    return x*f;
}
void print(int x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9) print(x/10);
    putchar(x%10+'0');
}
const int N=1e5+5;
int n,m,in[N],l,r,ans[N],pos[N];
queue<int> q;
struct node
{
    int x,y,z;
}a[N];
bool b[N],vis[N];
vector<node> edge[N],mid[N];
void add(int u)
{
    int vl=0,vr=0;
    for(auto it=edge[u].begin();it!=edge[u].end();it++)
    {
        int x=(*it).x,y=(*it).y,z=(*it).z;
        if(!pos[x]&&pos[y])
        {
            if(pos[y]<l) vr++;
            else vl++;
        }
    }
    for(auto it=mid[u].begin();it!=mid[u].end();it++)
    {
        int x=(*it).x,y=(*it).y,z=(*it).z;
        if(!pos[x]&&pos[y])
        {
            if(pos[y]<l) vl++;
            else vr++;
        }
        if(pos[x]&&!pos[y])
        {
            if(pos[x]<l) vl++;
            else vr++;
        }
    }
    if(vl>=vr) ans[l]=u,pos[u]=l,l++;
    else ans[r]=u,pos[u]=r,r--;
}
int main()
{
    n=read();
    m=read();
    l=1,r=n;
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        x=read();
        y=read();
        z=read();
        in[y]+=2;
        edge[x].push_back({y,z,i});
        edge[z].push_back({y,x,i});
        mid[y].push_back({x,z,i});
        if(x>y) swap(x,y);
        a[i].x=x;
        a[i].y=y;
        a[i].z=z;
    }
    for(int i=1;i<=n;i++)
        if(!in[i]) q.push(i);
    while(q.size())
    {
        int u=q.front();
        q.pop();
        add(u);
        for(auto it=edge[u].begin();it!=edge[u].end();it++)
        {
            int x=(*it).x,y=(*it).y,z=(*it).z;
            if(b[z]) continue;
            in[x]-=2;
            b[z]=true;
            if(!in[x]) q.push(x);
        }
    }
    for(int i=1;i<=n;i++)
    {
        print(ans[i]);
        putchar(' ');
    }
    return 0;
}