洛谷P 3376ネットワーク最大ストリーム
ネットの流れではなく、ボードを貯めて、私のDinicはEKより倍遅く走ってもいいです.
2つの良いチュートリアルを添付します.いずれも洛谷日報EKsfcolor{blue}EK EK D i n i csfcolor{blue}Dinic Dinicから来ています.
次はコードです
EK
Dinic
2つの良いチュートリアルを添付します.いずれも洛谷日報EKsfcolor{blue}EK EK D i n i csfcolor{blue}Dinic Dinicから来ています.
次はコードです
EK
#include
#include
const int N=10010;
int n,m,l,r,t,p1,p2,x,y,c,mn,ans,v[N],last[N],Q[N];
struct node { int v,e; }pre[N];
struct Edge { int y,pre,v; }E[200010];
inline int min(int x,int y) { return (x<y?x:y); }
int bfs() {
memset(v,0,sizeof v); memset(pre,0,sizeof pre);
v[p1]=1; Q[l=r=1]=p1;
while (l<=r) {
t=Q[l]; ++l;
for (int i=last[t]; i; i=E[i].pre)
if (!v[y=E[i].y]&&E[i].v) {
pre[y]={t,i}; if (y==p2) return 1;
v[y]=1; Q[++r]=y;
}
}
return 0;
}
int main() {
scanf("%d%d%d%d",&n,&m,&p1,&p2);
for (int i=1; i<=m; ++i) {
scanf("%d%d%d",&x,&y,&c);
E[i<<1]={y,last[x],c}; last[x]=(i<<1);
E[i<<1|1]={x,last[y],0}; last[y]=(i<<1|1);
}
while (bfs()) {
mn=19260817;
for (int i=p2; i!=p1; i=pre[i].v)
mn=min(mn,E[pre[i].e].v);
for (int i=p2; i!=p1; i=pre[i].v)
E[pre[i].e].v-=mn,E[pre[i].e^1].v+=mn;
ans+=mn;
}
printf("%d
",ans);
return 0;
}
Dinic
#include
#include
const int N=10010,inf=0x3f3f3f3f;
int n,m,t1,t2,s,ans,l,r,x,y,c,last[N],v[N],dep[N],Q[N];
struct node { int y,pre,v; }E[200010];
inline int min(int x,int y) { return (x<y?x:y); }
int bfs() {
memset(dep,0x3f,sizeof dep); int t,y;
for (Q[l=r=1]=t1,dep[t1]=0; l<=r; ++l) {
v[t=Q[l]]=0;
for (int i=last[t]; i; i=E[i].pre)
if (E[i].v&&dep[y=E[i].y]>dep[t]+1)
dep[y]=dep[t]+1,v[y]||(Q[++r]=y,v[y]=1);
}
return (dep[t2]!=inf);
}
int dfs(int x,int s) {
if (x==t2) return s; int s2,y;
for (int i=last[x]; i; i=E[i].pre)
if (E[i].v&&dep[y=E[i].y]==dep[x]+1)
if (s2=dfs(y,min(E[i].v,s)))
return E[i].v-=s2,E[i^1].v+=s2,s2;
return 0;
}
int main() {
scanf("%d%d%d%d",&n,&m,&t1,&t2);
for (int i=1; i<=m; ++i) {
scanf("%d%d%d",&x,&y,&c);
E[i<<1]={y,last[x],c}; last[x]=(i<<1);
E[i<<1|1]={x,last[y],0}; last[y]=(i<<1|1);
}
while (bfs()) while (s=dfs(t1,inf)) ans+=s;
printf("%d
",ans);
return 0;
}