YCS_GG @ 2017-11-09 21:12:24
标准dinic
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
#include<cstdio>
using namespace std;
struct Edge{
int v;
int w,next;
}edge[100010];
int head[100010],level[100010];
inline void read(int &x){
x=0;
char c=getchar();
while(c<'0'||c>'9')
c=getchar();
while(c>='0'&&c<='9'){
x=(x<<3)+(x<<1)+(c^'0');
c=getchar();
}
}
int n,m,ans,num=1;
void add(int u,int v,int w){
edge[++num].v=v;
edge[num].w=w;
edge[num].next=head[u];
head[u]=num;
edge[++num].v=u;
edge[num].w=0;
edge[num].next=head[v];
head[v]=num;
}
bool bfs(int s,int t){
queue<int> q;
memset(level,0,sizeof(level));
q.push(s);
level[s]=1;
while(!q.empty()){
int qnow=q.front();
q.pop();
for(int i=head[qnow];i!=-1;i=edge[i].next){
if(!level[edge[i].v]&&edge[i].w!=0){
level[edge[i].v]=level[qnow]+1;
if(edge[i].v==t)
return true;
q.push(edge[i].v);
}
}
}
return false;
}
int dfs(int x,int maxflow,int t){
if(x==t||maxflow==0)
return maxflow;
int used=0;
for(int i=head[x];i!=-1;i=edge[i].next){
if(level[edge[i].v]==level[x]+1&&edge[i].w){
int flow=dfs(edge[i].v,min(maxflow,edge[i].w),t);
//if(flow==0)
//level[edge[i].v]=0;
used+=flow;
maxflow-=flow;
edge[i].w-=flow;
edge[i^1].w+=flow;
}
}
return used;
}
void Dinic(int s,int t){
while(bfs(s,t)){
ans+=dfs(s,0x3f3f3f3f,t);
}
}
int main(){
int s,t;
read(n);
read(m);
read(s);
read(t);
memset(head,-1,sizeof(head));
for(int i=1;i<=m;i++){
int u,v,w;
read(u);
read(v);
read(w);
add(u,v,w);
}
Dinic(s,t);
cout<<ans;
}
by ZlycerQan @ 2017-11-09 21:15:04
您数组开小了吧。。。。
by YCS_GG @ 2017-11-09 21:38:20
谢谢.......de了半天