题解：SP287 NETADMIN - Smart Network Administrator

· · 题解

思路

注意到题面中给出的一句话“使得经过最多次数的边经过次数最少”，引导我们往二分考虑。

显然可以二分最多经过次数，下界为 1，上界为 k，然后验证在此经过次数内能否使 k 个特殊点都到达 1 号点。

考虑将经过次数限制转为流量限制，跑最大流，若最大流 f_{\max}\ge k，则可行。

使用 Dinic 跑最大流，时间复杂度 O(n^2m)，总时间复杂度 O(n^2m\log k) 且跑不满，可以通过。

代码

注意多测清空。

#include <bits/stdc++.h>
#define int long long
#define __BEGIN_MULTITEST__ \
    signed T; \
    scanf("%d",&T); \
    while(T--) \
    {
#define __END_MULTITEST__ }
using namespace std;
//using namespace __gnu_cxx;
//using namespace __gnu_pbds;
namespace Dinic
{
    int head[200005],cur[200005],d[200005];
    bool vis[200005];
    int cnt=1,n,m;
    struct node{int to,nxt,w;} e[500005];
    void initdinic() {cnt=1; memset(head,0,sizeof head); memset(vis,0,sizeof vis);}
    void add(int u,int v,int w)
    {
        e[++cnt].to=v;
        e[cnt].w=w;
        e[cnt].nxt=head[u];
        head[u]=cnt;
    }
    void AddEdge(int u,int v,int w)
    {
        add(u,v,w);
        add(v,u,0);
    }
    bool bfs(int s,int t)
    {
        for(int i=1;i<=n;i++)
            d[i]=1e18;
        queue<int> q;
        q.push(s);
        cur[s]=head[s];
        d[s]=0;
        while(!q.empty())
        {
            int tmp=q.front();
            q.pop();
            for(int i=head[tmp];i;i=e[i].nxt)
                if(e[i].w>0&&d[e[i].to]==1e18)
                {
                    q.push(e[i].to);
                    cur[e[i].to]=head[e[i].to];
                    d[e[i].to]=d[tmp]+1;
                    if(e[i].to==t)
                        return 1; 
                }
        }
        return 0;
    }
    int dfs(int u,int t,int sum)
    {
        if(u==t)
            return sum;
        int ret=0;
        for(int i=cur[u];i&&sum;i=e[i].nxt)
        {
            cur[u]=i;
            if(e[i].w>0&&d[e[i].to]==d[u]+1)
            {
                int k=dfs(e[i].to,t,min(sum,e[i].w));
                if(!k)
                    d[e[i].to]=1e18;
                e[i].w-=k;
                e[i^1].w+=k;
                ret+=k;
                sum-=k;
            }
        }
        return ret;
    }
    int s,t;
    int dinic(int &ans)
    {
        while(bfs(s,t))
            ans+=dfs(s,t,1e18);
        return ans;
    }
}
int k;
int u[200005],v[200005],spe[200005];
using namespace Dinic;
bool check(int x)
{
    initdinic();
    for(int i=1;i<=m;i++)
    {
        AddEdge(u[i],v[i],x);
        AddEdge(v[i],u[i],x);
    }
    s=n+1;
    t=1;
    for(int i=1;i<=k;i++)
        AddEdge(s,spe[i],1);
    int ans=0;
    dinic(ans);
    return ans>=k;
}
signed main()
{
    __BEGIN_MULTITEST__
    scanf("%lld%lld%lld",&n,&m,&k);
    for(int i=1;i<=k;i++)
        scanf("%lld",&spe[i]);
    for(int i=1;i<=m;i++)
        scanf("%lld%lld",&u[i],&v[i]);
    int l=1,r=k;
    while(l<=r)
    {
        int mid=l+r>>1;
        if(check(mid))
            r=mid-1;
        else
            l=mid+1;
    }
    printf("%lld\n",r+1);
    __END_MULTITEST__
    return 0;
}