TLE #10,WA #13。
用的链式前向星建图,对着老师的代码写的,好像和题解区的建边方法有些不一样。
#include<cstdio>
#include<cstring>
#include<queue>
#include<iostream>
#define int long long
using namespace std;
const int N=1e4+10,M=1e5+10; int s,t,cnt=1,h[N],level[N];
struct Edge { int v,c,f,nxt; }e[M<<1];
void add(int u,int v,int w) { e[++cnt]=(Edge){v,w,0,h[u]},h[u]=cnt,e[++cnt]=(Edge){u,0,w,h[v]},h[v]=cnt; }
bool bfs() {
memset(level,0,sizeof(level)),level[s]=1; queue<int>q; q.push(s);
while(!q.empty()) {
int u=q.front(); q.pop();
for(int i=h[u];i;i=e[i].nxt) {
int v=e[i].v,c=e[i].c,f=e[i].f;
if(!level[v]&&c>f) level[v]=level[u]+1,q.push(v);
}
}
return level[t];
}
int dfs(int u,int cp) {
if(u==t) return cp;
int t=cp;
for(int i=h[u];i&&t;i=e[i].nxt) {
int v=e[i].v,c=e[i].c,f=e[i].f;
if(level[v]==level[u]+1&&c>f) {
int k=dfs(v,min(t,c-f));
e[i].f+=k,e[i^1].f+=k,t-=k;
}
}
return cp-t;
}
signed main() {
int n,m,u,v,w; scanf("%lld %lld %lld %lld",&n,&m,&s,&t);
while(m--) scanf("%lld %lld %lld",&u,&v,&w),add(u,v,w);
int sum=0;
while(bfs()) sum+=dfs(s,2147483647);
printf("%lld",sum);
return 0;
}