前置知识:
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;
}
标签:Pairs,return,int,题解,Flow,flow,res,dinic,fff
From: https://www.cnblogs.com/LZMkingNB/p/17686001.html