题目大意
给出一个无向图,一个人会从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)\)满足\(u\in S_0,v\in 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\n" : "No %lld\n", ans);
}
return 0;
}