一道神奇的 $\texttt{Tarjan}$ 题目或者 最小割树 的简单题。
题目链接:QuestOJ 2136。
题目好像是来自 福建省长乐第一中学 2017.06.24。
题目
题目描述
给定一张 $n$ 个点 $m$ 条边的无向图,点从 $1$ 开始编号,保证所有点的度数都不超过 $3$。
现在假定每条边的容量都为 $1$,请你求出任意两点间的最大流。为了方便,你只需要输出所有点对 $(a,b)(a<b)$ 间最大流的和。
数据范围
变量 | 数据范围 |
---|---|
$n$ | $1\leq n\leq 3000$ |
$m$ | $0\leq m\leq\lfloor\dfrac{3n}{2}\rfloor$ |
时空限制
题目 | 时间限制 | 空间限制 |
---|---|---|
QuestOJ 2136 | $2\text{s}$ | $256\text{MiB}$ |
题解
附上官方题解:
思路
这道题的正解是 $\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;
}
近期评论