【FJWC2019】最短路（最小割）（二分答案）

给你一张 n 个点 m 条边的无向图，走过每条边都需要花费 1 秒。

给你一个整数 k ，请你选择至多 k 个点，令经过这些点也需要花费 1 秒，使得从点 0 走到点 n−1 的最短时间最大。

输出这个最大值。

注意，不能选择点 0 或点 n−1 。

对于全部数据， 2 ≤ n ≤ 100 , 1 ≤ m ≤ n × ( n − 1 ) / 2 , 0 ≤ k ≤ n 2≤n≤100,1≤m≤n×(n−1)/2,0≤k≤n 2≤n≤100,1≤m≤n×(n−1)/2,0≤k≤n。

对于 30 30 30% 的数据，保证答案不超过 k=0 时的答案+1。

题解：

正解跑不过乱搞系列。

首先二分答案 m i d mid mid，建立分层图，分 0 0 0到 m i d mid mid一共 m i d + 1 mid+1 mid+1层，一个点 u u u在同层中拆分为两个点， s u s_u su​和 t u t_u tu​。

同层中 s u s_u su​向 t u t_u tu​连容量为 1 1 1的边，该层 s u s_u su​向下一层 t u t_u tu​连容量为 I N F INF INF的边。

对于每条边 ( u , v ) (u,v) (u,v)，连 t u t_u tu​到下一层 s v s_v sv​容量为 I N F INF INF的边， t v t_v tv​到下一层 s u s_u su​同理。

随后每一层的 s n s_n sn​到下一层 s n s_n sn​连容量为 I N F INF INF的边。

从第 0 0 0层 t 1 t_1 t1​号点向第 m i d mid mid层 s n s_n sn​跑最小割，最小割大小即为让最短路达到 m i d mid mid需要指定的最少点数。

正确性显然。

代码：

#include<bits/stdc++.h>
#define ll long long
#define re register
#define gc get_char
#define cs const

namespace IO{
	inline char get_char(){
		static cs int Rlen=1<<22|1;
		static char buf[Rlen],*p1,*p2;
		return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,Rlen,stdin),p1==p2)?EOF:*p1++;
	}
	
	template<typename T>
	inline T get(){
		char c;
		while(!isdigit(c=gc()));T num=c^48;
		while(isdigit(c=gc()))num=(num+(num<<2)<<1)+(c^48);
		return num;
	}
	inline int getint(){return get<int>();}
}
using namespace IO;

using std::cerr;
using std::cout;

cs int N=105,M=N*N,INF=0x7ffffff;

int st[N<<1][N],ed[N<<1][N],cnt;

int S,T;
namespace NetWork{
	cs int N=::N*::N<<2;
	
	struct edge{
		int to,cap,rev;
		edge(int _to,int _cap,int _rev):to(_to),cap(_cap),rev(_rev){}
	};
	
	std::vector<edge> G[N];
	typedef std::vector<edge>::iterator iter;
	iter cur[N];
	
	inline void addedge(int u,int v,int val){
		G[u].push_back(edge(v,val,G[v].size()));
		G[v].push_back(edge(u,0,G[u].size()-1));
	}
	
	bool finished;
	int lev[N],gap[N];
	inline bool BFS(){
		memset(lev+1,0,sizeof(int)*cnt);
		memset(gap+1,0,sizeof(int)*cnt);
		std::queue<int> q;q.push(T);
		lev[T]=gap[1]=1;
		while(!q.empty()){
			int u=q.front();q.pop();cur[u]=G[u].begin();
			for(edge &e:G[u])if(!lev[e.to])
			++gap[lev[e.to]=lev[u]+1],q.push(e.to);
		}
		return lev[S]==0;
	}
	
	int dfs(int u,int flow){
		if(u==T)return flow;
		int ans=0;
		for(iter &e=cur[u];e!=G[u].end();++e)
		if(e->cap&&lev[e->to]+1==lev[u]){
			int delta=dfs(e->to,std::min(flow-ans,e->cap));
			e->cap-=delta;
			G[e->to][e->rev].cap+=delta;
			if((ans+=delta)==flow)return flow;
		}
		cur[u]=G[u].begin();
		if(!--gap[lev[u]])finished=true;
		++gap[++lev[u]];
		return ans;
	}
	
	inline int Flow(){
		int ans=0;finished=BFS();
		while(!finished)ans+=dfs(S,INF);
		return ans;
	}
	
	inline void clear(){for(int re i=1;i<=cnt;++i)G[i].clear();}
}

int n,m,k;
struct edge{int u,v;}E[M];

inline bool check(int lim){
	S=ed[0][1],T=st[lim][n];
	for(int re i=0;i<lim;++i){
		for(int re u=2;u<n;++u){
			NetWork::addedge(st[i][u],ed[i][u],1);
			NetWork::addedge(st[i][u],ed[i+1][u],INF);
		}
		NetWork::addedge(st[i][n],st[i+1][n],INF);
		for(int re j=1;j<=m;++j){
			int u=E[j].u,v=E[j].v;
			NetWork::addedge(ed[i][u],st[i+1][v],INF);
			NetWork::addedge(ed[i][v],st[i+1][u],INF);
		}
	}
	int res=NetWork::Flow();
	NetWork::clear();
	return res<=k;
}

signed main(){
#ifdef zxyoi
	freopen("min.in","r",stdin);
#endif
	n=getint(),m=getint(),k=getint();
	for(int re i=1;i<=m;++i)E[i]=(edge){getint()+1,getint()+1};
	for(int re i=0;i<=n*2;++i)for(int re j=1;j<=n;++j)st[i][j]=++cnt,ed[i][j]=++cnt;
	int l=0,r=2*n,mid,ans;
	while(l<=r)check(mid=l+r>>1)?l=ans=mid+1:r=mid-1;
	cout<<ans<<"\n";
	return 0;
}