首页 > 其他分享 >CF1615H-Reindeer Games【保序回归,整体二分,网络流】

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

时间:2024-08-13 09:48:47浏览次数:13  
标签:ll mid tot leq Reindeer Games ls 保序 include

正题

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


题目大意

有 \(n\) 个点,每个点有个初始权值 \(a_i\) ,你每次可以让一个点权值 \(+1\) 或者 \(-1\) 。

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

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

\(2\leq n,m\leq 1000,1\leq a_i\leq 10^9\)


解题思路

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

然后我们考虑用网络流解决设置点权的问题,如果要求 \(b_x\leq 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;
}

标签:ll,mid,tot,leq,Reindeer,Games,ls,保序,include
From: https://www.cnblogs.com/QuantAsk/p/18356250

相关文章

  • 【倍增】Rigged Games
    题意两队打比赛,大比分2b−1赢,小比分2a−1赢。给定的长度为n的串,两队比赛的每个小分结果是这个串的循环重复。问从该串的每个位置开始,最终谁会赢得整个比赛。思路倍增。首先对于每个位置,计算出它\(2a-1\)局后的比分的比分终点的位置。然后采用倍增,即假设我们要......
  • 2024牛客多校3J Rigged Games
    欢迎来我的博客看这篇题解!Problem在两人竞技比赛中,对于任何正整数\(a\),我们定义\(BO(2a-1)\)如下:两名玩家继续竞争,直到其中一人获胜\(a\)次,那么他赢得整个比赛。\(BO(2a-1)\)最多包含\(2a-1\)小局游戏,最少包含\(a\)小局游戏。现在两个人进行一场DotA2比赛,使用的......
  • 《Epic Games》启动显示找不到xinput1_3.dll怎么处理,Epic游戏平台提示缺失xinput1_3.d
    在通过EpicGames平台尽情畅玩各类精彩游戏的过程中,有部分玩家或许会不幸遭遇“找不到xinput1_3.dll”或者“xinput1_3.dll缺失”这样的错误提示。由此导致游戏无法顺利启动。这类问题的根源在于系统中缺少了一个被称作“xinput1_3.dll”的关键重要动态链接库文件,直接对游戏的......
  • Games101-3 triangle
    rasterize==drawingontothescreencolor=(red,green,blue)pixelindicesarefrom(0,0)to(width-1,height-1)pixel(x,y)iscenteredat(x+0.5,y+0.5)光栅化判断一个像素的中心点是否需要draw采样的方法--将函数离散化如果中心再三角形内。如何判断......
  • Games101-5 shadering
    shader对不同物体应用不同的材质定义:shading!=shadowdiffusereflection漫反射光照角度不同,则反射程度也不同于此同时物体离光源越远,反射程度越低高光项镜面反射和视线比较接近的时候使用半程向量计算高光注:半程向量比较好算,反射向量比较难算指数p:cos......
  • Games101-6 Geometry
    implicit--隐式几何explicit--显示几何implicit点不需要知道位置,但是可以用点之间的关系表示(按照类别归类)E.g.allpointsin3D,where$x2+y2+z^2=1$更通用的表示$f(x,y,z)=0$劣势:不直观优势:可以很简单的判断一个点是否再物体内或者外。explicit......
  • Games101-7 raytracing
    shadowmapping思想:光源可以看到点,人也可以看到的点。---不在shadow中的点只能处理点光源深度不一致浮点数的精度问题。软/硬阴影raytracing直线传播不会碰撞从光源出发,到人眼光线是可以反射的多次弹射的光纤追踪rayequation对隐式表面对显示......
  • Games101-7 raytracing2
    辐射度量学basicradiometry---精确的描述光光线的强度Iis10。在屋里层次准确的描述光Newterms:radiantfluxintensityirradianceradianceradiantenergyandflux,radiantintensityRadiantintensity中角度是如何定义的单位立体角Radiantinte......
  • Games101-8 material and appearance
    漫反射的prdfglossymaterial折射BTDF全反射的情况:$n_i$远大于$n_{t}$也就是说入射密度大。因此水底看空气---会发生全反射情况。fresnelreflectionterm菲涅尔项绝缘体见到那说就是如果如何入射光和法线几乎平行---则大量会被反射。导体......
  • Games101 环境搭建
    wsl环境配置必要的库sudoaptinstallg++gdbcmakesudoaptinstalllibopencv-devlibeigen3-devopencv头文件{"configurations":[{"name":"Linux","includePath":[&qu......