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

/*时间复杂度：O(N*N*M)*/#include <bits/stdc++.h>using namespace std;const int maxn=210;const int maxm=5e3+10;typedef long long ll;const int inf=0x3f3f3f3f;int head[maxn],cnt=0;struct edge{int v,next;int c;}e[maxm<<2];int n,m,s,t;int dis[maxn];int cur[maxn];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;}void add(int u,int v,int 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++){dis[i]=-1;}dis[s]=0;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;int c=e[i].c;if(c>0 && dis[v]==-1){dis[v]=dis[u]+1;q.push(v);}}}return dis[t]!=-1;}int dfs(int u,int t,int flow){if(u==t) return flow;int delta=flow;for (int i=head[u];~i;i=e[i].next){int v=e[i].v;int c=e[i].c;if(c>0 && dis[v]==dis[u]+1){int d=dfs(v,t,min(c,delta));if(!d) dis[v]=0;//这里加优化,剪枝e[i].c-=d;e[i^1].c+=d;delta-=d;if(delta == 0) break;}}return flow-delta;}ll dinic(int s,int t){ll maxflow = 0;while(bfs(s,t)){maxflow+=dfs(s,t,inf);}return maxflow;}int main(){cin>>n>>m>>s>>t;for (int i=1;i<=n;i++) head[i]=-1;cnt=0;for (int i=1;i<=m;i++){int u,v;int c;//		scanf(\"%d%d%d\",&u,&v,&c);u=read();v=read();c=read();add(u,v,c);add(v,u,0);}ll maxflow = dinic(s,t);cout<<maxflow<<endl;return 0;}