题解：AT_abc397_g [ABC397G] Maximize Distance

这里有一个不用二分的做法。

首先我们枚举答案

d

，同其他题解，当

d=1

时，答案就为原图的最小割。

我先抛出我的建图，正确性一会再讲。

对于一个 $d$ ，我们首先建出 $d$ 个题目中的图，所有边容量都为 $1$ 。
然后源点 $S$ 向每个图中的点 $1$ 都连一条容量为 $\inf$ 的边。
再将每个图中的点 $N$ 都向汇点 $T$ 连一条容量为 $\inf$ 的边。
最后对于原图的每一条边 $(u,v)$ 和 $1\leqslant i<d$ 的每个 $i$ ，将第 $i$ 个图的点 $u$ 向第 $i+1$ 个图的点 $v$ 连一条容量为 $inf$ 的边。

相信前三种边大家都很容易理解，并且也知道最后一种边是为了使每条边至多只割一次。

考虑连第四种边的正确性。

给一个图：

其中

u

和

v

是一个图，剩下四个点是另一个图。

考虑如果

(u,v)

在上一个图被割了，那么这个图再割

(u_2,v_2)

也没用了，因为后面还有一个或多个

(x,y)

割掉才能使

S

与

T

不连通，那么

(u_2,v_2)

割了不如不割。

所以就可以使每条边至多只割一次。

最后，由于一个

d

可以从

d-1

的残量网络加一些边而来，而不用重新建图，所以就相当于跑了一次

n^2

个点，

nm

条边的 dinic，但会多一些常数，所以时间复杂度为

O(n^5m)

，但由于是边权只有

1

或

\inf

，于是常数很小，最慢的测试点跑了不到 5ms。

code

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int inf=1e7;
int n,m,k;
int h[100010],cnt=1;
struct node{
	int to,next,flow;
}edge[100010];
void add(int x,int y,int z){
	edge[++cnt]={y,h[x],z},h[x]=cnt;
	edge[++cnt]={x,h[y],0},h[y]=cnt;
}
int s,t;
int dis[100010],c[100010];
bool bfs(){
	for(int i=s;i<=t;i++) dis[i]=0,c[i]=h[i];
	queue<int> q;
	q.push(s),dis[s]=1;
	while(!q.empty()){
		int x=q.front();q.pop();
		for(int i=h[x];i;i=edge[i].next){
			int v=edge[i].to;
			if(!dis[v]&&edge[i].flow){
				dis[v]=dis[x]+1;
				q.push(v);
			}
		}
	}
	return dis[t]!=0;
}
int dfs(int x,int limit){
	if(!limit||x==t) return limit;
	int res=0;
	for(int&i=c[x];i;i=edge[i].next){
		int v=edge[i].to;
		if(dis[v]==dis[x]+1&&edge[i].flow){
			int p=dfs(v,min(limit-res,edge[i].flow));
			res+=p,edge[i].flow-=p;
			edge[i^1].flow+=p;
		}
	}
	if(res==limit) dis[x]=0;
	return res;
}
int xx[120],yy[120];
int dinic(){
	int sum=0;
	while(bfs()){
		while(int l=dfs(s,inf)) sum+=l;
	}
	return sum;
}
signed main(){
	cin>>n>>m>>k;
	t=(n+2)*n+1;
	add(s,1,inf),add(n,t,inf);
	for(int i=1;i<=m;i++){
		cin>>xx[i]>>yy[i];
		add(xx[i],yy[i],1);
	}
	int sum=dinic();
	if(sum>k) return cout<<0,0;
	for(int i=2;i<=n+2;i++){
		for(int j=1;j<=m;j++){
			add(xx[j]+(i-2)*n,yy[j]+(i-1)*n,inf);
			add(xx[j]+(i-1)*n,yy[j]+(i-1)*n,1);
		}
		add(s,(i-1)*n+1,inf),add(i*n,t,inf);
		sum+=dinic();//注意是+=
		if(sum>k) return cout<<i-1,0;
	}
	return 0; 
}

题解：AT_abc397_g [ABC397G] Maximize Distance

文章操作

code

相关推荐

评论

题解：AT_abc397_g [ABC397G] Maximize Distance