题解：AT_abc397_g [ABC397G] Maximize Distance

emmoy · 2025-03-20 22:13:53 · 题解

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

首先我们枚举答案 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

#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; 
}