zixi @ 2019-08-09 11:03:11
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e4+10;
const int inf=0x3f3f3f3f;
int n,m,s,t;
int liu[maxn][maxn],rong[maxn][maxn];
int p[maxn],pre[maxn];
int maxsum;
void inter(){
queue<int>st;
while(1){
memset(p,0,sizeof(p));
p[s]=inf;
st.push(s);
while(!st.empty()){
int ans=st.front();st.pop();
for(int i=1;i<=n;i++){
if(!p[i]&&rong[ans][i]>liu[ans][i]){
p[i]=min(p[ans],rong[ans][i]-liu[ans][i]);
pre[i]=ans;
st.push(i);
}
}
}
if(!p[t]){
break;
}
maxsum+=p[t];
int temp=t;
while(pre[temp]){
liu[pre[temp]][temp]+=p[t];
liu[temp][pre[temp]]-=p[t];
temp=pre[temp];
}
}
}
int main()
{
cin>>n>>m>>s>>t;
int x,y,z;
for(int i=1;i<=m;i++){
cin>>x>>y>>z;
rong[x][y]+=z;
}
inter();
cout<<maxsum<<endl;
}
by 挪威的森林 @ 2019-09-23 11:22:28
这个东西算法复杂度太大了,数组1e8也开不下啊。