「bzoj4669」抢夺 - 二分+费用流

题目大意

    大战将至, 美国决定实行计划经济。美国西部总共有$N$个城市，编号为$0\rightarrow N−1$，以及$M$条道路，道路是单向的。其中城市$0$是一个大城市，里面住着$K$个人，而城市$N−1$是一个农业城市。现在所有城市$0$的居民都需要到城市$N−1$去领取食物。由于担心体力不支，所以居民都会采取开车的形式出行。但道路不是无限宽的，对于一条道路，会有$c_i$的限制，表示在同一天内，最多只能有$c_i$辆车同时在这条道路上行驶。一条道路的长度为$1$，每辆车的行驶速度也可以假定为$1$每天。城市$N−1$会在每个居民都到达后马上开始发放食物。现在Reddington想知道，假如在最优安排下，居民最早能在多少天后领到食物。假如没有居民那就不需要发放食物，默认为第$0$天。

---

题目分析

考虑二分答案$ans$。
考虑第一波最先走的人，他们肯定沿着各种途径前往目标结点，因此后一波走的人路径与前一波人完全相同。
因此我们可以根据第一次的增广计算出在$ans$天内到达的人数：

$$num=(ans-dist[T]+1)*a[T]$$

其中$dist[]$是残余网络最短路，$a[]$是可增广量。
若$num\ge k$，则$ans$天是可行的。

因为二分与网络流独立，因此可以先做一次网络流，然后再二分。

至于退流造成的影响。
考虑退流所获得的贡献与退流的意义所对应的贡献，列出式子发现贡献和是相同的，故退流没有影响。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

typedef long long LL;
#define mp make_pair
#define pii pair<int,int>

inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}

const int maxn=1005;

struct Edge {
	int from,to,cap,flow,cost;
	Edge(int x=0,int y=0,int c=0,int f=0,int co=0):from(x),to(y),cap(c),flow(f),cost(co) {}
};

vector<pii> A;

struct MinimumCost_MaximumFlow {
	int n,m;
	vector<Edge>edges;
	vector<int>G[maxn];
	bool inque[maxn];
	int a[maxn],dist[maxn],path[maxn];
	void init(int n) {
		this->n=n;
		edges.clear();
		for(int i=1; i<=n; i++)G[i].clear();
	}
	void AddEdge(int x,int y,int v,int f) {
		edges.push_back(Edge(x,y,v,0,f));
		edges.push_back(Edge(y,x,0,0,-f));
		m=edges.size();
		G[x].push_back(m-2);
		G[y].push_back(m-1);
	}
	bool bellmanford(int s,int t) {
		for(int i=1; i<=n; i++)dist[i]=INT_MAX;
		memset(inque,0,sizeof(inque));
		queue<int>Q;
		Q.push(s);
		dist[s]=path[s]=0;
		a[s]=INT_MAX;
		while(!Q.empty()) {
			int Now=Q.front();
			Q.pop();
			inque[Now]=0;
			for(int id:G[Now]) {
				Edge& e=edges[id];
				int Next=e.to;
				if(e.cap>e.flow&&dist[Next]>dist[Now]+e.cost) {
					dist[Next]=dist[Now]+e.cost;
					path[Next]=id;
					a[Next]=min(a[Now],e.cap-e.flow);
					if(!inque[Next]) {
						Q.push(Next);
						inque[Next]=1;
					}
				}
			}
		}
		if(dist[t]==INT_MAX)return false;
		for(int Now=t; Now!=s; Now=edges[path[Now]].from) {
			edges[path[Now]].flow+=a[t];
			edges[path[Now]^1].flow-=a[t];
		}
		return true;
	}
	void maxflow(int s,int t) {
		while(bellmanford(s,t))A.push_back(mp(dist[t],a[t]));
	}
} mcmf;

int n,m,k,x[5005],y[5005],v[5005];

bool Check(int ans) {
	LL num=k;
	for(pii x:A)num-=(LL)(ans-x.first+1)*x.second;
	return num<=0;
}

int main() {
	while(~scanf("%d%d%d",&n,&m,&k)) {
		for(int i=1; i<=m; i++) {
			x[i]=Get_Int()+1;
			y[i]=Get_Int()+1;
			v[i]=Get_Int();
		}
		if(!k) {
			puts("0");
			continue;
		}
		mcmf.init(n);
		for(int i=1; i<=m; i++)mcmf.AddEdge(x[i],y[i],v[i],1);
		A.clear();
		mcmf.maxflow(1,n);
		int Left=1,Right=n+k;
		while(Left<=Right) {
			int mid=(Left+Right)>>1;
			if(Check(mid))Right=mid-1;
			else Left=mid+1;
		}
		if(Left==n+k+1)puts("No solution");
		else printf("%d\n",Left);
	}
	return 0;
}