学步园

#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int INF = 100000000;
const int nmax = 20000+100;
const int mmax = 1000000;

struct EDGE{
    int u,v,cap,flow;
    int next;
    EDGE(int a=0,int b=0,int c=0,int d=0):
        u(a),v(b),cap(c),flow(d){}
};

struct EDGEList{
    int start[nmax];
    int last[nmax];
    int t;
    EDGE arc[mmax];
    void clear(){//清除操作
        t=0;
        for(int i=0;i<nmax;i++){
            last[i]=-1;
        }
    }
    void Push_back(EDGE edge){//追加操作
        edge.next=-1; arc[t]=edge;
        if(last[edge.u]!=-1) arc[last[edge.u]].next=t;
        else start[edge.u]=t;
        last[edge.u]=t;  t++;
    }
    void add_arc(EDGE edge){//创建双向弧
        Push_back(edge);
        Push_back(EDGE(edge.v,edge.u,edge.cap));
    }
}net;

int q[2][nmax];//数组模拟滚动数组
int q1[2],q2[2],qnow;//模拟队列

void push_queue(int a){//入队列
    q[qnow][q2[qnow]++]=a;
}

int pop_queue(){//出队列
    return q[qnow^1][q1[qnow^1]++];
}

void switch_queue(){//滚动数组
    qnow^=1;
    q1[qnow]=0;
    q2[qnow]=0;
}

bool empty_queue(){//判断队列是否为空
    return q1[qnow^1]>=q2[qnow^1];
}

int size_queue(){//队列大小
    return q2[qnow^1]-q1[qnow^1];
}

int n,m;
int dis[nmax];//层次网络（距离标号）
int path[nmax],deep;//路径
int cur[nmax];

bool Bfs(){//Bfs构建层次网络
    int l,u,v;
    for(int i=0;i<nmax;i++){
        dis[i]=-1; //初始化
    }
    dis[0]=0; qnow=0;
    switch_queue();
    push_queue(0);
    switch_queue();
    while(!empty_queue()){
        l=size_queue();
        while(l--){
            u=pop_queue();//取出队列结点
            for(int i=net.start[u];i!=-1;i=net.arc[i].next){
                v=net.arc[i].v;
                if(dis[v]==-1&&net.arc[i].cap>net.arc[i].flow){
                    push_queue(v);
                    dis[v]=dis[u]+1;
                    if(v==n)  return true;//汇点在层次网络中
                }
            }
        }
        switch_queue();//滚动队列
    }
    return false;
}

int Dinic(){//Dinic求最大流
    int u,neck,pos,res,i;
    int maxflow=0;
    while(Bfs()){
        memcpy(cur,net.start,sizeof(cur));
        deep=0;
        u=0;
        while(1){//最短路径增广
            if(u==n){
                neck=INF;
                for( i=0;i<deep;i++){
                    res=net.arc[path[i]].cap-net.arc[path[i]].flow;
                    if(res<neck){
                        neck=res;
                        pos=i;
                    }
                }
                maxflow+=neck;
                for( i=0;i<deep;i++){
                    net.arc[path[i]].flow+=neck;
                    net.arc[path[i]^1].flow-=neck;
                }
                deep=pos;
                u=net.arc[path[deep]].u;
            }
            //在层次网络中进行增广
            for(i=cur[u];i!=-1;i=net.arc[i].next){
                if(net.arc[i].cap>net.arc[i].flow&&dis[u]+1==dis[net.arc[i].v])
                break;
            }
            cur[u]=i;
            if(i!=-1){
                path[deep++]=i;
                u=net.arc[i].v;
            }
            else {
                if(deep==0) break;
                dis[u]=-1;
                u=net.arc[path[--deep]].u;
            }
        }
    }
    return maxflow;//返回最大流
}

int main()
{
    int a,b,w;
    scanf("%d%d",&n,&m);
    net.clear();//初始化
    for(int i=1;i<=n;i++){
        scanf("%d%d",&a,&b);
        net.add_arc(EDGE(0,i,a));
        net.add_arc(EDGE(i,n+1,b));
    }
    for(int i=0;i<m;i++){
        scanf("%d%d%d",&a,&b,&w);
        net.add_arc(EDGE(a,b,w));
    }
    n++;
    printf("%d\n",Dinic());
    return 0;
}