$\texttt{Description}$

给你一张 $n$ 个点，$m$ 条边的有向带权图，请选出两条不相交的路线，使得权值总和最小
$\texttt{Data Range:}1\le n\le 10^3,1\le m\le 10^4$

$\texttt{Solution}$

一眼看上去像是最短路，然而这个数据规模显然不对劲。

两条路线不相交，也就意味着每条边和每个点只能经过一次。考虑建立费用流模型，对边进行流量限制，对点进行拆点以达到限制点的经过次数的目的。

把一个点拆成 $i$ 和 $i^{\prime}$ 两个点，中间连一条流量为 $1$ 费用为 $0$ 的边，代表这个点只能走一次。但注意起点和终点拆点后应该连一条流量为 $2$（或INF）的边。

对于原图中的边流量都是 $1$，费用就是原图的边权。

由于要找两条路径，那么需要确保求出来的最大流是 $2$，因此建立超级源点 $s$ （代码中编号为 $0$），向起点 $1$ 连一条流量为 $2$ 费用为 $0$ 的边。

建立超级汇点 $t$ ，由终点向 $t$ 连一条流量为 $2$ 费用为 $0$ 的边。

由于题目保证图中至少存在两条不相交的从起点到终点的路径，因此最大流一定是 $2$。所以跑一遍费用流，答案就是最小费用。

虽然Dinic跑费用流时间复杂度是 $O(nmf)$ 的，~~但因为这是网络流，所以可以过~~

#include <cstdio>
#include <queue>
#include <cstring>

const int INF = 1e9;
inline int min(const int x, const int y) {return x < y ? x : y;}
struct Edge {
	int to, nxt, cap, cost;
} e[50005];
int head[3005], cur[3005], dis[3005], tot, s, t, n, m;
bool mark[3005], vis[3005];
std::queue<int> Q;
inline void AddEdge(const int u, const int v, const int cap, const int cost) {
	e[++ tot].to = v, e[tot].nxt = head[u], head[u] = tot;
	e[tot].cap = cap, e[tot].cost = cost;
	e[++ tot].to = u, e[tot].nxt = head[v], head[v] = tot;
	e[tot].cap = 0, e[tot].cost = -cost;
}

bool SPFA() {
	memcpy(cur, head, sizeof cur);
	memset(dis, 0x3f, sizeof dis);
	memset(mark, 0, sizeof mark);
	memset(vis, 0, sizeof vis);
	dis[s] = 0;
	Q.push(s);
	while (Q.size()) {
		int u(Q.front());
		Q.pop();
		mark[u] = false;
		for (int i(head[u]); i; i = e[i].nxt) {
			int v(e[i].to);
			if (e[i].cap && dis[u] + e[i].cost < dis[v]) {
				dis[v] = dis[u] + e[i].cost;
				if (!mark[v]) Q.push(v), mark[v] = true;
			}
		}
	}
	return dis[t] <= INF;
}

int dfs(int u, int low) {
	if (u == t) return low;
	vis[u] = true;
	int res(0), flow(0);
	for (int i(cur[u]); i; i = e[i].nxt) {
		cur[u] = i;
		if (e[i].cap && low && dis[u] + e[i].cost == dis[e[i].to] && !vis[e[i].to])
			if (flow = dfs(e[i].to, min(low, e[i].cap))) {
				e[i].cap -= flow, e[i ^ 1].cap += flow;
				res += flow, low -= flow;
			}
	}
	return res;
}

int Dinic() {
	int Mincost(0);
	while (SPFA()) Mincost += dis[t] * dfs(s, INF);
	return Mincost;
}

int main() {
	while (scanf("%d%d", &n, &m) == 2) {
		tot = 1;
		memset(head, 0, sizeof head);
		for (int i(1); i <= m; ++ i) {
			int u, v, w;
			scanf("%d%d%d", &u, &v, &w);
			AddEdge(2 * u, 2 * v - 1, 1, w);
		}
		for (int i(2); i < n; ++ i)
			AddEdge(2 * i - 1, 2 * i, 1, 0);
		AddEdge(1, 2, 2, 0), AddEdge(2 * n - 1, 2 * n, 2, 0);
		AddEdge(s = 0, 1, 2, 0);
		AddEdge(2 * n, t = 2 * n + 1, 2, 0);
		printf("%d\n", Dinic());
	}
}

zqs`s blog

题解【UVA1658 海军上将 Admiral】

$\texttt{Description}$

$\texttt{Solution}$