记录编号	328284	评测结果	AAAAAAAAAA
题目名称	[NOI 2006]最大获利	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	0.670 s
提交时间	2016-10-23 21:18:50	内存使用	1.39 MiB

#include <cstdio>
#include <cstdarg>
#include <cstring>
#include <string>
#include <list>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
#define MAXN 60000
class dinic
{
private:
   bool vis[MAXN];
   int dist[MAXN];
   int cure[MAXN];
   vector<int> G[MAXN];
   struct edge
   {
       int from, to, rem;
   };
   int s, t;
   vector<edge> edges;
public:
    dinic(int fr, int to)
    {
        s = fr;
        t = to;
    }
    void addedge(int u, int v, int c)
    {
        edges.push_back((edge){u, v, c});
        edges.push_back((edge){v, u, 0});
        int k = edges.size();
        G[u].push_back(k-2);
        G[v].push_back(k-1);
    }
    bool bfs()
    {
        memset(vis, 0, sizeof(vis));
        queue<int> q;
        q.push(s);
        vis[s] = true;
        dist[s] = 0;
        while(q.size())
        {
            int c = q.front();
            q.pop();
            for(int i = 0; i < G[c].size(); i++)
            {
                edge &e = edges[G[c][i]];
                if(!vis[e.to] && e.rem > 0)
                {
                    vis[e.to] = true;
                    dist[e.to] = dist[c] + 1;
                    q.push(e.to);
                }
            }
        }
        return vis[t];
    }
    int dfs(int x, int f)
    {
        if(f == 0 || x == t)return f;
        int tot = 0;
        int nt;
        for(int &i = cure[x]; i < G[x].size(); i++)
        {
            edge &e = edges[G[x][i]];
            if(dist[e.to] == dist[x] + 1 && (nt = dfs(e.to, min(f, e.rem))) > 0)
            {
                f -= nt;
                tot += nt;
                e.rem -= nt;
                edges[G[x][i]^1].rem += nt;
                if(f == 0)break;
            }
        }
        return tot;
    }
    int maxf()
    {
        int f = 0;
        while(bfs())
        {
            memset(cure, 0, sizeof(cure));
            f += dfs(s, 0x7fffffff);
        }
        return f;
    }
};
int main()
{
    freopen("profit.in", "r", stdin);
    freopen("profit.out", "w", stdout);
    int n, m;
    scanf("%d %d", &n, &m);
    dinic d(0, n+m+1);
    for(int i = 1; i <= n; i++)
    {
        int t;
        scanf("%d", &t);
        d.addedge(i, n+m+1, t);
    }
    int sum = 0;
    for(int i = 1; i <= m; i++)
    {
        int u, v, c;
        scanf("%d %d %d", &u, &v, &c);
        sum += c;
        d.addedge(0, i+n, c);
        d.addedge(i+n, u, 0x7fffffff);
        d.addedge(i+n, v, 0x7fffffff);
    }
    printf("%d\n", sum - d.maxf());
    return 0;
}