(BZOJ) 1061: [Noi2008]志愿者招募 [神奇的 min cost max flow ]

http://www.lydsy.com/JudgeOnline/problem.php?id=1061

直接附題解連結：http://www.cnblogs.com/jianglangcaijin/p/3799759.html

好像跟 "單純形法" 有關><。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
using namespace std;

typedef long long LL;
typedef pair<LL,LL> pii;

struct Flow
{
    static const int N = 20006;
    struct Edge
    {
        int to,rev;
        LL cap;
        LL cost;
        Edge(int _to,LL _cap,int _rev,LL _cost)
        {
            to = _to;
            cap = _cap;
            rev = _rev;
            cost = _cost;
        }
    };
    vector<Edge> G[N];
    #define SZ(x) ((int)(x).size())
    void add_edge(int from,int to,LL cap,LL cost)
    {
        G[from].push_back(Edge(to,cap,SZ(G[to]),cost));
        G[to].push_back(Edge(from,0,SZ(G[from])-1,-cost));
    }
    int n,s,t;
    void init(int _n,int _s,int _t)
    {
        n = _n;
        s = _s;
        t = _t;
        for (int i=0;n>=i;i++)
        {
            G[i].clear();
        }
    }
    int pre[N],pre_id[N];
    LL dis[N];
    bool in_que[N];
    pii flow()
    {
        LL flow=0,cost=0;
        LL INF = (1LL << 60);
        while (true)
        {
            queue<int> que;
            memset(in_que,0,sizeof(in_que));
            fill(dis,dis+n+1,INF);
            que.push(s);
            dis[s]=0;
            while (!que.empty())
            {
                int t=que.front();
                que.pop();
                in_que[t] = false;
                for (int id=0;G[t].size()>id;id++)
                {
                    Edge e = G[t][id];
                    if (e.cap > 0 && dis[e.to] > dis[t] + e.cost)
                    {
                        dis[e.to] = dis[t] + e.cost;
                        pre[e.to] = t;
                        pre_id[e.to] = id;
                        if (!in_que[e.to])
                        {
                            in_que[e.to] = 1;
                            que.push(e.to);
                        }
                    }
                }
            }
            //cout << "dis t = "<<
            if (dis[t] == INF) break;
            LL mn_flow = INF;
            for (int i=t;i!=s;i=pre[i])
            {
                mn_flow = min(mn_flow,G[ pre[i] ][ pre_id[i] ].cap);
            }
            flow += mn_flow;
            cost += mn_flow*dis[t];
            for (int i=t;i!=s;i=pre[i])
            {
                G[ pre[i] ][ pre_id[i] ].cap -= mn_flow;
                G[i][ G[ pre[i] ][ pre_id[i] ].rev ].cap += mn_flow;
            }
        }
        return make_pair(flow,cost);
    }
} solver;

LL d[10007];

int main ()
{
    int n,m;
    scanf("%d %d",&n,&m);
    for (int i=1;n>=i;i++)
    {
        scanf("%lld",&d[i]);
    }
    int s=0,t=n+1;
    solver.init(t,s,t);
    for (int i=1;m>=i;i++)
    {
        int s,t,d;
        scanf("%d %d %d",&s,&t,&d);
        solver.add_edge(s,t+1,(1LL<<40),d);
    }
    for (int i=1;n+1>=i;i++)
    {
        LL tmp = d[i] - d[i-1];
        if (tmp >= 0) solver.add_edge(s,i,tmp,0);
        else solver.add_edge(i,t,-tmp,0);
        if (i>1) solver.add_edge(i,i-1,(1LL<<40),0);
    }
    printf("%lld\n",solver.flow().second);
}