记录编号	38520	评测结果	AAAWWWWWWW
题目名称	狙击兵	最终得分	30
用户昵称	王者自由	是否通过	未通过
代码语言	C++	运行时间	0.008 s
提交时间	2012-04-20 11:50:12	内存使用	0.29 MiB

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int N = 60, INF = ~0u>>2;
int T, n, m, u, v, s, t, k[N], e;
int c[N][N], f[N][N], a[N], p[N];
int main() {
    freopen("snipers.in", "r", stdin);
    freopen("snipers.out", "w", stdout);
    scanf("%d", &T);
    while(T--) {
        scanf("%d %d", &n, &m);
        s = 0, t = n;
        for(int i=1; i<n; i++)
            scanf("%d", k+i);
        k[t] = INF; e = 0;
        memset(c, 0, sizeof(c));
        memset(f, 0, sizeof(f));
        memset(p, 0, sizeof(p));
        for(int i=0; i<m; i++) {
            scanf("%d %d", &u, &v);
            if(u > v) swap(u, v);
            c[u][v] = k[v];
        }
        queue<int> q;
        for(; ; ) {
            memset(a, 0, sizeof(a));
            a[s] = INF; q.push(s);
            while(!q.empty()) {
                u = q.front(); q.pop();
                for(v=s; v<=t; v++)
                    if(!a[v] && c[u][v] > f[u][v]) {
                        p[v] = u; q.push(v);
                        a[v] = min(a[u], c[u][v] - f[u][v]);
                    }
            } if(a[t] == 0) break;
            for(u=t; u!=s; u=p[u]) {
                f[p[u]][u] += a[t];
                f[u][p[u]] -= a[t];
            } e += a[t];
        }
        printf("%d\n", e);
    }
    return 0;
}