526互联

All Pairs Maximum Flow题解

发布时间 2023-09-07 20:39:19作者: 镜予歌

前置知识：

1. P3376 【模板】网络最大流

2.P4897 【模板】最小割树（Gomory-Hu Tree）

Ebola 有一句很著名的话

如果你乱搞过了我请你抽烟

那么这道题肯定不能普通的 dinic 直接水过去，不然就不是紫题了，那么直接祭出最小割树，复杂度 \(O(Tn^3m)\)，但是因为 dinic 跑不满，所以是可以过的。

还有就是要注意 \(0\) 的情况，我的代码里特判了一下。最后就是要注意空格在行末不能输出。

#include<bits/stdc++.h>
#define int long long 
int max(int a,int b){return a>b?a:b;}
int min(int a,int b){return a<b?a:b;}

const int M=80010;
const int N=410;
const int INF=1e15;

int n,S,T;
int d[M],now[M];
int tmp1[M],tmp2[M];
int node[M];
int anss[N][N];

struct liststar
{
    int u,v,w,nxt;
}e[M];
int cnt=1,head[M];
void add(int u,int v,int w){e[++cnt].nxt=head[u];head[u]=cnt;e[cnt].v=v;e[cnt].w=w;}
void addd(int u,int v,int w){add(u,v,w);add(v,u,0);}
void init(){for(int i=1;i<=cnt;i+=2)e[i].w+=e[i^1].w,e[i^1].w=0;}

bool bfs()
{
    std::queue<int>q;
    memset(d,0,sizeof(d));
    d[S]=1;now[S]=head[S];
    q.emplace(S);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=head[u],y;i;i=e[i].nxt)
            if(e[i].w && !d[y=e[i].v])
            {
                d[y]=d[u]+1;
                now[y]=i;
                q.emplace(y);
                if(y==T)return true;
            }
    }
    return false;
}

int fff(int x,int flow)
{
    if(x==T)return flow;
    int res=flow;
    for(int i=head[x],y;i && res;i=e[i].nxt)
    {
        now[x]=i;
        if(e[i].w && d[y=e[i].v]==d[x]+1)
        {
            int t=fff(y,min(e[i].w,res));
            if(!t)d[y]=0;
            res-=t;e[i].w-=t;e[i^1].w+=t;
        }
    }
    return flow-res;
}

int dinic()
{
    init();
    int res,maxn=0;
    while(bfs())while(res=fff(S,INF))maxn+=res;
    return maxn;
}

void work(int l,int r)
{
    if(l==r)return ;
    S=node[l];T=node[l+1];
    int t=dinic();
    anss[S][T]=anss[T][S]=t;
    int ss=S,tt=T,cnt1=0,cnt2=0;
    for(int i=l;i<=r;i++)
        if(d[node[i]])tmp1[++cnt1]=node[i];
        else tmp2[++cnt2]=node[i];
    for(int i=1;i<=cnt1;i++)node[i+l-1]=tmp1[i];
    for(int i=1;i<=cnt2;i++)node[i+l-1+cnt1]=tmp2[i];
    work(l,l+cnt1-1);
    work(l+cnt1,r);
    for(int i=1;i<=cnt1;i++)
        for(int j=1;j<=cnt2;j++)
        {
            int b=node[i+l-1],w=node[j+l-1+cnt1];
            anss[b][w]=anss[w][b]=min(min(anss[b][ss],anss[ss][tt]),anss[tt][w]);
        }
}

int read()
{
    int x=0,s=1;
    char ch=getchar();
    for(;!isdigit(ch);ch=getchar())if(ch=='-')s=-1;
    for(;isdigit(ch);ch=getchar())x=x*10+ch-48;
    return x*s;
}

signed main()
{
    int tot=0;
    int TT=read();
    while(TT--)
    {
        printf("Case #%lld:\n",++tot);
        for(int i=0;i<N;i++)
            for(int l=0;l<N;l++)anss[i][l]=INF;
        memset(e,0,sizeof(e));
        memset(head,0,sizeof(head));
        memset(now,0,sizeof(now));
        cnt=1;
        n=read();
        if(n==0)continue;
        for(int i=1;i<=n;i++)
            for(int l=1;l<=n;l++)
            {
                int x=read();
                addd(i,l,x);
            }
        for(int i=1;i<=n;i++)node[i]=i;
        work(1,n);
        for(int i=1;i<=n;i++)
        {
            for(int l=1;l<=n;l++)
            {
                if(anss[i][l]==INF)anss[i][l]=0;
                printf("%lld",anss[i][l]);
                if(l!=n)printf(" ");
            }
            puts("");
        }
    }
    return 0;
}