代码如下,码风比较怪,求谅解。 洛谷模板55,USACO模板爆零,求调。
#include<bits/stdc++.h>
#define int long long
#define to e[i].v
using namespace std;
int n,m,s,t,maxf,cnt=1,lst[201],pre[201],flow[201],hd[201];
bool vis[201],f[201][201];
struct Edge{
int v,nxt,flow;
}e[10003];
void addedge(int u,int v,int w){
e[++cnt].v=v; e[cnt].nxt=hd[u];
e[cnt].flow=w; hd[u]=cnt;
}
bool spfa(){
queue<int>q; q.push(s);
memset(vis,0,sizeof(vis));
vis[s]=1; flow[s]=1145141919810;
while(!q.empty()){
int u=q.front(); q.pop();
for(int i=hd[u];i;i=e[i].nxt){
if(e[i].flow<=0) continue;
if(vis[to]) continue;
pre[to]=u; lst[to]=i;
flow[to]=min(flow[u],e[i].flow);
q.push(to); vis[to]=1;
if(to==t) return 1;
}
}
return 0;
}
void maxflow(){
while(spfa()){
int now=t;
while(now!=s){
e[lst[now]].flow-=flow[t];
e[lst[now]+1].flow+=flow[t];
now=pre[now];
}
maxf+=flow[t];
}
}
signed main(){
cin>>n>>m>>s>>t;
for(int i=1;i<=m;i++){
int t1,t2,t3; cin>>t1>>t2>>t3;
if(!f[t1][t2]){
addedge(t1,t2,t3);
addedge(t2,t1,0);
f[t1][t2]=cnt;
}
else e[cnt-1].flow+=t3;
}
maxflow();
cout<<maxf<<endl;
}