hdu4280 네트워크 흐름

#pragma comment(linker, "/STACK:1024000000,1024000000")

#include <iostream>

#include <stdio.h>

#include <string.h>

#include <cstring>

#include <algorithm>

#include <vector>

#define Maxn 120010

#define Maxm 210000

#define LL int

#define inf 100000000

#define Abs(a) (a)>0?(a):(-a)

using namespace std;

struct Edge{

    int from,to,next;

    LL val;

}edge[Maxm];

const double eps=1e-9;

LL value[Maxn];

int head[Maxn],work[Maxn],dis[Maxn],q[Maxn],e,vi[Maxn];

void init()

{

    e=0;

    memset(head,-1,sizeof(head));

}

void add(int u,int v,LL c)// 

{

    edge[e].to=v;edge[e].val=c;edge[e].next=head[u];head[u]=e++;

    edge[e].to=u;edge[e].val=c;edge[e].next=head[v];head[v]=e++;

}

int bfs(int S,int T)

{

    int rear=0;

    memset(dis,-1,sizeof(dis));

    dis[S]=0;q[rear++]=S;

    for(int i=0;i<rear;i++)

    {

        for(int j=head[q[i]];j!=-1;j=edge[j].next)

        {

            if(edge[j].val&&dis[edge[j].to]==-1)

            {

                dis[edge[j].to]=dis[q[i]]+1;

                q[rear++]=edge[j].to;

                if(edge[j].to==T) return 1;

            }

        }

    }

    return 0;

}

LL dfs(int cur,LL a,int T)

{

    if(cur==T) return a;

    for(int &i=work[cur];i!=-1;i=edge[i].next)

    {

        if(edge[i].val&&dis[edge[i].to]==dis[cur]+1)

        {

            LL t=dfs(edge[i].to,min(a,edge[i].val),T);

            if(t)

            {

                edge[i].val-=t;

                edge[i^1].val+=t;

                return t;

            }

        }

    }

    return 0;

}

LL Dinic(int S,int T)

{

    LL ans=0;

    while(bfs(S,T))

    {

        memcpy(work,head,sizeof(head));

        while(LL t=dfs(S,inf,T)) ans+=t;

    }

    return ans;

}

int main()

{

    int n,m,i,j,num=0,t,a,b,west=100000,east=-100000,S,T;

    LL c;

    scanf("%d",&t);

    while(t--)

    {

        init();

        west=1000000,east=-1000000;

        scanf("%d%d",&n,&m);

        for(i=1;i<=n;i++)

        {

            scanf("%d%d",&a,&b);

            if(a<west)

                west=a,S=i;

            if(a>east)

                east=a,T=i;

        }

        for(i=1;i<=m;i++)

        {

            scanf("%d%d%d",&a,&b,&c);

            add(a,b,c);

        }

        LL ans=Dinic(S,T);

        printf("%d
",ans);

    }

    return 0;

}