【板子】网络流（Dinic）

#include<bits/stdc++.h>
using namespace std;

const int N = 205;
const int M = 205;

const int INF = 0x3f3f3f3f;

int edgeid=2;
int head[N];
struct edge
{
    int v,w,nxt;
}e[M*2];
inline void addedge(int u,int v,int w)
{
    e[edgeid].v=v;
    e[edgeid].w=w;
    e[edgeid].nxt=head[u];
    head[u]=edgeid;
    edgeid++;
}

int n,m;
int ans;
int cur[N];
int dis[N];

int st,ed;

queue<int> q;
bool Bfs()
{
    while(!q.empty()) q.pop();
    for(int i=1;i<=n;i++)
    {
        cur[i]=head[i]; //重置当前弧优化
        dis[i]=0; //重置距离
    }
    q.push(st);
    dis[st]=1;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=head[u];i;i=e[i].nxt)
        {
            int v=e[i].v;
            if(e[i].w && !dis[v]) 
            {
                dis[v]=dis[u]+1;
                if(v==ed) return 1;
                q.push(v);
            }
        }
    }
    return 0;
}

int Dfs(int u,int rst)
{
    if(!rst || u==ed) return rst;
    int sum=0;
    for(int i=cur[u];i;i=e[i].nxt) //当前弧优化 确保时间复杂度O(n^2 m)
    {
        int v=e[i].v;
        cur[u]=i;
        int f;
        if(dis[v]==dis[u]+1 && (f=Dfs(v,min(rst,e[i].w))))
        {
            e[i].w-=f;
            e[i^1].w+=f;
            sum+=f;
            rst-=f;
            if(rst==0) break;//余量优化 常数
        }
    }
    if(sum==0) dis[u]=0;//废点优化 常数
    return sum;
}

void Dinic()
{
    while(Bfs())
    {
        ans+=Dfs(1,INF);
    }
}

int main()
{
    cin>>m>>n;
    st=1,ed=n;
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        addedge(u,v,w);
        addedge(v,u,0);
    }
    Dinic();
    cout<<ans;
    return 0;
}