洛谷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;
}