Codechef 12.9 PARADE 最短路+Floyd+费用流
题目大意：
有一个$n$个点，$m$条边的有向图，边上是带权的，现在要找出若干条路径，首先花费所有路径上的边的权值之和（若某条边出现在$k$条路径中则计算$k$次），随后如果有一条路径的起点和终点不同额外花费$C$的费用，如果有一个点没有出现在任意一条路径中额外花费$C$的费用。现有$Q$组询问，每次给定一个$C$的取值，问这种情况下的最小花费。
数据范围$n\leq{250},m\leq{30000}$。
算法讨论：
我们用Floyd算法求出全局最短路，然后重新建图，将每两个点之间连一条边，边权为两个点之间的最短路。然后，我们在新图上求解这个问题，那么可以将问题转化为选出一些点不相交的路径，若路径上一共有$k$条边，则付出的费用为所有边的权值之和再加上$(n-k)\times{C}$。
那么这个问题类似于有向图的最小路径覆盖问题，我们将所有点拆成入点和出点，然后利用SPFA求最小费用流，那么每次增广选择的边的权值都是单调递增的，我们将这些权值记下来，那么对于一个给定的$C$，我们可以二分找到第一个$>C$的权值，只选择这个权值前面的权值对应的边。
时空复杂度：
时间复杂度$O(n^3+COSTFLOW(n,n^2)+Q\log n)$，空间复杂度$O(n^2)$。
代码：
#include <cstdio>
#include <cstring>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
#define inf 0x1f1f1f1f
#define N 260
int f[N][N], ans[N], num;
struct Solver {
static const int V = 510;
static const int E = 1000010;
int head[V], nxt[E], to[E], flow[E], cost[E], ind;
int d[V], ld[V], lb[V];
bool inq[V];
void reset() {
ind = 0;
memset(head, -1, sizeof head);
}
void addedge(int a, int b, int f, int c) {
int q = ind++;
to[q] = b;
nxt[q] = head[a];
head[a] = q;
flow[q] = f;
cost[q] = c;
}
void make(int a, int b, int f, int c) {
//printf("%d %d %d %d\n", a, b, f, c);
addedge(a, b, f, c);
addedge(b, a, 0, -c);
}
bool spfa(int s, int t) {
static queue<int> q;
static int i, j;
memset(d, 0x1f, sizeof d);
memset(inq, 0, sizeof inq);
d[s] = 0;
inq[s] = 1;
q.push(s);
while (!q.empty()) {
i = q.front();
q.pop();
inq[i] = 0;
for (j = head[i]; j != -1; j = nxt[j]) {
if (flow[j] && d[to[j]] > d[i] + cost[j]) {
ld[to[j]] = i;
lb[to[j]] = j;
d[to[j]] = d[i] + cost[j];
if (!inq[to[j]]) {
q.push(to[j]);
inq[to[j]] = 1;
}
}
}
}
return d[t] != inf;
}
void minCost(int s, int t) {
int i, mn;
while (spfa(s, t)) {
for (i = t, mn = inf; i != s; i = ld[i])
mn = min(mn, flow[lb[i]]);
for (ans[++num] = d[t] * mn, i = t; i != s; i = ld[i]) {
flow[lb[i]] -= mn;
flow[lb[i] ^ 1] += mn;
}
}
}
}g;
int main() {
//freopen("tt.in", "r", stdin);
int n, m, q, i, j, k, a, b, c;
cin >> n >> m >> q;
memset(f, 0x1f, sizeof f);
while (m--) {
scanf("%d%d%d", &a, &b, &c);
f[a][b] = min(f[a][b], c);
}
for (i = 1; i <= n; ++i)
f[i][i] = 0;
for (k = 1; k <= n; ++k)
for (i = 1; i <= n; ++i)
for (j = 1; j <= n; ++j)
f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
g.reset();
int s = 0, t = 2 * n + 1;
for (i = 1; i <= n; ++i) {
g.make(s, 2 * i - 1, 1, 0);
g.make(2 * i, t, 1, 0);
}
for (i = 1; i <= n; ++i)
for (j = 1; j <= n; ++j)
if (i != j && f[i][j] != inf)
g.make(2 * i - 1, 2 * j, 1, f[i][j]);
g.minCost(s, t);
int cnt, res;
while (q--) {
scanf("%d", &c);
for (cnt = res = 0, i = 1; i <= num; ++i) {
if (ans[i] <= c) {
++cnt;
res += ans[i];
}
else
break;
}
printf("%d\n", res + (n - cnt) * c);
}
return 0;
}
Sep 26, 2022 02:00:26 AM
Each 6th class student who wants to give their best in every Geography examination conducted by the any Central Education Board in Term-1 & Term-2 such as SA1, SA2, FA1, FA2, FA3, FA4 and Assignments and other types of exams can download NCERT 6th Class Geography Sample Paper 2023 with answers for regular practising by mock tests and revisions. NCERT Geography Question Paper Class 6 Each 6th class student who wants to give their best in every Geography examination conducted by the any Central Education Board in Term-1 & Term-2 such as SA1, SA2, FA1, FA2, FA3, FA4 and Assignments and other types of exams can download NCERT 6th Class Geography Sample Paper 2023 with answers for regular practising by mock tests and revisions.