题解：SP287 NETADMIN - Smart Network Administrator

· · 题解

网络流水题。

题意

多测，每次给定 n 个点 m 条边的无向图，并给出 k 个关键节点，找出每个关键节点到 1 的一条路径，求图中被这些路径经过次数最多的边，被经过的次数是多少。

解析

不难想到网络流，但是这个最大经过次数最小很难直接算。于是想到二分。二分出每条边的容量 mid，每次重新建图，对于原图中的无向边都变成两条容量为 mid 的有向边。超级源点向 k 个关键节点连容量为 1 的边，汇点为 1 然后跑最大流，如果最大流等于 k 说明每个关键节点都有一条到汇点的路径，所以是合法的。
使用 Dinic 求最大流，时间复杂度：\Theta(t n^2 m \log k)，跑不满，能过。

程序

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define infll 0x3f3f3f3f3f3f3f3f
#define N 10010
#define M 500010
int n,m,k,s,t,tot=1;
int A[N],X[M],Y[M];
ll maxflow;
int Head[N],Son[M],Next[M];
ll Cap[M];
deque<int>Q;
int Cur[N];
ll Dis[N];
inline void add(int x,int y,ll z)
{
    Son[++tot]=y;
    Cap[tot]=z;
    Next[tot]=Head[x];
    Head[x]=tot;
}
bool bfs()
{
    memset(Dis,0x3f,sizeof(Dis));
    memcpy(Cur,Head,sizeof(Cur));
    Q.clear();
    Q.push_back(s);
    Dis[s]=0;
    while(!Q.empty())
    {
        int x=Q.front();
        Q.pop_front();
        for(int i=Head[x];i;i=Next[i])
        {
            int y=Son[i];
            if(Cap[i]>0&&Dis[y]==infll)
            {
                Q.push_back(y);
                Dis[y]=Dis[x]+1;
                if(y==t)return 1;
            }
        }
    }
    return 0;
}
ll dfs(int x,ll flow)
{
    if(x==t)return flow;
    ll res=0;
    for(int i=Cur[x];i&&flow;i=Next[i])
    {
        int y=Son[i];
        Cur[x]=i;
        if(Cap[i]>0&&Dis[y]==Dis[x]+1)
        {
            ll k=dfs(y,min(flow,Cap[i]));
            if(!k)Dis[y]=infll;
            Cap[i]-=k;
            Cap[i^1]+=k;
            res+=k;
            flow-=k;
        }
    }
    return res;
}
void Dinic()//网络流板子
{
    while(bfs())maxflow+=dfs(s,infll);
}
bool check(int mid)//每次重新建图跑一遍最大流
{
    tot=1;
    memset(Head,0,sizeof(Head));
    maxflow=0;
    for(int i=1;i<=k;i++)
    {
        add(s,A[i],1);
        add(A[i],s,0);
    }
    for(int i=1;i<=m;i++)
    {
        add(X[i],Y[i],mid);
        add(Y[i],X[i],0);
        add(Y[i],X[i],mid);
        add(X[i],Y[i],0);
    }
    Dinic();
    return maxflow==k;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int _;
    cin>>_;
    while(_--)
    {
        int ans=-1;
        cin>>n>>m>>k;
        s=n+1;
        t=1;
        for(int i=1;i<=k;i++)
            cin>>A[i];
        for(int i=1;i<=m;i++)
            cin>>X[i]>>Y[i];
        int l=1,r=k;
        while(l<=r)//二分答案
        {
            int mid=(l+r)>>1;
            if(check(mid))
            {
                ans=mid;
                r=mid-1;
            }
            else l=mid+1;
        }
        cout<<ans<<'\n';
    }
    return 0;
}