题意：N个点，M条边(2 <= N <= 1000 , 0 <= M <= 10^5)，每个点有个权值W(0 <= W <= 10^5)，现要去除一些点（不能去掉点0），使得结点 0 与结点 N - 1 不连通，求去掉的点的最小权值和。
题目链接：http://cstest.scu.edu.cn/soj/problem.action?id=3254
——>>这是非常明显的最小点权割。。
建图方案：
1）将所有点 i 拆成 i 和 i + N，i -> i + N（容量为Wi）
2）原图中的边 i -> j 变成 i + N -> j（容量为无穷大）
3）0 -> 0 + N（因为原图中的边可能有涉及到0 -> x，这时会拆0）
接着，根据最小割最大流定理，求得最小割。。（又换命名法了我，囧。。）
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>using std::min;
using std::queue;const int MAXN = 1000 * 2 + 10;
const int MAXM = 2 * (1000 + 100000) + 10;
const int INF = 0x3f3f3f3f;struct EDGE
{int to;int cap;int flow;int nxt;
};int N, M;
int hed[MAXN], nxt[MAXM], S, T;
int cur[MAXN], h[MAXN];
bool vis[MAXN];
int ecnt;
EDGE edge[MAXM];void Init()
{ecnt = 0;memset(hed, -1, sizeof(hed));
}void AddEdge(int u, int v, int cap)
{edge[ecnt].to = v;edge[ecnt].cap = cap;edge[ecnt].flow = 0;edge[ecnt].nxt = hed[u];hed[u] = ecnt++;
}bool Bfs()
{queue<int> qu;memset(vis, 0, sizeof(vis));qu.push(S);vis[S] = true;h[S] = 0;while (!qu.empty()){int u = qu.front();qu.pop();for (int e = hed[u]; e != -1; e = edge[e].nxt){int v = edge[e].to;if (!vis[v] && edge[e].flow < edge[e].cap){h[v] = h[u] + 1;vis[v] = true;qu.push(v);}}}return vis[T];
}int Dfs(int u, int cap)
{if (u == T || cap == 0) return cap;int flow = 0, subFlow;for (int e = cur[u]; e != -1; e = edge[e].nxt){cur[u] = e;int v = edge[e].to;if (h[v] == h[u] + 1 && (subFlow = Dfs(v, min(cap, edge[e].cap - edge[e].flow))) > 0){flow += subFlow;edge[e].flow += subFlow;edge[e ^ 1].flow -= subFlow;cap -= subFlow;if (cap == 0) break;}}return flow;
}int Dinic()
{int flow = 0;while (Bfs()){memcpy(cur, hed, sizeof(hed));flow += Dfs(S, INF);}return flow;
}void Read()
{int W;scanf("%d%d", &N, &M);for (int i = 1; i < N; ++i){scanf("%d", &W);AddEdge(i, i + N, W);AddEdge(i + N, i, 0);}int P, Q;for (int i = 0; i < M; ++i){scanf("%d%d", &P, &Q);AddEdge(P + N, Q, INF);AddEdge(Q, P + N, 0);}AddEdge(0, N, INF);AddEdge(N, 0, 0);S = 0;T = 2 * N - 1;
}void Solve()
{printf("%d\n", Dinic());
}int main()
{int T;scanf("%d", &T);while (T--){Init();Read();Solve();}return 0;
}