这题要求调整部分边的方向，把有环的有向图中部分边反向，使其变成无环图，我们要求的是调整的边的最大权值最小的方案。首先我们要知道一个原理，如果无环图加入$A \to B$会使其变为有环图，那么$B\to A$一定是连通的，那么加入边$B\to A$不会使其成环。那么，我们删掉某些边得到无环图之后，必然可以加回来得到无环图。而如果我们删除权值不大于ans的所有边，我们可以很快地算出是否有环。如果有环，则ans一定小于答案，如果无环，则ans不小于答案。根据这一性质，我们可以二分套判环解决，判环使用拓扑方法，复杂度为$O((m+n)logM)M$可以是最大边权，也可以是边权的中位数（$O(n)$找中位数要多写不少代码，并且这题不必要）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
|
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define RST(a) memset(a, 0, sizeof(a))
#define RSTV(a, v) memset(a, v, sizeof(a))
#define FOR(i, a, b) for (auto i = a; i < b; ++i)
struct E {
int v, w;
};
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, m, M = 0;
cin >> n >> m;
vector<E> path[n + 1];
FOR(i, 0, m) {
int u, v, w;
cin >> u >> v >> w;
M = max(M, w);
path[u].push_back({v, w});
}
int ans = M / 2;
int tmp[2] = {0, M};
do {
vector<E> pathcpy[n + 1];
int cnt[n + 1];
RST(cnt);
FOR(i, 1, n + 1) for (auto p : path[i]) if (p.w > ans) {
pathcpy[i].push_back(p);
++cnt[p.v];
}
queue<int> q;
FOR(i, 1, n + 1) if (!cnt[i]) q.push(i);
int c = 0;
while (!q.empty()) {
++c;
int now = q.front();
q.pop();
for (auto p : pathcpy[now]) {
--cnt[p.v];
if (!cnt[p.v]) q.push(p.v);
}
}
tmp[c == n] = ans + (c != n);//有环时答案大于ans，可以从ans+1开始
ans = ((ll)tmp[0] + tmp[1]) / 2;
} while (tmp[1] != tmp[0]);
cout << ans;
}
|
这题是求免费一条边的最小生成树权值和，以及要使权值和等于该值的情况下，可以选择的免费边的数量。首先，最小生成树的算法这里不再累述，kruskal算法即可。然后根据贪心的思想易知第一个问题的答案为最小生成树总权值-最小生成树上最大边权值。然后难点就在于第二个问题。树上权值最大的边（可能有多条相等）如果能被另一条边替代，那么替代后免费新的边，也能得到相同的结果。所以我们要找到可以替换树上最大边的边。我们可以把最大边去掉（第一次并查集记录最大边条数，第二次并查集参考G题），这样树就出现了中断，然后我们需要寻找能够把中断补上的边。我们沿用kruskal算法的并查集，即可轻松判断一条边是否能补上中断。遍历一遍边即可，由最小生成树的性质，小边不可能替代大边，所以权值小于树上最大边的边可以直接略过。
最大部分的时间复杂度就是kruskal的时间复杂度，即$O(mlogm+mA(n)+n)$，其实复杂度最大的地方就是排序边的O(mlogm)
代码及注释：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
|
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define RST(a) memset(a, 0, sizeof(a))
#define RSTV(a, v) memset(a, v, sizeof(a))
#define FOR(i, a, b) for (auto i = a; i < b; ++i)
int fa[100001], depth[100001];
int find(int x) {
if (fa[x] == x) return x;
return fa[x] = find(fa[x]);
}
void connect(int u, int v) {
u = find(u), v = find(v);
if (depth[u] > depth[v])
fa[v] = u;
else {
fa[u] = v;
if (depth[v] == depth[u]) ++depth[v];
}
}
struct E {
int u = 0, v = 0, w = 0;
bool operator<(E x) const { return w < x.w; }
};
E edge[200005];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int M = 0, n, m, i = 0, cm = 0;
ll S = 0;
cin >> n >> m;
for (int i = 1; i <= n; ++i) fa[i] = i;
for (int i = 0; i < m; ++i) {
int u, v, w;
cin >> u >> v >> w;
edge[i] = {u, v, w};
}
sort(edge, edge + m);
for (auto p : edge)//第一次并查集
if (i == n - 1)
break;
else if (find(p.u) == find(p.v))
continue;
else {
++i;
connect(p.u, p.v);
S += p.w;
if (p.w > M) {
M = p.w;
cm = 1;
} else if (p.w == M)
++cm;//记录树上最大边的条数
}
for (int i = 1; i <= n; ++i) fa[i] = i;
RST(depth);
int cnt = i = 0;
for (auto p : edge)
if (i == n - 1 - cm)//跳过树上最大边
break;
else if (find(p.u) == find(p.v))
continue;
else {
++i;
connect(p.u, p.v);
}
for (auto p : edge)//如果想进一步优化，可以保留第二次并查集的最后位置，然后从该位置-cm开始
if (p.w >= M && find(p.u) != find(p.v)) ++cnt;
cout << S - M << ' ' << cnt;
}
|
该题判断是否有欧拉路径，然后输出字典序最小的欧拉路径。判断欧拉路径根据出入度，所有点入度等于出度则有欧拉回路，入度比出度大一的点和出度比入度大一的点各一个（必须两者都有一个）则有欧拉路径（非回路）。然后是输出部分，如果是回路，要从有路的最小点作为起点。然后可以用一个dfs，从小的边开始搜，回溯的时候即可得到反向的欧拉路径，再反向输出即可。由于路径可能很长，搜索深度可能很深，dfs递归会发生栈溢出，可以加inline内联交给GNU的强大力量去解决（这样写甚至跑起来更快），也可以写非递归版的dfs（码量稍大）。复杂度$O(m)$
代码及注释：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
|
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define RST(a) memset(a, 0, sizeof(a))
#define RSTV(a, v) memset(a, v, sizeof(a))
#define FOR(i, a, b) for (auto i = a; i < b; ++i)
int n, m, ans[2000005], pos = 0, cnt = 0;
vector<int> path[1000005];
inline void dfs(int s) {//递归版
while (!path[s].empty()) {
int p = path[s].back();
path[s].pop_back();
dfs(p);
ans[cnt++] = p;
}
}
void dfs(int s) {//非递归版
int stack[2000005], top = 0;
stack[++top] = s;
while (top) {
int x = stack[top];
if (path[x].empty()) {
top--;
ans[cnt++] = x;
} else {
stack[++top] = path[x].back();
path[x].pop_back();
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
int i[n + 1], o[n + 1];
RST(i);
RST(o);
FOR(j, 0, m) {
int u, v;
cin >> u >> v;
path[u].push_back(v);
++i[v], ++o[u];
}
int s = 0, t = 0;
FOR(j, 1, n + 1) {
if (o[j] == i[j])
continue;
else if (o[j] - i[j] == 1) {
if (s) goto shame;
s = j;
} else if (o[j] - i[j] == -1) {
if (t) goto shame;
t = j;
} else
goto shame;
}
if ((bool)s ^ (bool)t) goto shame;
for (auto &p : path) sort(p.begin(), p.end(), greater<int>());
if (!s)
while (!o[++s])
;
dfs(s);
//递归版起点要单独输出一下 cout << s << ' ';
while (cnt) cout << ans[--cnt] << ' ';
return 0;
shame:
cout << "What a shame!";
}
|
这题要求的是在一个有向，可能有环的正点权图上获取最大值。如果它是无环的，那么以终点的权作为边权求最长路即可（无环图不会到达一个点多次），因此，我们就考虑怎么处理环。这样就引入了缩点的概念(据说暴力也可以过?)，为了获取最大权，进入环中一个点后必然会把整个环吃完，然后从中选择合适的点出环。根据这一性质，我们可以找到图中的环（不一定是单层的环，标准的名称为强联通分量），把每一个环缩成一个点，权值为各点权值之和，环内点与环外点的路径都加在缩成的点上。实现的方法有Kosaraju、Tarjan（没错，又是这位图灵奖巨佬）等。本题以Kosaraju为例，从起点开始进行一次dfs，回溯时按顺序记录点，再在反向图上，按之前的记录逆序一次dfs，在第i次反向dfs中初次找到的点（当然，正向dfs中不可达的点要排除）就构成了第i个强联通分量。然后建立新图，按一开始说的无环图做法即可，正权图最长路相当于负权图最短路，使用spfa算法求解。Kosaraju的复杂度通常为$O(n+m)$，时间瓶颈在于spfa，复杂度最坏可达$O(mn)$
代码及注释：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
|
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define RST(a) memset(a, 0, sizeof(a))
#define RSTV(a, v) memset(a, v, sizeof(a))
#define FOR(i, a, b) for (auto i = a; i < b; ++i)
struct E {
int v, l;
};
vector<int> path[3001], repath[3001];
int m, n, l[3001], dfn[3001], pos = 0, vis[3001], revis[3001], f[3001], point[3001], s, p[3001], dis[3001];
vector<E> fpath[3001];
inline void dfs(int now) {//正向dfs
vis[now] = 1;
for (auto &p : path[now])
if (!vis[p]) dfs(p);
dfn[pos++] = now;
}
inline void redfs(int now, int pos) {//反向dfs
if (!vis[now] || revis[now]) return;
revis[now] = 1;
f[now] = pos;
point[pos] += l[now];
for (auto &p : repath[now]) redfs(p, pos);
}
void spfa() {
RST(dis);
queue<int> q;
dis[f[s]] = point[f[s]];
q.push(f[s]);
bool has[3001] = {0};
has[f[s]] = 1;
while (!q.empty()) {
int now = q.front();
q.pop();
has[now] = 0;
for (auto p : fpath[now])
if (dis[p.v] < dis[now] + p.l) {
dis[p.v] = dis[now] + p.l;
if (!has[p.v]) {
q.push(p.v);
has[p.v] = 1;
}
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
int u[m], v[m];
FOR(i, 0, m) {
cin >> u[i] >> v[i];
path[u[i]].push_back(v[i]);
repath[v[i]].push_back(u[i]);//反向图
}
FOR(i, 1, n + 1) cin >> l[i];
int np;
cin >> s >> np;
FOR(i, 0, np) cin >> p[i];
RST(vis);
dfs(s);
int tmp = pos;
pos = 0;
RST(revis);
for (int i = tmp - 1; i >= 0; --i) redfs(dfn[i], pos++);
FOR(i, 0, m)
if (f[u[i]] != f[v[i]])
fpath[f[u[i]]].push_back({f[v[i]], point[f[v[i]]]});//建立缩点后的新图
spfa();
int M = 0;
FOR(i, 0, np) M = max(M, dis[f[p[i]]]);
cout << M;
}
|
这是本次的签到题，解题方法是根据贪心的思想，按权值从小到大取边，同时采用并查集判断边是否可取，这种算法被称为
kruskal算法，复杂度为$O(mlogm+mA(n)+n)$，瓶颈是边排序的$O(mlogm)$
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
#include <bits/stdc++.h>
using namespace std;
int fa[1001], depth[1001];
int find(int x) {
if (fa[x] == x) return x;
return fa[x] = find(fa[x]);
}
void connect(int u, int v) {
u = find(u), v = find(v);
if (depth[u] > depth[v])
fa[v] = u;
else {
fa[u] = v;
if (depth[v] == depth[u]) ++depth[v];
}
}
struct E {
int u, v, w;
bool operator<(E x) const { return w < x.w; }
};
E edge[500000];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, m, k, pos = 0;
cin >> n >> m >> k;
for (int i = 1; i <= n; ++i) fa[i] = i;
for (int i = 0; i < m; ++i) {
int u, v, w;
cin >> u >> v >> w;
edge[i] = {u, v, w};
}
sort(edge, edge + m);
int result = 0;
for (auto p : edge)
if (n == k)
break;
else if (find(p.u) == find(p.v))
continue;
else {
connect(p.u, p.v);
--n;
result += p.w;
}
cout << result;
}
|
这题的思路没有什么好说的，很明显的网络流板题。下面简单说一下网络流（以后有时间可能会单独写一篇博客，也很可能会鸽）
网络流是一个有若干条带权（容量）边组成的，固定源点和汇点的有向图。本题要解决的是，从源点产生的流（本题中水流是个很形象的例子），经过各边汇集到汇点，这样的流的最大流量。显然，对于每个点，流入流出的量相等，总流量守恒；同时，每条边上的流量均不能超过该条边的容量。在思考怎么求出最大流的过程中，我们要了解一个非常重要的定理──增广路定理。当我们找到网络流中一条从源点到汇点的通路时，可以把这条通路的各段边的容量减少一个值 $a$，最好的情况下下，这样处理后的网络的最大流就减少了 $a$，这样的网络我们称之为残量（残留容量）网络，当残量网络中没有上述通路时，残量网络的最大流为0，原网络的最大流为$\sum a$，我们可以利用dfs找通路，$a$ 取路径上的最小残量，不断循环得出结果。
然而，这样做会存在一些问题
1.每次找到的路径可以是最好的路连接径吗？似乎不是。这种情况我们在数据结构专题的K题（点此进入）中遇到过，当时我们在删点的时候加入新的点来模拟反悔的操作。这里我们也可以加入反向边来模拟反悔的操作。
2.这样反复的dfs很耗时，可能会反复搜某一条边，尤其是各边容量的极差很大时。该算法称为Ford-Fulkerson算法，复杂度为$O(mC)$，通常只建议用来处理容量很小的图，如单位容量简单网络最大流的快速算法（其实我并不会）的其中部分步骤可以用它。可以采用bfs，即Edmonds-Karp算法来改进，复杂度为$O(nm^2)$。但是EK算法过这题似乎有点紧，有没有更快的做法？dinic、ISAP、等（其实两者原理很像，优化魔改之后界限并不是那么清晰）。
我们把所有的节点根据与源点的距离分层，找增广路时只取依层递进的路径，然后再重新分层，反复循环。复杂度最大为$O(mn^2)$（较松，还能加优化），具体实现如下（注意有注释的地方）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
|
#include <bits/stdc++.h>
using namespace std;
#define RST(a) memset(a, 0, sizeof(a))
#define RSTV(a, v) memset(a, v, sizeof(a))
#define FOR(i, a, b) for (auto i = a; i < b; ++i)
struct edge {
int e, c;
};
int n, m, cur[201], tail = 0, depth[201];
bool visited[201];
edge edges[20001];
vector<int> path[201];
inline void addedge(int s, int e, int c) {//建图时把反向边位置也分配好，并且分配到正向边位置^1，便于快速找反向边
edges[tail] = {e, c};
path[s].push_back(tail++);
edges[tail] = {s, 0};
path[e].push_back(tail++);
}
bool dinic_bfs() {//通过bfs，逐层外扩，实现分层
RST(depth);
RST(visited);
visited[1] = 1;
queue<int> q;
q.push(1);
while (!q.empty()) {
int now = q.front();
q.pop();
for (auto p : path[now]) {
if (!visited[edges[p].e] && edges[p].c) {
depth[edges[p].e] = depth[now] + 1;
q.push(edges[p].e);
visited[edges[p].e] = 1;
}
}
}
return visited[n];//如果汇点已不可达，说明已无增广路，则结束循环，否则继续
}
int dinic_dfs(int now, int cap) {
if (now == n || !cap) return cap;
for (auto &i = cur[now]; i < path[now].size(); ++i) {//加入cur数组实现当前弧优化，搜到每条点时之前已被搜过的点不会搜出新的增广路路径，因此可以直接跳过。
auto &p = path[now][i];
if (depth[edges[p].e] == depth[now] + 1 && edges[p].c) {
int tmp = dinic_dfs(edges[p].e, min(cap, edges[p].c));
edges[p].c -= tmp;
edges[p ^ 1].c += tmp;//反向边加上相同的值，后面可以走这条反向边来反悔之前选的边
if (tmp) return tmp;//找到有值的增广路，返回
}
}
depth[now] = -1;
return 0;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
while (m--) {
int s, e, c;
cin >> s >> e >> c;
addedge(s, e, c);
}//首先建图
int result = 0;
while (dinic_bfs()) {//然后开始跑分层
RST(cur);
int tmp;
while ((tmp = dinic_dfs(1, INT_MAX >> 2))) result += tmp;//再在图中跑符合要求的增广路，找不到了就重新分层
}
cout << result;
}
|
这是一道很裸的有向图（无向图拆边，然后做法也一样）K短路问题，我们可以采用一个方向最短路算法初始化（dijkstra，spfa什么的都可以，时间很松），一个方向A*启发式搜索（这类题是$h(x)=h*(x)$的特例）的方法解题。最短路算法不再多说，对于A*算法，我们用一个优先队列，从起点开始，每次扩展其直接可达的边入队，这样的过程中，跑出i次第i短路时，它可以扩展出i+1次第i+1短路，由此，当某条边出队K次时可以终止，此时的路径长度就是第k短路的长度。复杂度（貌似）$O(kmlogm)$
代码及注释
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
|
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct edge {
int v;
ll w;
};
struct status {
int p;
ll l;
bool operator<(status b) const { return l > b.l; }
};
struct astar {
int v;
ll g, f;
bool operator<(astar b) const { return f == b.f ? g > b.g : f > b.f; }
};
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, m, k, s, t;
cin >> n >> m >> k >> s >> t;
vector<edge> path[n + 1], repath[n + 1];
ll dis[n + 1];
int visited[n + 1];
for (int i = 0; i < m; ++i) {//建立正向图和反向图
int u, v, w;
cin >> u >> v >> w;
path[u].push_back({v, w});
repath[v].push_back({u, w});
}
memset(dis, 0x3f, sizeof(dis));
memset(visited, 0, sizeof(visited));
priority_queue<status> q;
dis[t] = 0;
q.push({t, 0});
while (!q.empty()) {//反向dijkstra算法求最短路，预处理出h(x)
status now = q.top();
q.pop();
if (visited[now.p]) continue;
visited[now.p] = 1;
for (auto &p : repath[now.p]) {
if (dis[p.v] > dis[now.p] + p.w) {
dis[p.v] = dis[now.p] + p.w;
q.push({p.v, dis[p.v]});
}
}
}
memset(visited, 0, sizeof(visited));
priority_queue<astar> paths;//然后正向通过A*算法得出结果
paths.push({s, 0, dis[s]});
while (!paths.empty()) {
astar now = paths.top();
paths.pop();
if (++visited[now.v] == k && now.v == t) {
cout << now.f;
return 0;
};
if (visited[now.v] > k) continue;
for (auto p : path[now.v])
paths.push({p.v, p.w + now.g, p.w + now.g + dis[p.v]});
}
cout << -1;//跑完之后仍找不到，则说明没有
}
|
这道题目给了我们一个二分图，然后希望求一个最小的点的数量，来覆盖这一个二分图的所有边。我们求出最大匹配，在每个匹配的其中一个点上放置一个点即可覆盖，因此该题实际上是求最大匹配数，我们把二分图各边的容量设为1，然后加入源点s并依次连至左边的元素，右边的元素依次连至汇点t，该问题便转化为了一个网络流问题，而且是单位容量的简单网络流。对于这种特殊情况的网络流，可使用Hopcroft算法达到$O(m\sqrt n)$的复杂度，使用常规的dinic算法也可以平稳通过。以下代码为dinic算法（具体做法见H题）
代码及注释：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
|
#include <bits/stdc++.h>
using namespace std;
#define RST(a) memset(a, 0, sizeof(a))
#define RSTV(a, v) memset(a, v, sizeof(a))
#define FOR(i, a, b) for (auto i = a; i < b; ++i)
struct edge {
int e, c;
};
int a, b, m, cur[200002], tail = 0, depth[200002], End;
bool visited[200002];
edge edges[500000];
vector<int> paths[200002];
inline void addedge(int s, int e, int c) {
edges[tail] = {e, c};
paths[s].push_back(tail++);
edges[tail] = {s, 0};
paths[e].push_back(tail++);
}
bool dinic_bfs() {
RST(depth);
RST(visited);
*visited = 1;
queue<int> q;
q.push(0);
while (!q.empty()) {
int now = q.front();
q.pop();
for (auto p : paths[now]) {
if (!visited[edges[p].e] && edges[p].c) {
depth[edges[p].e] = depth[now] + 1;
q.push(edges[p].e);
visited[edges[p].e] = 1;
}
}
}
return visited[End];
}
int dinic_dfs(int now, int cap) {
if (now == End || !cap) return cap;
for (auto &i = cur[now]; i < paths[now].size(); ++i) {
auto &p = paths[now][i];
if (depth[edges[p].e] == depth[now] + 1 && edges[p].c) {
int tmp = dinic_dfs(edges[p].e, min(cap, edges[p].c));
edges[p].c -= tmp;
edges[p ^ 1].c += tmp;
if (tmp) return tmp;
}
}
depth[now] = -1;
return 0;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> a >> b >> m;
End = a + b + 1;//0为源点，1到a+b为二分图中点，a+b+1为汇点
while (m--) {
int s, e;
cin >> s >> e;
addedge(s, e + a, 1);
}
FOR(i, 1, a + 1) addedge(0, i, 1);
FOR(i, 1, b + 1) addedge(i + a, End, 1);//建好图，后面就搬H题过来了
int result = 0;
while (dinic_bfs()) {
RST(cur);
int tmp;
while ((tmp = dinic_dfs(0, INT_MAX >> 2))) result += tmp;
}
cout << result;
}
|
这题求的是免费K条边的最短路。我们的一个容易想到的直观的思路是做分层图，把已经免费的次数作为一个维度建图，但是如果完整的建完整张图，会导致内存超出，而分层图中存在大量的重复边，可以都从第一层取边，然后再加上跨层的边。但我觉得这题更好的思路是，最短路算法本质上是一个一维状态的动态规划（dijkstra偏向于贪心，是bfs的扩展，但其本质上仍然是动态规划的一种），而这题我们需要的是一个二维的动态规划。我们可以按照最短路算法思路，在其基础上使用位置+已免费边数的状态替换位置状态，在状态转移的过程中，由最短路算法的$dis[q]=min{dis[p]+w(p\to q)}$，拓展为$dis[q][h]=min({dis[p][h]+w(p\to q)},{dis[p][h-1]})$，p为所有存在边$p\to q$的点。然后该方程的性质仍然满足dijkstra的要求（转移过程中$dis[q][h]$不小于$dis[p][h]$和$dis[p][h-1]$)，因此可以按照dijkstra的思路，用修改版的dijkstra求解。复杂度$O(kmlogkn)$。spfa的话，直接交貌似会TLE，SLF优化貌似对这种情况效果比较好。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
|
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define RST(a) memset(a, 0, sizeof(a))
#define RSTV(a, v) memset(a, v, sizeof(a))
#define FOR(i, a, b) for (auto i = a; i < b; ++i)
int s, t, k;
ll dis[10005][25];
struct status {//原版dijstra是位置+当前位置的最短路，这里增加来b表示免费的次数
int a = 0, b = 0;
ll dis;
bool operator<(status x) const { return dis > x.dis; }//注意这里dis要静态保存，去掉dis然后动态计算(return dis[a][b] > dis[x.a][x.b])会导致顺序出错，WA on 10
};
struct edge {
int v = 0, w = 0;
};
vector<edge> path[10005];
ll dijkstra() {
RSTV(dis, 0x7f);
priority_queue<status> q;
for (auto &p : dis[s]) p = 0;
q.push({s, 0});
bool visited[10005][25];
while (!q.empty()) {
status now = q.top();
q.pop();
if (visited[now.a][now.b]) continue;
visited[now.a][now.b] = 1;
for (auto &p : path[now.a]) {
if (dis[p.v][now.b] > dis[now.a][now.b] + p.w) {
dis[p.v][now.b] = dis[now.a][now.b] + p.w;
q.push({p.v, now.b, dis[p.v][now.b]});
}//第一种转移，同正常的dijkstra
if (now.b < k && dis[p.v][now.b + 1] > dis[now.a][now.b]) {
dis[p.v][now.b + 1] = dis[now.a][now.b];
q.push({p.v, now.b + 1, dis[p.v][now.b + 1]});
}//第二种转移，跨层，dis值不增加
}
}
return dis[t][k];
}
signed main() {//建图，跑最短路，输出
ios::sync_with_stdio(0);
cin.tie(0);
int n, m;
cin >> n >> m >> k >> s >> t;
while (m--) {
int u, v, w;
cin >> u >> v >> w;
path[u].push_back({v, w});
path[v].push_back({u, w});
}
cout << dijkstra();
}
|
这题有些复杂，购买物品需要花费，购买某个集合的所有物品可获得相应的奖励，答案要求是两者差最大，而不是限制最大花费。这样看起来比动态规划中01背包问题复杂得多。这种问题称为最大权闭合子图问题，我们从源点连接所有的物品，所有集合连向汇点，容量均取正。然后根据包含关系，用无限容量的边连接物品和集合。这样一来，就可以用割去某个物品到源点的边模拟购买此物品，某个集合被买完之后其到终点的流被切断。这样一来我们求一个割，即使得所有的边都被割断，所花费的最小代价，这样对于每个集合，要么获得并且花费了相应的代价，要么放弃了该集合。所有集合的总的压岁钱数量减去此时的割，就是他可以剩下的压岁钱。我们要求最大的剩余压岁钱，就要求最小割。显然，我们按照最大流的路径去割是最佳方案，这样最小割就等于最大流（最大流做法见H题）。复杂度$O((n+m)^2\sum k)$
代码及注释
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
|
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define RST(a) memset(a, 0, sizeof(a))
#define RSTV(a, v) memset(a, v, sizeof(a))
#define FOR(i, a, b) for (auto i = a; i < b; ++i)
struct E {
int e, c;
};
int n, m, t, depth[20002], tail = 0, cur[20002];
E edges[250000];
bool visited[20002];
vector<int> paths[20002];
inline void addedge(int s, int e, int c) {
edges[tail] = {e, c};
paths[s].push_back(tail++);
edges[tail] = {s, 0};
paths[e].push_back(tail++);
}
bool dinic_bfs() {
RST(depth);
RST(visited);
visited[0] = 1;
queue<int> q;
q.push(0);
while (!q.empty()) {
int now = q.front();
q.pop();
for (auto p : paths[now]) {
if (!visited[edges[p].e] && edges[p].c) {
depth[edges[p].e] = depth[now] + 1;
q.push(edges[p].e);
visited[edges[p].e] = 1;
}
}
}
return visited[t];
}
int dinic_dfs(int now, int cap) {
if (now == t || !cap) return cap;
for (auto &i = cur[now]; i < paths[now].size(); ++i) {
auto &p = paths[now][i];
if (depth[edges[p].e] == depth[now] + 1 && edges[p].c) {
int tmp = dinic_dfs(edges[p].e, min(cap, edges[p].c));
edges[p].c -= tmp;
edges[p ^ 1].c += tmp;
if (tmp) return tmp;
}
}
depth[now] = -1;
return 0;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
FOR(i, 1, m + 1) {
int tmp;
cin >> tmp;
addedge(0, i, tmp);
}
t = m + n + 1;
int sum = 0;
FOR(i, m + 1, t) {
int c, k;
cin >> c >> k;
sum += c;//计算所有集合的压岁钱数量总和
addedge(i, t, c);
while (k--) {
int tmp;
cin >> tmp;
addedge(tmp, i, INT_MAX >> 1);
}
}//建图完，0为源点，1到m为物品，m+1到m+n为集合，m+n+1为汇点，然后跑最大流
int result = 0;
while (dinic_bfs()) {
RST(cur);
int tmp;
while ((tmp = dinic_dfs(0, INT_MAX >> 1))) result += tmp;
}
cout << sum - result;//输出结果
}
|
这题是一道差分约束，某两个量存在一个大于关系，可以用一条权值为1（它们至少相差1）的有向边连接（小于则相反），等于就是权值为0的双向边，这样，然后从源点向每条边添加权值为最小值1的边，这样源点到每个点的最长路长度就是它的最小值，题目要求输出的就是这些值的和。如果有环就说明存在矛盾。带判环的spfa可以用来解决这个问题。复杂度$O(nm)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
|
#include <bits/stdc++.h>
using namespace std;
#define RST(a) memset(a, 0, sizeof(a))
#define RSTV(a, v) memset(a, v, sizeof(a))
#define FOR(i, a, b) for (auto i = a; i < b; ++i)
struct edge {
int v, l;
};
vector<edge> path[10001];
int dis[1001];
int spfa() {
RSTV(dis, 0x80);
queue<int> q;
*dis = 0;
int cnt[1001] = {0};
q.push(0);
bool has[1001] = {1};
++*cnt;
while (!q.empty()) {
int now = q.front();
q.pop();
has[now] = 0;
for (auto p : path[now])
if (dis[p.v] < dis[now] + p.l) {
dis[p.v] = dis[now] + p.l;
if (!has[p.v]) {
q.push(p.v);
has[p.v] = 1;
++cnt[p.v];
if (cnt[p.v] > 1000) return 0;
}
}
}
return 1;
}
int main() {
int n, m;
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
while (m--) {
int a, b, o;
cin >> o >> a >> b;
switch (o) {
case 1:
path[b].push_back({a, 1});
break;
case 2:
path[a].push_back({b, 1});
break;
case 3:
path[a].push_back({b, 0});
path[b].push_back({a, 0});
}
}//建图，过程如前面的描述
FOR(i, 1, n + 1) path->push_back({i, 1});
int result = 0;
if (spfa()) {
FOR(i, 1, n + 1) result += dis[i];
cout << result;
} else//如果spfa跑失败了就输出-1
cout << -1;
}
|
这题，最少花费，可以让人联想到图上面的最短路，而问题的关键就是怎么建图，即找到满足要求的点（状态）和转移路径。状态的描述方式为二进制（参考状压dp。然后跑dijkstra即可。（点和边的判断方式见注释），复杂度貌似为$O(2^n+2^{2(n-\overline m)}+2^{n-\overline m}C_{n-\overline m}^{k-\overline m})$，$\overline m$是$m$减去$m$对cp关系中环的数量，似乎$n$很大(15)，$m$很小(1)的数据可以卡掉（如有错误请指正）
代码及注释
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
|
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define RST(a) memset(a, 0, sizeof(a))
#define RSTV(a, v) memset(a, v, sizeof(a))
#define FOR(i, a, b) for (auto i = a; i < b; ++i)
struct E {
int v, l;
};
int pos = 0, n, m, k, point[2 << 16];//末位表示洁姐姐，然后从右到左依次表示其他人
vector<E> path[2 << 16];
pii against[15];
bool judge_p(int x) {//判断点（状态）
if ((x & 1)) return 1;//如果洁姐姐在当然没问题
FOR(i, 0, m)
if (x >> against[i].first & 1 && x >> against[i].second & 1) return 0;//如果不在就要判断有没有cp，没有才过关
return 1;
}
int judge_e(int x, int y) {//判断边（转移）
int det = x ^ y, cnt = 0;
if (max(x, y) - min(x, y) != det) return 0;//去掉既有有人上，又有人下的情况
if (!(det & 1)) return 0;//去掉洁姐姐没有参加的情况
FOR(i, 0, 16) cnt += det >> i & 1;
return cnt > k ? 0 : cnt;//参加的人不能超过k，满足条件的输出返回人数，作为增加的边的边权。
}
void addedge(int u, int v, int l) {
path[u].push_back({v, l});
path[v].push_back({u, l});
}
int dijkstra() {
priority_queue<pii> q;
bool visited[2 << 16] = {0};
int dis[2 << 16];
RSTV(dis, 0x3f);
*dis = 0;
q.push({0, 0});
while (!q.empty()) {
pii now = q.top();
q.pop();
if (visited[now.first]) continue;
visited[now.first] = 1;
for (auto &p : path[now.first]) {
if (dis[p.v] > dis[now.first] + p.l) {
dis[p.v] = dis[now.first] + p.l;
q.push({p.v, dis[p.v]});
}
}
}
return dis[(1 << (n + 1)) - 1] == 0x3f3f3f3f ? 0 : dis[(1 << (n + 1)) - 1];
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m >> k;
FOR(i, 0, m) {//记录cp关系
int u, v;
cin >> u >> v;
against[pos++] = make_pair(u, v);
}
pos = 0;
int Max = (1 << (n + 1)) - 1;
FOR(i, 0, 1 << (n + 1))
if (judge_p(i) && judge_p(Max - i)) point[pos++] = i;//必须两边都ok，才可以
int tmp;
FOR(i, 0, pos)
FOR(j, i, pos)
if ((tmp = judge_e(point[i], point[j]))) addedge(point[i], point[j], tmp);//遍历点的所有组合，判断并添加边
if ((tmp = dijkstra()))//跑最短路，到不了就输出"mole"
cout << tmp;
else
cout << "mole";
}
|
这题是在三维空间上面取一棵生成树，求这棵树的$\frac{\sum h}{\sum d}$的最小值。我们假设这个值为ans，则${\sum h}\geq ans\sum d$，记最小生成树上的边集合为$A$，则$\sum (e.h-ans \cdot e.d)=0,e\in A$。当ans过大时，$\sum (e.h-ans \cdot e.d) < 0,e\in A$，过小则反之。这样一来，我们就可以用二分套最小生成树来求解。最小生成树部分用prim跑得飞快，用kruskal要慢一些，注意常数别太差还是能过。复杂度$O(Alognz)$，$A$为最小生成树的复杂度
代码及注释：（kruskal）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
|
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define RST(a) memset(a, 0, sizeof(a))
#define RSTV(a, v) memset(a, v, sizeof(a))
#define FOR(i, a, b) for (auto i = a; i < b; ++i)
int fa[1001], depth[1001];
int find(int x) {
if (fa[x] == x) return x;
return fa[x] = find(fa[x]);
}
void connect(int u, int v) {
u = find(u), v = find(v);
if (depth[u] > depth[v])
fa[v] = u;
else {
fa[u] = v;
if (depth[v] == depth[u]) ++depth[v];
}
}
struct E {
int u, v;
double w;
inline bool operator<(E x) const { return w < x.w; }
};
struct P {
int x, y, z;
};
P points[1001];
E edge[500001];
int pos = 0;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
FOR(i, 0, n) cin >> points[i].x >> points[i].y >> points[i].z;
double sum, ans = 10000000;
bool a = 0;
double tmp[2] = {0, 10000000};//中间开始二分
do {
ans = (tmp[0] + tmp[1]) / 2;
pos = sum = 0;
FOR(i, 0, n)
FOR(j, i + 1, n)
edge[pos++] = {i, j,
abs(points[i].z - points[j].z) -
ans * sqrt(((ll)points[i].x - points[j].x) *
(points[i].x - points[j].x) +
((ll)points[i].y - points[j].y) *
(points[i].y - points[j].y))};
for (int i = 0; i < n; ++i) fa[i] = i;//每次要重新加边
RST(depth);
int i = 0;
sort(edge, edge + pos);
for (auto &p : edge)
if (i == n - 1)
break;
else if (find(p.u) == find(p.v))
continue;
else {
++i;
sum += p.w;
connect(p.u, p.v);
}
tmp[sum < 0] = ans;
} while (abs(tmp[0] - tmp[1]) >= 0.0001);//精度1e-4
cout << fixed << setprecision(3) << ans;
}
|