hdu4280 网络流+挂（无向图的网络流注意建边）

http://acm.hdu.edu.cn/showproblem.php?pid=4280

2
5 7
3 3
3 0
3 1
0 0
4 5
1 3 3
2 3 4
2 4 3
1 5 6
4 5 3
1 4 4
3 4 2
6 7
-1 -1
0 1
0 2
1 0
1 1
2 3
1 2 1
2 3 6
4 5 5
5 6 3
1 4 6
2 5 5
3 6 4

9
6

/**
hdu 4280 网络流+挂
题目大意：给出一些点从最西边的点经过网络到最东边的点，问最大流量（无向图）
解题思路：无向图网络流，不过无向图建边要正反向都要赋予流量值，如果有向图则正向流量值，反向为0；
*/
#pragma comment(linker, "/STACK:10240000000000,10240000000000")
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
const int oo=1e9;
const int mm=200051;

const int mn=100005;

int node,src,dest,edge;

int ver[mm],flow[mm],_next[mm];

int head[mn],work[mn],dis[mn],q[mn];

void prepare(int _node,int _src,int _dest)
{
    node=_node,src=_src,dest=_dest;
    for(int i=0; i<node; ++i)head[i]=-1;
    edge=0;
}

void addedge(int u,int v,int c)
{
    ver[edge]=v,flow[edge]=c,_next[edge]=head[u],head[u]=edge++;
    ver[edge]=u,flow[edge]=c,_next[edge]=head[v],head[v]=edge++;
}

bool Dinic_bfs()
{
    int i,u,v,l,r=0;
    for(i=0; i<node; ++i)dis[i]=-1;
    dis[q[r++]=src]=0;
    for(l=0; l<r; ++l)
        for(i=head[u=q[l]]; i>=0; i=_next[i])
            if(flow[i]&&dis[v=ver[i]]<0)
            {

                dis[q[r++]=v]=dis[u]+1;
                if(v==dest)return 1;
            }
    return 0;
}

int Dinic_dfs(int u,int exp)
{
    if(u==dest)return exp;

    for(int &i=work[u],v,tmp; i>=0; i=_next[i])
        if(flow[i]&&dis[v=ver[i]]==dis[u]+1&&(tmp=Dinic_dfs(v,min(exp,flow[i])))>0)
        {
            flow[i]-=tmp;
            flow[i^1]+=tmp;
            return tmp;
        }
    return 0;
}
int Dinic_flow()
{
    int i,ret=0,delta;
    while(Dinic_bfs())
    {
        for(i=0; i<node; ++i)work[i]=head[i];
        while(delta=Dinic_dfs(src,oo))ret+=delta;
    }
    return ret;
}
int n,m;
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        int a,b;
        int maxx=-1,minn=0x3f3f3f3f;
        for(int i=1;i<=n;i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            if(maxx<x)
            {
                maxx=x;
                b=i;
            }
            if(minn>x)
            {
                minn=x;
                a=i;
            }
        }
        prepare(n+1,a,b);
        for(int i=0;i<m;i++)
        {
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            addedge(u,v,w);
        }
        int ans=Dinic_flow();
        printf("%d\n",ans);
    }
    return 0;
}

hdu4280 网络流+挂（无向图的网络流注意建边）

原文：http://blog.csdn.net/lvshubao1314/article/details/44589661