Battle

5 5 
8 
-8 
-10 
12 
-10 

1 2 
2 5 
1 4 
3 4 
4 5

2

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>
#include <stack>
#include <vector>
#include <set>
#include <queue>
#pragma comment (linker,"/STACK:102400000,102400000")
#define maxn 1005
#define MAXN 300005
#define mod 1000000009
#define INF 0x3f3f3f3f
#define pi acos(-1.0)
#define eps 1e-6
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
#define FRE(i,a,b)  for(i = a; i <= b; i++)
#define FREE(i,a,b) for(i = a; i >= b; i--)
#define FRL(i,a,b)  for(i = a; i < b; i++)
#define FRLL(i,a,b) for(i = a; i > b; i--)
#define mem(t, v)   memset ((t) , v, sizeof(t))
#define sf(n)       scanf("%d", &n)
#define sff(a,b)    scanf("%d %d", &a, &b)
#define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)
#define pf          printf
#define DBG         pf("Hi\n")
typedef long long ll;
using namespace std;

struct Edge
{
    int u,v,cap,next;
}edge[MAXN];

int head[maxn],cur[maxn],level[maxn];
int n,m,num;

void init()
{
    num=0;
    mem(head,-1);
}

void addedge(int u,int v,int w)
{
    edge[num].u=u; edge[num].v=v; edge[num].cap=w; edge[num].next=head[u]; head[u]=num++;
    edge[num].u=v; edge[num].v=u; edge[num].cap=0; edge[num].next=head[v]; head[v]=num++;
}

bool bfs(int s,int t)
{
    mem(level,-1);
    queue<int>Q;
    level[s]=0;
    Q.push(s);
    while (!Q.empty())
    {
        int u=Q.front(); Q.pop();
        for (int i=head[u];i+1;i=edge[i].next)
        {
            int v=edge[i].v;
            if (level[v]==-1&&edge[i].cap>0)
            {
                level[v]=level[u]+1;
                Q.push(v);
            }
        }
    }
    return level[t]!=-1;
}

int dfs(int u,int t,int f)
{
    if (u==t) return f;
    for (int &i=cur[u];i+1;i=edge[i].next)
    {
        int v=edge[i].v;
        if (edge[i].cap>0&&level[v]==level[u]+1)
        {
            int d=dfs(v,t,min(f,edge[i].cap));
            if (d>0)
            {
                edge[i].cap-=d;
                edge[i^1].cap+=d;
                return d;
            }
        }
    }
    return 0;
}

int dinic(int s,int t,int nodenum)
{
    int flow=0,f;
    while (bfs(s,t))
    {
        for (int i=0;i<=nodenum;i++) cur[i]=head[i];
        while ((f=dfs(s,t,INF))>0)
            flow+=f;
    }
    return flow;
}

int main()
{
//    freopen("C:/Users/asus1/Desktop/IN.txt","r",stdin);
    int i,j,x,u,v;
    while (~scanf("%d%d",&n,&m))
    {
        init();
        int all=0;
        for (i=1;i<=n;i++)
        {
            scanf("%d",&x);
            if (x>0) addedge(0,i,x),all+=x;
            else addedge(i,n+1,-x);
        }
        for (i=1;i<=m;i++)
        {
            scanf("%d%d",&u,&v);
            addedge(u,v,INF);
        }
        printf("%d\n",all-dinic(0,n+1,n+2));
    }
    return 0;
}

Battle (hdu 3061 最大权闭合图模板题)

原文：http://blog.csdn.net/u014422052/article/details/45442997