CF1615H-Reindeer Games【保序回归,整体二分,网络流】

正题

题目链接:https://www.luogu.com.cn/problem/CF1615H

---

题目大意

有 $n$ 个点，每个点有个初始权值 $a_i$ ，你每次可以让一个点权值 $+1$ 或者 $-1$ 。

有 $m$ 个限制要求某个点最终权值小于等于另一个点。

求最少的操作次数使得满足所有限制。

$2\le n,m\le 1000,1\le a_i\le 10^9$

---

解题思路

对于这类的保序回归问题，我们可以考虑整体二分，当前枚举到 $mid$ 时我们考虑将点权设为 $mid$ 或者 $mid+1$ 时的最优情况，如果在这种情况下某个点被设置为 $mid$ 则最终值在 $[l,mid]$ 中，否则在 $[mid+1,r]$ 中。

然后我们考虑用网络流解决设置点权的问题，如果要求 $b_x\le b_y$ ，那么当 $b_x$ 被设置为 $mid+1$ 时 $b_y$ 也要被设置为 $mid+1$ ，可以将题目变为一个最大权闭合图问题，使用网络流解决即可。

---

code

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#define ll long long
using namespace std;
const ll N=1100;
ll n,m,s,t,a[N],p[N],b[N];
ll pos[N],c[N],np[N],ans[N];
vector<ll> G[N];
namespace Net{struct node{ll to,next,w;}a[N<<2];ll dep[N],ls[N],tot,cnt;queue<ll> q;void addl(ll x,ll y,ll w){a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;a[tot].w=w;a[++tot].to=x;a[tot].next=ls[y];ls[y]=tot;a[tot].w=0;}bool bfs(){while(!q.empty())q.pop();for(ll i=1;i<=cnt;i++)dep[i]=0;q.push(s);dep[s]=1;while(!q.empty()){ll x=q.front();q.pop();for(ll i=ls[x];i;i=a[i].next){ll y=a[i].to;if(dep[y]||!a[i].w)continue;dep[y]=dep[x]+1;q.push(y);if(y==t)return true;}}return false;}ll dinic(ll x,ll flow){if(x==t)return flow;ll rest=0,k;for(ll i=ls[x];i;i=a[i].next){ll y=a[i].to;if(!a[i].w||dep[x]+1!=dep[y])continue;rest+=(k=dinic(y,min(a[i].w,flow-rest)));a[i].w-=k;a[i^1].w+=k;if(rest==flow)return rest;}if(!rest)dep[x]=0;return rest;}ll solve(){ll ans=0;while(bfs())ans+=dinic(s,1e18);bfs();return ans;}void init(){for(ll i=1;i<=cnt;i++)ls[i]=0;tot=1;s=1;t=2;return;}
}
void solve(ll l,ll r,ll L,ll R){if(l>r)return;if(L==R){for(ll i=l;i<=r;i++)ans[p[i]]=b[L];return;}ll mid=(L+R)>>1;Net::init();for(ll i=l;i<=r;i++){ll x=p[i];pos[x]=i;c[i]=abs(a[x]-b[mid])-abs(a[x]-b[mid+1]);if(c[i]>0)Net::addl(s,3+i-l,c[i]);else Net::addl(3+i-l,t,-c[i]);}for(ll i=l;i<=r;i++){ll x=p[i];for(ll z=0;z<G[x].size();z++)if(pos[G[x][z]]>=l&&pos[G[x][z]]<=r){ll j=pos[G[x][z]];Net::addl(3+i-l,3+j-l,1e18);}}for(ll i=l;i<=r;i++)pos[p[i]]=0;Net::cnt=3+r-l;Net::solve();ll xl=l,xr=r;for(ll i=l;i<=r;i++){if(Net::dep[3+i-l])np[xr--]=p[i];else np[xl++]=p[i];}for(ll i=l;i<=r;i++)p[i]=np[i];solve(l,xl-1,L,mid);solve(xr+1,r,mid+1,R);return;
}
signed main()
{ll k;scanf("%lld%lld",&n,&k);for(ll i=1;i<=n;i++)scanf("%lld",&a[i]),p[i]=i,b[i]=a[i];sort(b+1,b+1+n);m=unique(b+1,b+1+n)-b-1;for(ll i=1,x,y;i<=k;i++){scanf("%lld%lld",&x,&y);G[x].push_back(y);}solve(1,n,1,m);for(ll i=1;i<=n;i++)printf("%lld ",ans[i]);return 0;
}