一道神奇的 $\texttt{Tarjan}$ 题目或者 最小割树 的简单题。

题目链接：QuestOJ 2136。

题目好像是来自 福建省长乐第一中学 2017.06.24。

题目

题目描述

给定一张 $n$ 个点 $m$ 条边的无向图，点从 $1$ 开始编号，保证所有点的度数都不超过 $3$。

现在假定每条边的容量都为 $1$，请你求出任意两点间的最大流。为了方便，你只需要输出所有点对 $(a,b)(a<b)$ 间最大流的和。

数据范围

时空限制

题解

附上官方题解：

思路

这道题的正解是 $\texttt{Tarjan}$（比赛的时候根本没有想到会是它）。

直接写的最小割树暴力，结果跑得很快。

代码

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#define INF 0X3F3F3F3F
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
    reg bool f=false;
    reg char ch=getchar();
    reg int res=0;
    while(ch<'0'||'9'<ch)f|=(ch=='-'),ch=getchar();
    while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
    return f?-res:res;
}

const int MAXN=3000+5;
const int MAXLOG2N=12+1;
const int MAXM=3*MAXN+5;

inline void Read(void);
inline void Work(void);

int main(void){
    Read();
    Work();
    return 0;
}

struct Graph{
    int cnt,head[MAXN],to[MAXM<<1],w[MAXM<<1],Next[MAXM<<1];
    inline void Add_Edge(reg int u,reg int v,reg int len){
        Next[++cnt]=head[u];
        to[cnt]=v;
        w[cnt]=len;
        head[u]=cnt;
    }
    inline void Add_Tube(reg int u,reg int v,reg int len){
        Add_Edge(u,v,len);
        Add_Edge(v,u,len);
        return;
    }
};

int n,m;
Graph G,T;

inline void Read(void){
    n=read(),m=read();
    G.cnt=1;
    for(reg int i=1;i<=m;++i){
        static int u,v;
        u=read(),v=read();
        G.Add_Tube(u,v,1);
    }
    return;
}

int dep[MAXN];
queue<int> Q;

inline bool BFS(int s,reg int t,Graph& G){
    memset(dep,-1,sizeof(dep));
    while(!Q.empty())Q.pop();
    dep[s]=1,Q.push(s);
    while(!Q.empty()){
        reg int ID=Q.front();
        Q.pop();
        for(reg int i=G.head[ID];i;i=G.Next[i])
            if(dep[G.to[i]]==-1&&G.w[i]>0){
                dep[G.to[i]]=dep[ID]+1;
                Q.push(G.to[i]);
            }
    }
    return dep[t]!=-1;
}

int cur[MAXN];

inline int DFS(reg int ID,reg int t,reg int lim,Graph& G){
    if(ID==t)
        return lim;
    reg int flow=0;
    for(reg int &i=cur[ID];i;i=G.Next[i])
        if(dep[G.to[i]]==dep[ID]+1&&G.w[i]>0){
            reg int f=DFS(G.to[i],t,min(lim-flow,G.w[i]),G);
            if(f){
                flow+=f;
                G.w[i]-=f;
                G.w[i^1]+=f;
                if(flow==lim)
                    break;
            }
        }
    return flow;
}

inline int Dinic(reg int s,reg int t,Graph& G){
    reg int res=0;
    while(BFS(s,t,G)){
        memcpy(cur,G.head,sizeof(G.head));
        res+=DFS(s,t,INF,G);
    }
    return res;
}

int W[MAXM<<1];
bool vis[MAXN];
int p[MAXN];

inline void DFS(reg int ID,Graph& G){
    vis[ID]=true;
    for(reg int i=G.head[ID];i;i=G.Next[i])
        if(!vis[G.to[i]]&&G.w[i]>0)
            DFS(G.to[i],G);
    return;
}

int F[MAXN][MAXN];

inline void DFS(const int& ID,const int& fa,const int& Min,const int& root,Graph& T){
    F[root][ID]=F[ID][root]=Min;
    for(reg int i=T.head[ID];i;i=T.Next[i])
        if(T.to[i]!=fa)
            DFS(T.to[i],ID,min(Min,T.w[i]),root,T);
    return;
}

inline void Work(void){
    for(reg int i=1;i<=G.cnt;++i)
        W[i]=G.w[i];
    for(reg int i=2;i<=n;++i)
        p[i]=1;
    for(reg int i=2;i<=n;++i){
        reg int s=i,t=p[i];
        for(reg int j=1;j<=G.cnt;++j)
            G.w[j]=W[j];
        reg int ans=Dinic(s,t,G);
        memset(vis,false,sizeof(vis));
        DFS(s,G);
        T.Add_Tube(s,t,ans);
        for(reg int j=i;j<=n;++j)
            if(vis[j]&&p[j]==t)
                p[j]=s;
    }
    reg ll ans=0;
    for(int i=1;i<=n;++i){
        DFS(i,0,INF,i,T);
        for(reg int j=i+1;j<=n;++j)
            ans+=F[i][j];
    }
    printf("%lld\n",ans);
    return;
}