图论：网络流最大流EK算法

/*时间复杂度:O(N*M*M)*/#include <bits/stdc++.h>using namespace std;typedef long long ll;const int inf=0x3f3f3f3f;const int maxn=210;const int maxm=5e3+10;int n,m,s,t;ll maxflow = 0,dis[maxn];struct edge{int v,next;ll c;}e[maxm<<2];int head[maxn],cnt=0;int pre[maxn];//pre存上一个点bool vis[maxn];int flag[maxn][maxn];void add(int u,int v,ll c){e[cnt].v=v;e[cnt].c=c;e[cnt].next=head[u];head[u]=cnt++;}bool bfs(int s,int t){for (int i=1;i<=n;i++) vis[i]=0;dis[s]=inf;vis[s]=1;queue<int> q;q.push(s);while(!q.empty()){int u=q.front();q.pop();for (int i=head[u];~i;i=e[i].next){int v=e[i].v;ll c=e[i].c;// cout<<\"c = \"<<c<<endl;if(c>0 && !vis[v]){dis[v]=min(dis[u],c);// cout<<\"disv = \"<<dis[v]<<endl;pre[v] = i;q.push(v);vis[v]=1;if(v==t) return 1;//找到了一条增广路}}}return 0;}void update(int s,int t){int x=t;while(x!=s){int v=pre[x];e[v].c-=dis[t];e[v^1].c+=dis[t];x=e[v^1].v;}maxflow+=dis[t];}void EK(){while(bfs(s,t)){update(s,t);}}int read(){int x=0,f=1;char ch=getchar();while (ch<\'0\' || ch>\'9\'){if (ch==\'-\') f=-1;ch=getchar();}while (ch>=\'0\' && ch<=\'9\'){x=x*10+ch-48;ch=getchar();}return x*f;}ll readll(){ll x=0,f=1;char ch=getchar();while (ch<\'0\' || ch>\'9\'){if (ch==\'-\') f=-1;ch=getchar();}while (ch>=\'0\' && ch<=\'9\'){x=x*10+ch-48;ch=getchar();}return x*f;}int main(){cin>>n>>m>>s>>t;cnt=0;for (int i=1;i<=n;i++) head[i] = -1;for (int i=1;i<=m;i++){int u,v;ll c;u=read();v=read();c=readll();add(u,v,c);add(v,u,0);}EK();printf(\"%lld\\n\",maxflow);return 0;}