题目大意
给出一个无向图，一个人会从1号点沿着最短路走到n号点（可能有多条路径），而你需要在某些边的一端设置障碍，使他最终不能够到达n号点，求最小代价，并判断方案是否唯一。
分析
首先建出最短路图。我们可以把原来的边((u,v))拆成两段：((u,x))和((x,v))；割掉((u,x))的代价为(a[u])，割掉((x,v))的代价为(a[v])。我们的目的是用最小代价割掉最短路图上某些边，使得(1)走不到(n)，这是个最小割模型，于是做一遍最大流就求出了第二问。
问题难在第一问，如何判断最小割是否唯一？
一个不是很显然的结论是：设残量网络中源点(S)通过未满流边能够到达的点集为(S_0)，通过未满流边能够到达汇点(T)的点集为(T_0)，若一条边((u,v))满足(uin S_0,vin T_0)，这条边必定存在于任意一个最小割中。
反证法证明：假设((u,v))不能割，那可以将它的容量视为无穷大，根据题设，我们又能增加(S)到(T)的流量，这与已经求得最大流矛盾，故((u,v))是必须要割的边。
有了这个结论，我们直接将必割边的代价加起来，如果等于所求最小割，那么方案唯一，否则方案不唯一。
Code
#include <cstdio>
#include <cstring>
typedef long long ll;
const int N = 100007, M = 100007;
const ll INF = (1ll << 60);
ll min(ll a, ll b) { return a < b ? a : b; }
int test;
int n, m, S, T, cnt, s1[N], s2[N];
ll ans, sum, dis[N], a[N], len[M];
int tot, st[N], to[M], nx[M];
int total, head[N], go[M], next[M];
int h, t, q[N], vis[N];
void clear1() { tot = 0; memset(st, 0, sizeof(st)); memset(to, 0, sizeof(to)); memset(nx, 0, sizeof(nx)); }
void clear2() { total = 0; memset(head, 0, sizeof(head)); memset(go, 0, sizeof(go)); memset(next, 0, sizeof(next)); }
void add(int u, int v, ll w) { to[++tot] = v, nx[tot] = st[u], len[tot] = w, st[u] = tot; }
void link(int u, int v) { go[++total] = v, next[total] = head[u], head[u] = total; }
void spfa()
{
memset(dis, 0x3f, sizeof(dis));
memset(vis, 0, sizeof(vis));
h = 1, q[t = 1] = 1, vis[1] = 1, dis[1] = 0;
while (h <= t)
{
int u = q[h++];
vis[u] = 0;
for (int i = st[u]; i; i = nx[i])
if (dis[u] + len[i] < dis[to[i]])
{
dis[to[i]] = dis[u] + len[i];
if (!vis[to[i]]) q[++t] = to[i], vis[to[i]] = 1;
}
}
}
void dfs(int u)
{
vis[u] = 1;
for (int i = st[u]; i; i = nx[i])
if (dis[to[i]] + len[i] == dis[u])
{
link(u, to[i]);
if (!vis[to[i]]) dfs(to[i]);
}
}
int bfs()
{
memset(dis, 0, sizeof(dis));
h = 1, q[t = 1] = S, dis[S] = 1;
while (h <= t)
{
int u = q[h++];
for (int i = st[u]; i; i = nx[i])
if (!dis[to[i]] && len[i] > 0)
{
dis[to[i]] = dis[u] + 1, q[++t] = to[i];
if (to[i] == T) return 1;
}
}
return 0;
}
ll dinic(int u, ll flow)
{
if (u == T) return flow;
ll rest = flow, tmp;
for (int i = st[u]; i; i = nx[i])
if (dis[to[i]] == dis[u] + 1 && len[i] > 0)
{
tmp = dinic(to[i], min(rest, len[i]));
if (!tmp) dis[to[i]] = 0;
len[i] -= tmp, len[i ^ 1] += tmp, rest -= tmp;
if (!rest) return flow;
}
return flow - rest;
}
void getset()
{
memset(s1, 0, sizeof(s1)); memset(s2, 0, sizeof(s2));
memset(vis, 0, sizeof(vis));
h = 1, q[t = 1] = S, vis[S] = 1;
while (h <= t)
{
int u = q[h++]; s1[u] = 1;
for (int i = st[u]; i; i = nx[i]) if (len[i] > 0 && !vis[to[i]]) q[++t] = to[i], vis[to[i]] = 1;
}
memset(vis, 0, sizeof(vis));
h = 1, q[t = 1] = T, vis[T] = 1;
while (h <= t)
{
int u = q[h++]; s2[u] = 1;
for (int i = st[u]; i; i = nx[i]) if (len[i ^ 1] > 0 && !vis[to[i]]) q[++t] = to[i], vis[to[i]] = 1;
}
}
int main()
{
scanf("%d", &test);
while (test--)
{
clear1(), clear2();
scanf("%d%d", &n, &m);
for (int i = 1; i <= n - 1; i++) scanf("%lld", &a[i]); a[n] = INF;
for (int i = 1, u, v, w; i <= m; i++) scanf("%d%d%d", &u, &v, &w), add(u, v, w), add(v, u, w);
spfa();
memset(vis, 0, sizeof(vis)), dfs(n);
clear1(); tot = 1, cnt = n;
for (int i = 1; i <= n; i++) for (int j = head[i]; j; j = next[j]) add(go[j], ++cnt, a[go[j]]), add(cnt, go[j], 0), add(cnt, i, a[i]), add(i, cnt, 0);
S = 1, T = n, ans = sum = 0;
while (bfs()) ans += dinic(S, INF);
getset();
cnt = n;
for (int i = 1; i <= n; i++)
for (int j = head[i]; j; j = next[j])
{
++cnt;
if (s1[go[j]] && s2[cnt]) sum += a[go[j]];
if (s1[cnt] && s2[i]) sum += a[i];
}
printf(sum == ans ? "Yes %lld
" : "No %lld
", ans);
}
return 0;
}