自动搬运

查看原文

来自洛谷，原作者为

	hunengbuwuneng 胡能不无能

搬运于2025-08-24 22:17:42，当前版本为作者最后更新于2025-06-11 16:25:47，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

[JSOI2012] 铁拳

日志

2025.6.11 申请题解成功

2025.6.12 修复边权负数及其他细节描述

鸣谢

感谢 xzf_200906 提供的解题思路及指导！

题意

给出 $n$ 场比赛（题目中表示为 $m$）及 $m$ 个人（题目中表示为 $n$），每个人会给一场比赛提供正价值和另一场比赛负价值，且价值为一个浮动区间，现给出每场比赛对比上一场比赛的价值之差，请判断无方案满足题意或缩小每人的浮动区间，以两位小数形式输出。

思路

我们看到样例可以大胆猜想：

答案一定为整数区间。

仔细想想不难证明，因为初始范围和价值都为整数，最后范围是不可能出现分数的。假设存在那么必然可以进一步缩小。

接着我们可以通过区间来想到一些算法，不过在我们的简化题意中提到会给比赛改变权值且为区间，这给了我们一个思考方向：图。

朝着这个思路想下去，或许能想到一种冷门算法：

有上下界网络流

此算法正好可以给每条边赋区间流量，与我们的思路吻合。

再看数据范围：

$N,M(N\le200,M\le100)$

时间非常充足，或许可以一试。

细节处理及实现

建图

对于一场比赛建一个点，那么有一个第 $u$ 场进来的第 $v$ 场出去的人贡献为 $[l,r]$。此时我们由 $u$ 向 $v$ 连边，上下界为 $l,r$。 但此时有两个问题，我们有从第 $0$ 场进来和第 $m+1$ 场出去的人，以及我们需要对于每条边求答案，不能全部建边啊。

对于第一个问题，从一个虚拟点 $s$ 向第 $0$ 场进来的人连边即可，上下界为 $l,r$。此时等价于直接给第 $v$ 场加上负权值。

同理，从第 $m+1$ 场出去的人向一个虚拟点 $t$ 连边即可，上下界为 $l,r$。此时等价于直接给第 $u$ 场加上正权值，对于既从第 $0$ 场进来也第 $m+1$ 场出去的人则可不加，但也可直接连边虚拟点 $s$ 和虚拟点 $t$。

	cin>>m;
	rep(i,1,m){
		cin>>c[i].w1>>c[i].w2>>c[i].u>>c[i].v;
		if(c[i].u==0) c[i].u=n+1;
		if(c[i].v==0) c[i].v=n+2;
	}

为了使对于答案不影响，虚拟点直接应该要有一条上下界为 $0,INF$ 的边连接 $t$ 和 $s$。

对于第二个问题，我们可以对于我们枚举的求答案的边更改建边方式：让一个虚拟点 $S$ 向 $v$ 连边， $u$ 向一个虚拟点 $T$ 连边，最后为不影响答案建一条上下界为 $0,INF$ 的边连接 $T$ 和 $S$，这样最后答案就会存在连接 $T$ 和 $S$ 的反边上。

然后对于一场比赛 $i$ 比上次增加 $x$ 价值，那么

当 $x$ 为正数

则虚拟点 $s$ 向 $i$ 连边，上下界为 $x,x$。

当 $x$ 为负数

则 $i$ 向虚拟点 $t$ 连边，上下界为 $-x,-x$。

这样即可强制给 $i$ 流入或流出一定流量，且由于上文连边虚拟点 $s$ 和虚拟点 $t$则对答案无影响。

		a[++ss]={n+2,n+1,0,INF};//a用于存储将建的边，格式为以u连向v一条上下界为[l,r]的边。建边t到s
		rep(i,1,n){
			if(b[i]>0) a[++ss]={n+1,i,b[i],b[i]};//x为正
			if(b[i]<0) a[++ss]={i,n+2,-b[i],-b[i]};//x为负
		}
		rep(i,1,m){
			if(i!=id) a[++ss]={c[i].u,c[i].v,c[i].w1,c[i].w2};
			else{//枚举答案的边
				a[++ss]={S2,c[i].v,c[i].w1,c[i].w2};
				a[++ss]={c[i].u,T2,c[i].w1,c[i].w2};
			}
		}
		rep(i,1,ss){//模板部分
			long long u=a[i].u,v=a[i].v,w1=a[i].w1,w2=a[i].w2,w;
			w=w2-w1;
			put(u,v,w);
			put(v,u,0);
			d2[u]+=w1;
			d[v]+=w1;
		}
		t2=t;
		rep(i,1,n+6){
			nowww[i]=now[i];
		}//记录当前边，后面回溯，模板部分
		put(T2,S2,1e18);//建边T到S
		put(S2,T2,0);

计算答案及判断输入正误

建完边就很简单了，对于输入正误跑一边可行流即可。

