Bipartite King

L: Fat

The question ：

Ideas ：
Bipartite map matching .
For a permutation , Each location has some limitations , The reverse is that each number has some places to go , Let all positions hold , Bipartite graph matching can be used to determine whether there is an optimal solution .

tips：
For this garbage problem , Greed is no good ,dp No problem .
Just think about graph theory , Network flow will never let you wa, At most T.

#include<bits/stdc++.h>
#define rep(i,n,m) for(int i=n;i<=m;i++)
typedef long long ll;
using namespace std;


struct node{
    
	ll x,y,v;
}maxn[40005];
node minn[40005];
node bb[40005];
bool cmp1(node a,node b){
    
	return a.v<b.v;
}
bool cmp2(node a,node b){
    
	return a.v>b.v;
}
bool cmp(node a,node b){
    
	if(a.v!=b.v)return a.v<b.v;
	return a.x<b.x;
}
struct nod{
    
	ll maxn,minn;
}a[205];

ll n,m;
ll posl[205];
ll posr[205];
 
vector<int>mp[405];
int match[405];
int used[405];
void add(int u,int v){
    
	mp[u].push_back(v);
	mp[v].push_back(u);
}
bool dfs(int v){
    
	used[v]=1;
	for(int i=0;i<mp[v].size();i++){
    
		int u=mp[v][i],w=match[u];
		if(w<0||!used[w]&&dfs(w)){
    
			match[v]=u;
			match[u]=v;
			return 1;
		}
	}
	return 0;
}
int bi(){
    
	int res=0;
	memset(match,-1,sizeof(match));
	for(int i=1;i<=2*n;i++){
    
		if(match[i]<0){
    
            memset(used,0,sizeof(used));
			if(dfs(i))res++;
		}
	}
	return res;
}
int main(){
    
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n>>m;
	ll cnt1=0,cnt2=0;
	rep(i,1,m){
    
		ll f;
		cin>>f;
		if(f==1){
    
			cnt1++;
			ll x,y,v;
			cin>>x>>y>>v;
			maxn[cnt1].x=min(x,y);
			maxn[cnt1].y=max(x,y);
			maxn[cnt1].v=v;
		}
		else{
    
			cnt2++;
			ll x,y,v;
			cin>>x>>y>>v;
			minn[cnt2].x=min(x,y);
			minn[cnt2].y=max(x,y);
			minn[cnt2].v=v;
		}
	}
	
	rep(i,1,n){
    
		a[i].minn=0;
		a[i].maxn=n+1;
	}
	ll flag=1;
	sort(maxn+1,maxn+cnt1+1,cmp1);
	sort(minn+1,minn+cnt2+1,cmp2);
	rep(i,1,cnt1){
    
		ll f=0;
		rep(j,maxn[i].x,maxn[i].y){
    
			if(a[j].maxn>=maxn[i].v){
    
				a[j].maxn=maxn[i].v;
				f=1;
			}
		}
		if(f==0)flag=0;
	}
	rep(i,1,cnt2){
    
		ll f=0;
		rep(j,minn[i].x,minn[i].y){
    
			if(a[j].minn<=minn[i].v){
    
				a[j].minn=minn[i].v;
				f=1;
			}
		}
		if(f==0)flag=0;
	}
	rep(i,1,n){
    
		if(a[i].maxn<a[i].minn)flag=0;
	}
	ll cnt=0;
	rep(i,1,cnt1){
    
		cnt++;
		bb[cnt].x=maxn[i].x;
		bb[cnt].y=maxn[i].y;
		bb[cnt].v=maxn[i].v;
	}
	rep(i,1,cnt2){
    
		cnt++;
		bb[cnt].x=minn[i].x;
		bb[cnt].y=minn[i].y;
		bb[cnt].v=minn[i].v;
	}
	sort(bb+1,bb+cnt+1,cmp);
	rep(i,1,n-1){
    
		rep(j,i+1,n){
    
			if(bb[i].v==bb[j].v){
    
				if(bb[j].x>bb[i].y)flag=0;
			}
		}
	}
	if(flag==0){
    
		cout<<-1<<endl;
	}
	else{
    
		
		for(int i=1;i<=n;i++){
    
			posl[i]=0;
			posr[i]=n+1;
		}
		for(int i=1;i<=cnt;i++){
    
			int to=bb[i].v;
			posl[to]=max(posl[to],bb[i].x);
			posr[to]=min(posr[to],bb[i].y);
		}
		for(int i=1;i<=n;i++){
    
			if(posl[i]==0&&posr[i]==n+1){
    
				for(int j=1;j<=n;j++){
    
					if(a[j].maxn>i&&a[j].minn<i){
    
						add(i,n+j);
					}
				}
			}else{
    
				for(int j=posl[i];j<=posr[i];j++)
					if(a[j].maxn>=i&&a[j].minn<=i){
    
						add(i,n+j);
					}
			}
		}
		int ans=bi();
		if(ans!=n){
    
			cout<<-1<<endl;
		}else{
    
			for(int i=1+n;i<=2*n;i++)cout<<match[i]<<" ";
		}
	}
	return 0;
}