上下界网络流

题解

给定一个二分图，求一种最小价值的匹配，使得每个点的匹配次数都在$L_i,R_i$之间。显然这个可以通过上下界网络流实现。但此处要求的是最小费用流，而不是最小费用最大流，所以需要动态加边枚举流量来实现，而上下界网络流很难在残余网络上动态加边（如果每次都重构图的话会$TLE$），所以此处需要用一个小$trick$加上最小费用流来实现。该$trick$为对于每个点，都将其向$T$连的边（或者$S$向其连的边）分为两种，一种流量为$L_i$,费用为$-inf$，第二种流量为$R_i-L_i$,费用为$0$。跑完费用流后再将答案加上$L_i$的和*$inf$即可。由于第一种边费用极小，所以要优先选，当枚举到某一总流量时，如果此时即使优先选第一类便也没有选完，那么得到的答案一定大于$inf$，则这种情况代表无解。（用这样的方法可以代替上下界网络流，但是费用流速度不如$Dinic$；此题中需要在残余网络上动态加边，因此用这种方法比较方便）

代码

#include<bits/stdc++.h> 
using namespace std;
typedef long long ll;
const int N = 2e5+5;

int n,m,S,T,head[N],pre[N],d[N],cnt=1;
ll ans=1e9,ans1,ans2;

struct nd{
	int ne,to,w,f;
}e[N*20];

void in(int x,int y,int w,int f){
	++cnt;e[cnt].to=y;e[cnt].ne=head[x];head[x]=cnt;e[cnt].w=w;e[cnt].f=f;
	++cnt;e[cnt].to=x;e[cnt].ne=head[y];head[y]=cnt;e[cnt].w=0;e[cnt].f=-f;
}

bool spfa(){
	for(int i=1;i<=T;++i)d[i]=2e9;
	static bool inq[N];
	static queue<int>q;
	for(int i=1;i<=T;++i)inq[i]=0;
	d[S]=0;
	q.push(S);inq[S]=1;
	while(!q.empty()){
		int x=q.front();q.pop();inq[x]=0;
		for(int i=head[x];i;i=e[i].ne){
			int y=e[i].to;
			if(d[y]>d[x]+e[i].f&&e[i].w>0){
				d[y]=d[x]+e[i].f;
				pre[y]=i;
				if(!inq[y])inq[y]=1,q.push(y);
			}
		}
	}
	return d[T]!=2e9;
}

void dinic(){
	int flow=2e9;
	for(int i=pre[T];i;i=pre[e[i^1].to])flow=min(flow,e[i].w);
	for(int i=pre[T];i;i=pre[e[i^1].to])e[i].w-=flow,e[i^1].w+=flow;
	ans1+=flow;
	ans2+=flow*d[T];
}

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1,x,y,w;i<=m;++i){
		scanf("%d%d%d",&x,&y,&w);
		in(x,y+n,1,w);
	}
	S=2*n+2;
	T=2*n+3;
	for(int i=1;i<=n;++i){
		in(S,i,1,-1e9);
		in(S,i,1e9,0);
		in(i+n,T,1,-1e9);
		in(i+n,T,1e9,0);
	}
	S--;
	in(S,S+1,n-1,0);
	for(int i=1;i<=n+1;++i){
		in(S,S+1,1,0);
		while(spfa())dinic();
		ans=min(ans,ans2+(ll)2e9*n);
	}
	if(ans>=1e9)printf("NIE\n");
	else printf("%d\n",ans);
}