对于答案右边界（最大流）就要根据可行流流量加上 $S$ 向 $T$ 的最大流量，答案左边界（最小流）就要根据答案右边界（当前流）减去 $T$ 向 $S$ 的最大流量。具体原因此处不作解释，可去学习模板有源汇有上下界最大流/最小流。

		long long ans1=0,ans2=0;//答案
		ans=0;//dinic结果变量
		dinic();
		if(ans!=sss){//可行流模板
			cout<<"-1\n";
			return 0;
		}
		t=t2;//拆去不需要的边，回溯，最值流模板
		rep(i,1,n+5){
			now[i]=nowww[i];
		}
		ans2=val[t2+2];//当前流
		ans=0;
		S=S2,T=T2;//超级原点、汇点,也是前面S、T叫做S2、T2的原因
		dinic();
		ans2+=ans;//最大流
		ans1=ans2;//当前流
		ans=0;
		S=T2,T=S2;//反着跑最小流
		dinic();
		ans1-=ans;//最小流
		cout<<ans1<<".00 "<<ans2<<".00\n";//愉快的输出~

代码

#include <bits/stdc++.h>
#define debug(a) cout<<#a<<"="<<a<<"\n";
#define rep(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
const long long N=2e4+7,M=4e5+7,INF=1e18;
long long n,m,S2,T2,b[N],d[N],d2[N],S,T,t=1,t2,p[M],now[N],son[M],val[M],noww[N],nowww[N],h[N],ans;
struct node{
	long long u,v,w1,w2;
};
node a[M],c[M];
void put(int a,int b,long long c){
	p[++t]=now[a];
	now[a]=t;
	son[t]=b;
	val[t]=c;
}
bool bfs(){
	rep(i,1,n+6){
		noww[i]=now[i];
		h[i]=0;
	}
	h[S]=1;
	queue<int> q;
	q.push(S);
	while(q.size()){
		int u=q.front();
		q.pop();
		for(int i=noww[u];i;i=p[i]){
			int y=son[i];
			if(val[i]&&h[y]==0){
				h[y]=h[u]+1;
				q.push(y);
				if(y==T) return 1;
			}
		}
	}
	return 0;
}
long long dfs(int x,long long s){
	if(x==T) return s;
	long long sum=0;
	for(long long &i=noww[x];i;i=p[i]){
		int y=son[i];
		if(val[i]&&h[y]==h[x]+1){
			long long ss=dfs(y,min(s,val[i]));
			val[i]-=ss;
			val[i^1]+=ss;
			s-=ss;
			sum+=ss;
			if(s==0) break;
		}
	}
	if(sum==0) h[x]=0;
	return sum;
}
void dinic(){
	while(bfs()){
		ans+=dfs(S,1e18);
	}
}
int main(){
	cin>>n;
	b[0]=1e18;
	rep(i,1,n){
		cin>>b[i];
	}
	cin>>m;
	rep(i,1,m){
		cin>>c[i].w1>>c[i].w2>>c[i].u>>c[i].v;
		if(c[i].u==0) c[i].u=n+1;
		if(c[i].v==0) c[i].v=n+2;
	}
	rep(id,1,m){
		rep(i,1,n+6){
			now[i]=d[i]=d2[i]=0;
		}
		t=1;
		S=n+1+4,T=n+1+5;
		S2=n+1+2,T2=n+1+3;
		long long ss=0,sss=0,sss2=0;
		a[++ss]={n+2,n+1,0,INF};
		rep(i,1,n){
			if(b[i]>0) a[++ss]={n+1,i,b[i],b[i]};
			if(b[i]<0) a[++ss]={i,n+2,-b[i],-b[i]};
		}
		rep(i,1,m){
			if(i!=id) a[++ss]={c[i].u,c[i].v,c[i].w1,c[i].w2};
			else{
				a[++ss]={S2,c[i].v,c[i].w1,c[i].w2};
				a[++ss]={c[i].u,T2,c[i].w1,c[i].w2};
			}
		}
		rep(i,1,ss){
			long long u=a[i].u,v=a[i].v,w1=a[i].w1,w2=a[i].w2,w;
			w=w2-w1;
			put(u,v,w);
			put(v,u,0);
			d2[u]+=w1;
			d[v]+=w1;
		}
		t2=t;
		rep(i,1,n+6){
			nowww[i]=now[i];
		}
		put(T2,S2,1e18);
		put(S2,T2,0);
		rep(i,1,n+4){
			if(d[i]>d2[i]){
				sss+=d[i]-d2[i];
				put(S,i,d[i]-d2[i]);
				put(i,S,0);
			}
			else if(d[i]<d2[i]){
				sss2+=d2[i]-d[i];
				put(i,T,d2[i]-d[i]);
				put(T,i,0);
			}
		}
		if(sss!=sss2){
			cout<<"-1\n";
			return 0;
		}
		long long ans1=0,ans2=0;
		ans=0;
		dinic();
		if(ans!=sss){
			cout<<"-1\n";
			return 0;
		}
		t=t2;
		rep(i,1,n+5){
			now[i]=nowww[i];
		}
		ans2=val[t2+2];
		ans=0;
		S=S2,T=T2;
		dinic();
		ans2+=ans;
		ans1=ans2;
		ans=0;
		S=T2,T=S2;
		dinic();
		ans1-=ans;
		cout<<ans1<<".00 "<<ans2<<".00\n";
	}
	return 0;
}