洛谷P8299 题解

题意

你需要构造一个 $1∼N$ 的排列，满足 $M$ 个要求，要求形式是给出 $l,r$ 中的最大值或最小值。

思路

不难看出，这是一个二分图匹配问题。我们要给每个位置匹配一个数。那么怎么建边呢？我们发现根据题目给出的要求，好像不是很好直接看出每个位置能匹配哪些数。不过正难则反，题目给出的要求是很容易看出每个位置不能匹配哪些数的。显然如果题目给出 $[l,r]$ 中最小的数是 $x$，那么这些位置不能与任何小于 $x$ 的数匹配。大于同理。

这样就够了吗？其实是有问题的。我们这样无法保证 $x$ 这个数一定被分配到 $[l,r]$ 这个区间里。所以我们还有让所有不在 $[l,r]$ 的数都不能匹配到 $x$，这样就保证满足题目条件了。

至于二分图匹配部分，可以用匈牙利，当然我用的 Dinic。

丑陋的代码（跑得贼慢）

#include <bits/stdc++.h>
#define int long long
using namespace std;
bool ok[205][205];
int n,m,cnt=1,lst[415],s,t,inf=0x3f3f3f3f,now[415],dep[415],flow,seat[415]; 
struct edge{
    int f,t,val,lst;
    edge(int f=0,int t=0,int val=0,int lst=0):
        f(f),t(t),val(val),lst(lst){}; 
}e[400005];
void add(int u,int v,int w){
    e[++cnt]=edge(u,v,w,lst[u]);lst[u]=cnt;
    e[++cnt]=edge(v,u,0,lst[v]);lst[v]=cnt;
}
bool bfs(){
    memset(dep,-1,sizeof(dep));
    dep[s]=0;
    queue<int> q;
    q.push(s);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        now[u]=lst[u];
        for(int i=lst[u];i;i=e[i].lst){
            int v=e[i].t;
            if(dep[v]==-1&&e[i].val){
                dep[v]=dep[u]+1;
                q.push(v);
            }
        }
    } 
    return dep[t]!=-1;
}
int dfs(int u,int in){
    if(u==t)return in;
    int out=0;
    for(int i=now[u];i;i=e[i].lst){
        now[u]=i;
        int v=e[i].t;
        if(dep[v]==dep[u]+1&&e[i].val){
            int go=dfs(v,min(in,e[i].val));
            in-=go,out+=go;
            e[i].val-=go,e[i^1].val+=go;
            if(!in)break;
        }
    }
    if(!out)dep[u]=-1;
    return out;
}
signed main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int op,u,v,x;
        cin>>op>>u>>v>>x;
        if(op==1){
            for(int j=u;j<=v;j++){
                for(int k=x+1;k<=n;k++){
                    ok[j][k]=1;
                }
            }
            for(int j=1;j<u;j++){
                ok[j][x]=1;
            }
            for(int j=v+1;j<=n;j++){
                ok[j][x]=1;
            }
        }
        else{
            for(int j=u;j<=v;j++){
                for(int k=1;k<x;k++){
                    ok[j][k]=1;
                }
            }
            for(int j=1;j<u;j++){
                ok[j][x]=1;
            }
            for(int j=v+1;j<=n;j++){
                ok[j][x]=1;
            }
        }
    }
    s=0,t=n*2+1;
    for(int i=1;i<=n;i++){
        add(s,i,1);
        add(i+n,t,1);
        for(int j=1;j<=n;j++){
            if(!ok[i][j])add(i,j+n,1);
        }
    }
    while(bfs()){
        flow+=dfs(s,inf);
    }
    if(flow!=n)puts("-1");
    else{
        for(int i=2;i<=cnt;i++){
            if(!e[i].val&&e[i^1].val&&e[i].f<=n&&e[i].f&&e[i].t>n&&e[i].t!=t){
                seat[e[i].f]=e[i].t;
            }
        }
        for(int i=1;i<=n;i++)cout<<seat[i]-n<<' ';
    }
    return 0;
}