/*Dinic算法的基本思路:1.根据残量网络计算层次图。2.在层次图中使用DFS进行增广直到不存在增广路。 3.重复以上步骤直到无法增广。 残量网络:包含反向弧的有向图,Dinic要循环的,每次修改过的图都是残量网络,层次图:分层图,以[从原点到某点的最短距离]分层的图,距离相等的为一层DFS:这个就不用说了吧…增广  :在现有流量基础上发现新的路径,扩大发现的最大流量(注意:增加量不一定是这条路径的流量,而是新的流量与上次流量之差)增广路:在现有流量基础上发现的新路径.(快来找茬,和上一条有何不同?)剩余流量:当一条边被增广之后(即它是增广路的一部分,或者说增广路通过这条边),这条边还能通过的流量.反向弧:我们在Dinic算法中,对于一条有向边,我们需要建立另一条反向边(弧),当正向(输入数据)边剩余流量减少I时,反向弧剩余流量增加I*/ #include<iostream>#include<cstdio>#include<cstring>#define maxn 2010#define INF 9999185using namespace std;int head[maxn],deep[maxn],q[maxn],vis[maxn];int n,m,x,y,z,s=1,cnt,num,ans;struct node{    int u,v,next,flow;}e[maxn<<5];inline int init(){    int x=0,f=1;char c=getchar();    while(c>‘9‘||c<‘0‘){if(c==‘-‘)f=-1;c=getchar();}    while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();}    return x*f;}inline void add(int from,int to,int dis){    e[++num].v=to;    e[num].flow=dis;    e[num].next=head[from];    head[from]=num;}int BFS()//统计各点的层数 {    memset(deep,-1,sizeof deep);    int first=0,last=0;    q[last++]=1;deep[s]=0;    while(first<last)    {        int now=q[first++];        for(int i=head[now];i;i=e[i].next)        {            int v=e[i].v;            if(deep[v]==-1&&e[i].flow>0)            {                deep[v]=deep[now]+1;                if(v==m) return true;//找到终点就return true                q[last++]=v;            }        }    }    return false;}int dfs(int now,int came_flow)//now 是当前节点,came_flow是能流过来的流量,即当前点准备向外流的流量。 {    int use_flow=0;//这个点已经往外流的量     if(now==m) return came_flow;//流到终点     for(int i=head[now];i;i=e[i].next)//&&use_flow<came_flow 据说这是各优化，不懂23333     {        int v=e[i].v;        if(e[i].flow>0&&deep[v]==deep[now]+1)//往下一层         {            int min_flow=min(e[i].flow,came_flow-use_flow);//这个边是能流这个边流量还是剩下的流量            min_flow=dfs(v,min_flow);//当前增广路找到终点时的流量             use_flow+=min_flow;//用的加上             e[i].flow-=min_flow;//当前流量减去用的             e[i^1].flow+=min_flow;//反向弧加上用的         }    }    if(!use_flow)//优化 如果找到到不了汇点的点,就不管它。       deep[now]=-1;    return use_flow;}int Dicnic(int s,int t){    int tot=0;    while(BFS())//如果有增广路     {        ans=dfs(s,INF);         while(ans){tot+=ans;ans=dfs(s,INF);}//就一直流啊流啊流     }    return tot;}int main(){    n=init();m=init();    for(int i=1;i<=n;i++)    {        x=init();y=init();z=init();        add(x,y,z);add(y,x,0);    }    ans=0;    ans=max(ans,Dicnic(1,m));    printf("%d\n",ans);    return 0;}