网络流

就是单纯的,,emm。。贴个板子

一个在loj的辣鸡数据下可以过的板子

loj #101. 最大流

lbc教我们要把边排序,这样会快好多因为空间是连续的。、

然鹅蒟蒻自带一堆bug和巨大常数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<bits/stdc++.h>
#define int long long
inline int read(){
char c=getchar();while (c!='-'&&(c<'0'||c>'9'))c=getchar();
int k=1,kk=0;if (c=='-')c=getchar(),k=-1;
while (c>='0'&&c<='9')kk=kk*10+c-'0',c=getchar();return kk*k;
}using namespace std;
struct lsg{int x,y,z,oh;}a[10000000];
int n,m,S,T,d[1000010],l,r,flag[10000000],de[1000010],f[1000010],kk,kkk,ans,x,y,z;
bool pd(lsg x,lsg y){return x.x<y.x;}
bool bfs(int S,int T){
memset(de,10,sizeof(de));de[S]=1;d[1]=S;l=0;r=1;
while (l<r){
++l;if (d[l]==T)return 1;flag[d[l]]=0;
for (int i=f[d[l]];a[i].x==d[l];i++)
if (a[i].z&&de[a[i].y]>de[d[l]]+1)d[++r]=a[i].y,de[a[i].y]=de[d[l]]+1;
}return 0;
}int solve(int d,int mx){
if (d==T)return mx;int sum=0;
for (int i=f[d];a[i].x==d;i++)
if (a[i].z&&de[a[i].y]==de[d]+1&&!flag[a[i].y]){
int k=solve(a[i].y,min(a[i].z,mx));
sum+=k;mx-=k;a[i].z-=k;a[a[i].oh].z+=k;
if (!mx)break;
}if (sum==0)flag[d]=1;
return sum;
}void Dinic(int S,int T){
sort(a+1,a+1+kk,pd);for (int i=1;i<=kk;i++){
if (flag[a[i].oh])a[flag[a[i].oh]].oh=i,a[i].oh=flag[a[i].oh];
else flag[a[i].oh]=i;
}for (int i=kk;i>=1;i--)f[a[i].x]=i;
memset(flag,0,sizeof(flag));
while (bfs(S,T))ans+=solve(S,1e15);
}int add(int x,int y,int z){kkk++;a[++kk].x=x;a[kk].y=y;a[kk].z=z;a[kk].oh=kkk;a[++kk].x=y;a[kk].y=x;a[kk].z=0;a[kk].oh=kkk;}
signed main(){
n=read();m=read();S=read();T=read();
for (int i=1;i<=m;i++){
x=read();y=read();z=read();add(x,y,z);
}Dinic(S,T);cout<<ans<<endl;
}
分享到