http://www.lydsy.com/JudgeOnline/problem.php?id=1927
http://hi.baidu.com/lydrainbowcat/item/96ade2bf64c221f363388eb9

Brief description:

略。）

Analysis:

费用流，最小路径覆盖。）

//}/* .................................................................................................................................. */

int n, m;

namespace MinCostMaxFlow{

    const int N = 2048, M = 2*N*N + 9;
    const int NN = 2047; // cover_bit(N) - 1

    int D[N], hd[N], suc[M], to[M], cap[M], cst[M];
    int n, m, s, t; LL nesf, flow, cost;

    int new_node(){
        hd[n] = 0;
        return n++;
    }

    inline void add_edge(int x, int y, int c, int w = 0){
        suc[m] = hd[x], to[m] = y, cap[m] = c, cst[m] =  w, hd[x] = m++;
        suc[m] = hd[y], to[m] = x, cap[m] = 0, cst[m] = -w, hd[y] = m++;
        //nesf += w;
    }

    inline void add_edgee(int x, int y, int c, int w = 0){
        add_edge(x, y, c, w);
        add_edge(y, x, c, w);
    }

    int Q[NN+1], pre[N], cz, op; bool inQ[N];

#define v to[i]
#define c cap[i]
#define f cap[i^1]
#define w cst[i]

    bool spfa(){
        fill(inQ, inQ+n, 0), fill(D, D+n, INF);
        cz = 0, op = 1; D[Q[cz] = s] = 0; while (cz != op){
            int u = Q[cz++]; inQ[u] = 0; cz &= NN;
            REP_G(i, u) if (c && checkMin(D[v], D[u]+w)){
                pre[v] = i; if (!inQ[v]) Q[op++] = v, inQ[v] = 1, op &= NN;
            }
        }
        return D[t] != INF;
    }

#undef v

    void add_path(){
        int d = INF; int u, v = t; do{
            int i = pre[v]; checkMin(d, c);
            u = to[i^1], v = u;
        } while (u != s);

        flow += d; u, v = t; do{
            int i = pre[v]; f += d, c -= d; cost += d*w;
            u = to[i^1], v = u;
        } while (u != s);
    }

    pair<LL, LL> Run(){
        cost = 0, flow = 0; while (spfa()) add_path();
        return MP(cost, flow);
    }


#undef c
#undef f
#undef w

    void Init(){

        RST(hd); m = 2; RD(::n, ::m); s = 0, t = 2*::n+1; n = t+1;

        REP_1(i, ::n){
            add_edge(s, ::n+i, 1, RD());
            add_edge(s, i, 1, 0);
            add_edge(::n+i, t, 1, 0);
        }

        DO(::m){
            int x, y, w; RD(x, y, w); if (x > y) swap(x, y);
            add_edge(x, y+::n, 1, w);
        }
    }
} //using namespace MinCostMaxFlow;

int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif


    MinCostMaxFlow::Init();
    cout << MinCostMaxFlow::Run().fi << endl;
}

Posted by xiaodao
Category: 日常