将每条航线拆成两个点$i$和$i ^\prime$,源点向$i$,$i^\prime$向汇点连容量为无穷的边,如果一条航线$j$能接上另一条$i$,则从$j^\prime$向$i$连边,每条航线最少经过一次,容易发现是有源汇下界最小流模型,每个航线的$i$向$i^\prime$连一条下界为$1$的边,显然必有可行流。
另一方面,如果我们将一条航线视作一个点,将航线之间可以接上的关系视作边,则形成了一个$DAG$,原问题转化为了最小可重路径点覆盖问题。
$floyd$预处理两两站点之间的最短路,记为$g_{i,j}$,$j$能接上$i$的条件是$d_j+t_{x_j,y_j}+g_{y_j,x_i}+p_{y_j}\leq d_i$。
其实最小路径可重点覆盖本质上就是拆点下界网络流,不可重点覆盖就是拆点上下界网络流。
放出两种做法的代码
有源汇下界最小流
#include <iostream>
#include <cstring>
using namespace std;
const int N = 50010, M = 600100;
const int INF = 1E8;
int e[M], ne[M], h[N], f[M], idx;
int q[N], d[N], cur[N], A[N];
int n, m, S, T, s, t;
int p[510], r[510][510], g[510][510];
int x[510], y[510], D[510];
void insert(int u, int v, int c) {
e[idx] = v, ne[idx] = h[u], f[idx] = c, h[u] = idx++;
e[idx] = u, ne[idx] = h[v], f[idx] = 0, h[v] = idx++;
}
bool bfs() {
int tt = -1, hh = 0;
memset(d, -1, sizeof d);
d[S] = 0, cur[S] = h[S], q[++tt] = S;
while (hh <= tt) {
int t = q[hh++];
for (int i = h[t]; ~i; i = ne[i]) {
int j = e[i];
if (d[j] == -1 && f[i]) {
cur[j] = h[j];
d[j] = d[t] + 1;
if (j == T) return true;
q[++tt] = j;
}
}
}
return false;
}
int find(int u, int limit) {
if (u == T) return limit;
int flow = 0;
for (int i = cur[u]; ~i && flow < limit; i = ne[i]) {
int j = e[i];
cur[u] = i;
if (d[j] == d[u] + 1 && f[i]) {
int t = find(j, min(f[i], limit - flow));
if (!t) d[j] = -1;
f[i] -= t, f[i ^ 1] += t, flow += t;
}
}
return flow;
}
int dinic() {
int r = 0, flow;
while (bfs()) while (flow = find(S, INF)) r += flow;
return r;
}
int main() {
cin.tie(0)->sync_with_stdio(false);
s = N - 1, t = s - 1, S = t - 1, T = S - 1;
memset(h, -1, sizeof h);
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> p[i];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
cin >> r[i][j];
memset(g, 0x3f, sizeof g);
for (int i = 1; i <= n; i++) g[i][i] = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (i != j)
g[i][j] = r[i][j] + p[j];
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
for (int i = 1; i <= m; i++) {
insert(s, i, INF);
insert(i + m, t, INF);
insert(i, i + m, INF);
insert(i, T, 1);
insert(S, i + m, 1);
cin >> x[i] >> y[i] >> D[i];
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= m; j++) {
int tm = D[j] + r[x[j]][y[j]] + g[y[j]][x[i]] + p[y[j]];
if (tm <= D[i]) insert(j + m, i, INF);
}
}
insert(t, s, INF);
dinic();
int res = f[idx - 1];
S = t, T = s;
f[idx - 1] = f[idx - 2] = 0;
cout << res - dinic() << '\n';
return 0;
}
最小可重路径点覆盖
#include <iostream>
#include <cstring>
using namespace std;
const int N = 50010, M = 600100;
const int INF = 1E8;
int e[M], ne[M], h[N], f[M], idx;
int q[N], d[N], cur[N], A[N];
int n, m, S, T, s, t;
int p[510], r[510][510], g[510][510];
int x[510], y[510], D[510];
void insert(int u, int v, int c) {
e[idx] = v, ne[idx] = h[u], f[idx] = c, h[u] = idx++;
e[idx] = u, ne[idx] = h[v], f[idx] = 0, h[v] = idx++;
}
bool bfs() {
int tt = -1, hh = 0;
memset(d, -1, sizeof d);
d[S] = 0, cur[S] = h[S], q[++tt] = S;
while (hh <= tt) {
int t = q[hh++];
for (int i = h[t]; ~i; i = ne[i]) {
int j = e[i];
if (d[j] == -1 && f[i]) {
cur[j] = h[j];
d[j] = d[t] + 1;
if (j == T) return true;
q[++tt] = j;
}
}
}
return false;
}
int find(int u, int limit) {
if (u == T) return limit;
int flow = 0;
for (int i = cur[u]; ~i && flow < limit; i = ne[i]) {
int j = e[i];
cur[u] = i;
if (d[j] == d[u] + 1 && f[i]) {
int t = find(j, min(f[i], limit - flow));
if (!t) d[j] = -1;
f[i] -= t, f[i ^ 1] += t, flow += t;
}
}
return flow;
}
int dinic() {
int r = 0, flow;
while (bfs()) while (flow = find(S, INF)) r += flow;
return r;
}
int main() {
cin.tie(0)->sync_with_stdio(false);
S = N - 1, T = S - 1;
memset(h, -1, sizeof h);
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> p[i];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
cin >> r[i][j];
memset(g, 0x3f, sizeof g);
for (int i = 1; i <= n; i++) g[i][i] = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (i != j)
g[i][j] = r[i][j] + p[j];
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
for (int i = 1; i <= m; i++) cin >> x[i] >> y[i] >> D[i];
for (int i = 1; i <= m; i++) {
insert(S, i, 1);
insert(i + m, T, 1);
for (int j = 1; j <= m; j++) {
int tm = D[j] + r[x[j]][y[j]] + g[y[j]][x[i]] + p[y[j]];
if (tm <= D[i]) insert(j, i + m, INF);
}
}
cout << m - dinic() << '\n';
return 0;
}