View Code of Problem 3074

#include <iostream>
#include <stdio.h>
#include <map>
#include <algorithm>
#include <string.h>
using namespace std;
const int N=20010;
const int M=220010;
map<int,map<int,int> > mp;
int dis[N];
int vis[N];
int que[M];
int len;
int n;
int m;
int BFS()
{
    memset(vis,0,sizeof(vis));
    vis[0]=1;
    que[0]=0;
    len=1;
    int index=1;
    memset(dis,0,sizeof(dis));
    for(int i=0;i<len;)
    {
        int length=len;
        for(;i<length;i++)
        {
            for(map<int,int>::iterator it=mp[que[i]].begin();it!=mp[que[i]].end();it++)
            {
                if(!vis[it->first]&&it->second>0)
                {
                    vis[it->first]=1;
                    dis[it->first]=index;
                    que[len++]=it->first;
                }
            }
        }
        index++;
    }
    dis[n+1]=index;
    return 0;
}
int DFS(int u,int cur)
{
    if(u==n+1)return cur;
    int tmp=0;
    for(map<int,int>::iterator it=mp[u].begin();it!=mp[u].end();it++)
    {
        if(dis[u]<dis[it->first]&&it->second>0)
        {
            tmp=DFS(it->first,min(cur,it->second));
            if(tmp>0)
            {
                mp[u][it->first]-=tmp;
                mp[it->first][u]+=tmp;
                break;
            }
        }
    }
    return tmp;
}
int dinic()
{
    int total=0;
    int tmp=0;
    int cmp=0;
    while(1)
    {
        BFS();
        do
        {
            tmp=DFS(0,0x3f3f3f3f);
            total+=tmp;
        }while(tmp);
        if(cmp==total)break;
        else cmp=total;
    }
    return total;
}
int main()
{
    //freopen("test","r",stdin);
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        mp.clear();
        memset(dis,0,sizeof(dis));
        for(int i=1;i<=n;i++)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            mp[0][i]=a;
            mp[i][n+1]=b;
        }
        for(int i=0;i<m;i++)
        {
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            mp[a][b]=c;
            mp[b][a]=c;
        }
        int ans=dinic();
        printf("%d\n",ans);
    }
    return 0;
}