记录编号	38119	评测结果	AAAAAAAE
题目名称	[SDOI 2010] 星际竞速	最终得分	87
用户昵称	王者自由	是否通过	未通过
代码语言	C++	运行时间	0.787 s
提交时间	2012-04-13 11:23:26	内存使用	8.81 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int N = 600 + 10, INF = ~0u>>2;
int n, m, k, s, t, r;
int G[N][N], w[N][N], c[N][N], f[N][N];
int p[N], d[N], l[N], a, g, e;
inline void adde(int u, int v, int W, int C) {
    w[u][v] = W;
    c[u][v] = C;
    w[v][u] = 0;
    c[v][u] = -C;
}
void MinCostFlow() {
    queue<int> q;
    for(; ; ) {
        for(int i=s; i<=t; i++)
            d[i] = INF, l[i] = 0;
        d[s] = 0;
        q.push(s);
        while(!q.empty()) {
            int u = q.front(); q.pop();
            l[u] = 0;
            for(int v=s; v<=t; v++)
                if(w[u][v] > f[u][v] && d[v] > d[u] + c[u][v]) {
                    d[v] = d[u] + c[u][v];
                    p[v] = u;
                    if(!l[v]) {
                        l[v] = 1;
                        q.push(v);
                    }
                }
        }
        if(d[t] == INF) break;
        a = INF;
        for(int u=t; u!=s; u=p[u])
            a = min(a, w[p[u]][u] - f[p[u]][u]);
        for(int u=t; u!=s; u=p[u]) {
            f[p[u]][u] += a;
            f[u][p[u]] -= a;
        }
        g += d[t] * a;
        e += a;
    }
}
int main() {
    freopen("starrace.in", "r", stdin);
    freopen("starrace.out", "w", stdout);
    scanf("%d %d", &n, &m);
    s = 0; t = n * 2 + 1;
    for(int i=1; i<=n; i++) {
        scanf("%d", &r);
        adde(s, i+n, 1, r);
        adde(s, i, 1, 0);
        adde(i+n, t, 1, 0);
    }
    int x, y, z;
    for(int i=1; i<=m; i++) { 
        scanf("%d %d %d", &x, &y, &z);
        if(x > y) swap(x, y);
        adde(x, y+n, 1, z);
    }
    MinCostFlow();
    printf("%d\n", g);
    return 0;
}