图论刷题
昂贵的聘礼 (单源最短路, 图论建模)
思路:将每个物品看作一个点, 到达这个点表示获得该物品, 获取该物品的代价就是边权, 用0号点表示初始状态(不拥有任何物品), 获取某个物品有多种方式, 每种方式各对应一条边, 根据物品v的获取方式分别建边(原价购买表示从建边<0, v>, 边权为原价 以某件物品u加上一定金额兑换表示建边<u, v>边权为一定金额). 问题转化为求0号点到1号点的最短路径, 用dijkstra求解.由于有等级差距限制, 可以限制等级范围进行dijkstra.
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
const int maxn = 105;
int g[maxn][maxn], n, m, dist[maxn], vis[maxn], level[maxn];
void dijkstra(int s, int l, int r) {
memset(vis, 0, sizeof vis);
memset(dist, 0x3f, sizeof dist);
dist[s] = 0;
for (int i = 0; i < n + 1; ++i) {
int u = -1;
for (int j = 0; j <= n; ++j) {
if (!vis[j] && (u == -1 || dist[u] > dist[j]))
u = j;
}
vis[u] = 1;
for (int v = 1; v <= n; ++v) {
if (!vis[v] && dist[v] > dist[u] + g[u][v] && level[v] >= l &&
level[v] <= r) {
dist[v] = dist[u] + g[u][v];
}
}
}
}
int main() {
cin >> m >> n;
int s = 0;
memset(g, 0x3f, sizeof g);
for (int i = 1; i <= n; ++i)
g[i][i] = 0;
for (int i = 1; i <= n; ++i) {
int P, L, X;
cin >> P >> L >> X;
level[i] = L;
g[s][i] = min(g[s][i], P);
while (X--) {
int v, w;
cin >> v >> w;
g[v][i] = min(g[v][i], w);
}
}
int ans = 10000;
for (int i = level[1] - m; i <= level[1]; ++i) {
dijkstra(s, i, i + m);
ans = min(ans, dist[1]);
}
cout << ans << '\n';
return 0;
}
Telephone Lines (分层图最短路, 二分+双端队列bfs)
思路一(二分答案+双端队列bfs): 二分1到n路径上边权的最大值mid, 将1到n路径上大于mid的边权设为1(表示忽略了一条边的边权), 小于等于mid的边权设为0, 利用双端队列bfs求1到n的最短路径长度x, 如果x<=k, 另r=mid, 否则l=mid+1.
#include <cstring>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int maxn = 1005, inf = 0x3f3f3f3f;
struct Edge {
int to, w;
Edge(int _to = 0, int _w = 0) : to(_to), w(_w) {}
};
vector<Edge> e[maxn];
int vis[maxn], dist[maxn];
int bfs(int s, int t, int mid) {
memset(vis, 0, sizeof vis);
memset(dist, 0x3f, sizeof dist);
dist[s] = 0;
deque<int> q;
q.push_back(s);
while (q.size()) {
int u = q.front();
q.pop_front();
if (u == t)
return dist[t];
if (vis[u])
continue;
vis[u] = 1;
for (int i = 0; i < (int)e[u].size(); ++i) {
int v = e[u][i].to, w = e[u][i].w;
w = (w > mid ? 1 : 0);
if (!vis[v] && dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
if (w)
q.push_back(v);
else
q.push_front(v);
}
}
}
return inf;
}
int n, m, k;
int main() {
cin >> n >> m >> k;
while (m--) {
int u, v, w;
cin >> u >> v >> w;
e[u].push_back(Edge(v, w));
e[v].push_back(Edge(u, w));
}
int l = 0, r = 1000001;
while (l < r) {
int mid = l + r >> 1;
int t = bfs(1, n, mid);
if (t <= k)
r = mid;
else
l = mid + 1;
}
if (l == 1000001)
cout << -1 << '\n';
else
cout << l << '\n';
return 0;
}
思路二(分层图最短路, spfa dp): dp[i][j]表示1到i路径上忽略j条边的边权后剩余边权最大值中的最小值, 利用spfa进行dp. 考虑边<u, v>, 当前忽略边数为c, 忽略该边, 则dp[v][c+1] = min(dp[v][c+1], dp[u][c])(c+1<=k), 不忽略, 则dp[v][c] = min{dp[v][c], dp[u], w[u][v]}
#include <cstring>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int maxn = 1005, inf = 0x3f3f3f3f;
struct Edge {
int to, w;
Edge(int _to = 0, int _w = 0) : to(_to), w(_w) {}
};
vector<Edge> e[maxn];
int dp[maxn][maxn], vis[maxn][maxn];
int n, m, k;
void spfa(int s = 1) {
memset(vis, 0, sizeof vis);
memset(dp, 0x3f, sizeof dp);
dp[s][0] = 0;
queue<pair<int, int>> q;
q.push(make_pair(s, 0));
vis[s][0] = 1;
while (q.size()) {
pair<int, int> state = q.front();
q.pop();
int u = state.first, c = state.second;
vis[u][c] = 0;
for (int i = 0; i < (int)e[u].size(); ++i) {
int v = e[u][i].to, w = e[u][i].w;
if (c + 1 <= k && dp[v][c + 1] > dp[u][c]) {
dp[v][c + 1] = dp[u][c];
if (!vis[v][c + 1]) {
q.push(make_pair(v, c + 1));
vis[v][c + 1] = 1;
}
}
if (dp[v][c] > max(dp[u][c], w)) {
dp[v][c] = max(dp[u][c], w);
if (!vis[v][c]) {
q.push(make_pair(v, c));
vis[v][c] = 1;
}
}
}
}
}
int main() {
cin >> n >> m >> k;
while (m--) {
int u, v, w;
cin >> u >> v >> w;
e[u].push_back(Edge(v, w));
e[v].push_back(Edge(u, w));
}
spfa(1);
int ans = inf;
for (int i = 0; i <= k; ++i) {
ans = min(ans, dp[n][i]);
}
if (ans == inf)
ans = -1;
cout << ans << '\n';
return 0;
}
P1073 [NOIP2009 提高组] 最优贸易 (spfa)
思路: 不进行买卖就是0元, 再求进行一次买卖能够赚的钱的最大值, 先分别求出1到i路径上物品价格的最小值mn[i], n到i路径上物品价格的最大值mx[i], 那么进行一次买卖能够赚的钱的最大值就是max{mx[i] - mn[i]}.
#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int maxn = 100005;
vector<int> e[maxn], e2[maxn]; // e正向图, e2反向图
int mn[maxn], mx[maxn], a[maxn], vis[maxn];
int n, m;
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i)
scanf("%d", &a[i]);
while (m--) {
int u, v, z;
scanf("%d%d%d", &u, &v, &z);
e[u].push_back(v);
e2[v].push_back(u);
if (z == 2) {
e[v].push_back(u);
e2[u].push_back(v);
}
}
memset(mn, 0x3f, sizeof mn);
mn[1] = a[1];
queue<int> q;
q.push(1);
vis[1] = 1;
while (q.size()) {
int u = q.front();
q.pop();
vis[u] = 0;
for (int i = 0; i < (int)e[u].size(); ++i) {
int v = e[u][i];
if (mn[v] > min(mn[u], a[v])) {
mn[v] = min(mn[u], a[v]);
if (!vis[v]) {
q.push(v);
vis[v] = 1;
}
}
}
}
mx[n] = a[n];
q.push(n);
vis[n] = 1;
while (q.size()) {
int u = q.front();
q.pop();
vis[u] = 0;
for (int i = 0; i < (int)e2[u].size(); ++i) {
int v = e2[u][i];
if (mx[v] < max(mx[u], a[v])) {
mx[v] = max(mx[u], a[v]);
if (!vis[v]) {
q.push(v);
vis[v] = 1;
}
}
}
}
int ans = 0;
for (int i = 1; i <= n; ++i) {
ans = max(ans, mx[i] - mn[i]);
}
printf("%d\n", ans);
return 0;
}
P3008 [USACO11JAN]Roads and Planes G(dijkstra, 拓扑排序, dfs)
思路:dijkstra处理不了负权边, spfa又被卡, 此时需要用到另一个知识点:在有向无环图上, 无论边权正负, 只要按照拓扑序, 就能求出到每个点的最短路径长度. 先加入m条双向边, 此时会形成若干个连通块, 用dfs求出每个连通块包含的点, 再将每个连通块看作一个点, 加入q条单向边, 构成一张有向无环图, 按照拓扑序, 用dijkstra求出每个块中的最短路即可.
#include <cstring>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int maxn = 25005, inf = 0x3f3f3f3f;
struct Edge {
int to, w;
Edge(int _to = 0, int _w = 0) : to(_to), w(_w) {}
};
vector<Edge> e[maxn];
int n, m, q, s;
int blk[maxn], tot, in[maxn]; // blk[i]:点i的连通块编号, tot:连通块数量, in:入度
vector<int> B[maxn]; // B[i]保存连通块i中包含的点
int dist[maxn], vis[maxn];
void dfs(int u, int id) {
blk[u] = id;
B[id].push_back(u);
for (int i = 0; i < (int)e[u].size(); ++i) {
int v = e[u][i].to;
if (!blk[v])
dfs(v, id);
}
}
int main() {
scanf("%d%d%d%d", &n, &m, &q, &s);
while (m--) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
e[u].push_back(Edge(v, w));
e[v].push_back(Edge(u, w));
}
// dfs求连通块
for (int i = 1; i <= n; ++i) {
if (!blk[i]) {
dfs(i, ++tot);
}
}
// 加入单向边, 并统计入度
while (q--) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
e[u].push_back(Edge(v, w));
if (blk[u] != blk[v])
++in[blk[v]];
}
memset(dist, 0x3f, sizeof dist);
memset(vis, 0, sizeof vis);
dist[s] = 0;
queue<int> q;
for (int i = 1; i <= tot; ++i) {
if (!in[i]) {
q.push(i);
}
}
while (q.size()) {
int id = q.front();
q.pop();
priority_queue<pair<int, int>> pq;
for (int i = 0; i < (int)B[id].size(); ++i) {
int u = B[id][i];
pq.push(make_pair(-dist[u], u));
}
while (pq.size()) {
int u = pq.top().second;
pq.pop();
if (vis[u])
continue;
vis[u] = 1;
for (int i = 0; i < (int)e[u].size(); ++i) {
int v = e[u][i].to, w = e[u][i].w;
if (!vis[v] && dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
if (blk[v] == blk[u])
pq.push(make_pair(-dist[v], v));
}
if (blk[v] != blk[u]) {
--in[blk[v]];
if (!in[blk[v]]) {
q.push(blk[v]);
}
}
}
}
}
for (int i = 1; i <= n; ++i) {
if (dist[i] > inf / 2)
puts("NO PATH");
else
printf("%d\n", dist[i]);
}
return 0;
}
Choose the best route (超级源点+dijkstra)
思路: 利用超级源点s, 对w个点分别建边<s, $w_{i}$>, 边权为0, 再跑一边dijkstra.
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
const int maxn = 1005, inf = 0x3f3f3f3f;
struct Edge{
int to, w;
Edge(int _to = 0, int _w = 0):to(_to), w(_w){}
};
vector<Edge> e[maxn];
int n, m, t, s, w, dist[maxn], vis[maxn];
void dijkstra(int s = 1) {
memset(dist, 0x3f, sizeof dist);
memset(vis, 0, sizeof vis);
dist[s] = 0;
priority_queue<pair<int, int>> q;
q.push(make_pair(0, s));
while (q.size()) {
int u = q.top().second;
q.pop();
if (vis[u]) continue;
vis[u] = 1;
for (int i = 0; i < (int)e[u].size(); ++i) {
int v = e[u][i].to, w = e[u][i].w;
if (!vis[v] && dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
q.push(make_pair(-dist[v], v));
}
}
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
while (cin >> n >> m >> t) {
for (int i = 0; i <= n; ++i) e[i].clear();
while (m--) {
int u, v, w;
cin >> u >> v >> w;
e[u].push_back(Edge(v, w));
}
cin >> w;
while (w--) {
int v;
cin >> v;
e[s].push_back(Edge(v, 0));
}
dijkstra(s);
if (dist[t] == inf) cout << -1 << '\n';
else cout << dist[t] << '\n';
}
return 0;
}
P4011 孤岛营救问题 (bfs, 状态压缩)
思路:如果没有门, 那么本题即使一道bfs, 加了钥匙后, 由于钥匙并不会消耗, 即获得一类钥匙后, 该类钥匙可以开启任意数量的对应的门, 所以再加一维表示当前拥有的钥匙情况, 可以用状态压缩.之后套用bfs模板即可.
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
const int maxn = 15;
int g[maxn][maxn][maxn][maxn], n, m, p;
int key[maxn][maxn];
int dist[maxn][maxn][1 << maxn];
const int dr[] = {1, -1, 0, 0}, dc[] = {0, 0, 1, -1};
struct State {
int r, c, st;
State(int _r = 0, int _c = 0, int _st = 0) : r(_r), c(_c), st(_st) {}
};
int bfs(int sr, int sc, int tr, int tc) {
if (sr == tr && sc == tc)
return 0;
memset(dist, -1, sizeof dist);
dist[sr][sc][key[sr][sc]] = 0;
queue<State> q;
q.push(State(sr, sc, key[sr][sc]));
while (q.size()) {
State u = q.front();
q.pop();
int r = u.r, c = u.c, st = u.st;
for (int i = 0; i < 4; ++i) {
int vr = r + dr[i], vc = c + dc[i];
if (vr >= 1 && vr <= n && vc >= 1 && vc <= m) {
int t = g[r][c][vr][vc];
if (t == 0)
continue;
if (t == -1 || (st >> t & 1)) {
int vst = (st | key[vr][vc]);
if (dist[vr][vc][vst] == -1) {
dist[vr][vc][vst] = dist[r][c][st] + 1;
if (vr == tr && vc == tc)
return dist[vr][vc][vst];
q.push(State(vr, vc, vst));
}
}
}
}
}
return -1;
}
int main() {
cin >> n >> m >> p;
memset(g, -1, sizeof g);
int k;
cin >> k;
while (k--) {
int r, c, r2, c2, t;
cin >> r >> c >> r2 >> c2 >> t;
g[r][c][r2][c2] = g[r2][c2][r][c] = t;
}
int s;
cin >> s;
while (s--) {
int r, c, t;
cin >> r >> c >> t;
key[r][c] |= 1 << t;
}
cout << bfs(1, 1, n, m) << '\n';
return 0;
}
P1144 最短路计数(单源最短路计数)
思路:用dist[i]表示1到i的最短路径长度, cnt[i]表示1到i的最短路径条数, 由于边权都为1, 可用bfs, 且当第一次访问到点i时候, 此时1到i的最短路径已经可以确定, 之后再访问到点v时, 只需要判断当前路径长度是否等于最短路径长度, 是的话累加即可.
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
const int maxn = 1e5 + 5, mod = 100003;
vector<int> e[maxn];
int n, m;
int dist[maxn], cnt[maxn];
void bfs(int s) {
memset(dist, -1, sizeof dist);
cnt[s] = 1;
dist[s] = 0;
queue<int> q;
q.push(s);
while (q.size()) {
int u = q.front();
q.pop();
for (int i = 0; i < (int)e[u].size(); ++i) {
int v = e[u][i];
if (dist[v] == -1 || dist[v] == dist[u] + 1) {
(cnt[v] += cnt[u]) %= mod;
if (dist[v] == -1) {
dist[v] = dist[u] + 1;
q.push(v);
}
}
}
}
}
int main() {
cin >> n >> m;
while (m--) {
int u, v;
cin >> u >> v;
e[u].push_back(v);
e[v].push_back(u);
}
bfs(1);
for (int i = 1; i <= n; ++i) {
cout << cnt[i] << '\n';
}
return 0;
}
Sightseeing (单源最短路、次短路计数)
思路:本题在P1144 最短路计数的基础上加入了带权边, 以及次短路的要求, 需要用到dijkstra并多加一维状态dist[i][0]表示1到i的最短路径长度, dist[i][1]表示1到i的次最短路径长度, dist[i][1], cnt[i][0], cnt[i][1]同理.
#include <cstring>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int maxn = 1005;
struct Edge {
int to, w;
Edge(int _to = 0, int _w = 0) : to(_to), w(_w) {}
};
struct Node {
int u, t, d;
Node(int _u = 0, int _t = 0, int _d = 0) : u(_u), t(_t), d(_d) {}
bool operator<(const Node &rhs) const { return d > rhs.d; }
};
vector<Edge> e[maxn];
int n, m, s, t, dist[maxn][2], vis[maxn][2], cnt[maxn][2];
void dijkstra(int s) {
memset(vis, 0, sizeof vis);
memset(dist, 0x3f, sizeof dist);
memset(cnt, 0, sizeof cnt);
dist[s][0] = 0, cnt[s][0] = 1;
priority_queue<Node> q;
q.push(Node(s, 0, 0));
while (q.size()) {
Node state = q.top();
q.pop();
int u = state.u, t = state.t;
if (vis[u][t])
continue;
vis[u][t] = 1;
for (int i = 0; i < (int)e[u].size(); ++i) {
int v = e[u][i].to, w = e[u][i].w;
if (dist[v][0] > dist[u][t] + w) {
dist[v][1] = dist[v][0];
cnt[v][1] = cnt[v][0];
q.push(Node(v, 1, dist[v][1]));
dist[v][0] = dist[u][t] + w;
cnt[v][0] = cnt[u][t];
q.push(Node(v, 0, dist[v][0]));
} else if (dist[v][0] == dist[u][t] + w) {
cnt[v][0] += cnt[u][t];
} else if (dist[v][1] > dist[u][t] + w) {
dist[v][1] = dist[u][t] + w;
cnt[v][1] = cnt[u][t];
q.push(Node(v, 1, dist[v][1]));
} else if (dist[v][1] == dist[u][t] + w) {
cnt[v][1] += cnt[u][t];
}
}
}
}
void solve() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i)
e[i].clear();
while (m--) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
e[u].push_back(Edge(v, w));
}
scanf("%d%d", &s, &t);
dijkstra(s);
printf("%d\n", cnt[t][0] + (dist[t][0] + 1 == dist[t][1] ? cnt[t][1] : 0));
}
int main() {
int T;
scanf("%d", &T);
while (T--)
solve();
return 0;
}
Sorting It All Out(传递闭包)
思路: dist[i][j] = 1 表示i < j, 一条表达式相当于加入边, 每次加入一条边跑一边floyd求传递闭包, 判断是否出现矛盾或者已经可以确定全部的大小关系并进行记录, (矛盾表示出现i < i或i < j且j > i等情况, 可以确定全部的大小关系即对于dist[i][j]和dist[j][i]都只出现一个1),最后输出相应结果即可.由于每次只加入一条边, 并不需要跑一遍floyd, 只需根据传递性连接对应边即可
#include <cstring>
#include <iostream>
using namespace std;
const int maxn = 26;
int dist[maxn][maxn], n, m, vis[maxn];
void floyd() {
for (int k = 0; k < n; ++k)
for (int u = 0; u < n; ++u)
for (int v = 0; v < n; ++v)
if (u != v) dist[u][v] |= dist[u][k] & dist[k][v];
}
int check() {
for (int i = 0; i < n; ++i)
if (dist[i][i])
return 1;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (dist[i][j] == 1 && dist[j][i] == 1)
return 1;
}
}
bool flag = true;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (dist[i][j] == 0 && dist[j][i] == 0) {
flag = false;
break;
}
}
}
if (flag)
return 2;
return 0;
}
int get_min() {
for (int i = 0; i < n; ++i) {
if (!vis[i]) {
bool flag = true;
for (int j = 0; j < n; ++j) {
if (!vis[j] && dist[j][i] == 1) {
flag = false;
break;
}
}
if (flag) {
return i;
}
}
}
return 0;
}
int main() {
while (cin >> n >> m) {
int t = 0, p;
if (!n && !m)
break;
memset(dist, 0, sizeof dist);
for (int i = 1; i <= m; ++i) {
char s[4];
cin >> s;
int u = s[0] - 'A', v = s[2] - 'A';
if (!t) {
dist[u][v] = 1;
for (int i = 0; i < n; ++i) {
if (dist[i][u] && i != v)
dist[i][v] = 1;
if (dist[v][i] && u != i)
dist[u][i] = 1;
for (int j = 0; j < n; ++j) {
if (dist[i][u] && dist[v][j] && i != j)
dist[i][j] = 1;
}
}
// floyd();
t = check();
if (t) {
p = i;
}
}
}
if (!t) {
printf("Sorted sequence cannot be determined.\n");
} else if (t == 1) {
printf("Inconsistency found after %d relations.\n", p);
} else if (t == 2) {
// 每次选取最小值即可
memset(vis, 0, sizeof vis);
printf("Sorted sequence determined after %d relations: ", p);
for (int i = 0; i < n; ++i) {
int mn = get_min();
printf("%c", mn + 'A');
vis[mn] = 1;
}
printf(".\n");
}
}
return 0;
}
Sightseeing trip(无向图的最小环问题, floyd)
思路:已知答案的形式：u->...->v->k->u (至少3个节点) (u->...->v不经过k)
要求最小, 可以枚举u, v, 然后经过k再回到u，那么环的长度就是mindist[u, v] + w[v, k] + w[k, u], 以此更新答案 路径是 u->...->v->k->u, 先加入u, 再加入u到v之间的中间节点,
最后加入v, k
接下来的问题是求出mindist[u, v], 注意u到v之间不经过k(路径不能有重复节点)
我们可以利用1~k-1的点去更新mindistu, v
当枚举到第k次时候, 此时的mindist[u, v]就是u到v不经过k的最短距离,
然后再把k加入到环中, 尝试更新答案,
路径通过记录中间节点不难求出
#include <algorithm>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
const int maxn = 105, inf = 0x3f3f3f3f;
int g[maxn][maxn], d[maxn][maxn], n, m, pos[maxn][maxn];
vector<int> path;
void get_path(int u, int v) {
if (pos[u][v] == 0)
return;
get_path(u, pos[u][v]);
path.push_back(pos[u][v]);
get_path(pos[u][v], v);
}
int main() {
cin >> n >> m;
memset(g, 0x3f, sizeof g);
for (int i = 1; i <= n; ++i)
g[i][i] = 0;
while (m--) {
int u, v, w;
cin >> u >> v >> w;
g[u][v] = g[v][u] = min(g[u][v], w);
}
int ans = inf;
memcpy(d, g, sizeof g);
for (int k = 1; k <= n; ++k) {
for (int u = 1; u < k; ++u) {
for (int v = u + 1; v < k; ++v) {
if (1ll * d[u][v] + g[v][k] + g[k][u] < ans) {
ans = d[u][v] + g[v][k] + g[k][u];
path.clear();
path.push_back(u);
get_path(u, v);
path.push_back(v);
path.push_back(k);
}
}
}
for (int u = 1; u <= n; ++u) {
for (int v = 1; v <= n; ++v) {
if (d[u][v] > d[u][k] + d[k][v]) {
d[u][v] = d[u][k] + d[k][v];
pos[u][v] = k;
}
}
}
}
if (ans == inf)
cout << "No solution.\n";
else {
for (int i = 0; i < (int)path.size(); ++i) {
cout << path[i] << ' ';
}
cout << '\n';
}
return 0;
}
Cow Relays(经过k条边的最短路, 矩阵快速幂)
思路: 本题的边数最多只有100, 出现的不同点的个数最多为200, 先进行离散化. 令g[i][j]表示经过一条边的最短路径长度, 枚举中转点k, 求出从i到k再到j的最短路径, 得到经过两条边的最短路径, 由于该过程具有结合律, 可用矩阵快速幂进行优化.
#include <algorithm>
#include <cstring>
#include <iostream>
#include <map>
using namespace std;
const int inf = 0x3f3f3f3f;
struct Mat {
static const int maxsize = 200;
int n, a[maxsize][maxsize];
Mat(int _n = maxsize) : n(_n) { memset(a, 0, sizeof a); }
int *operator[](int i) { return a[i]; }
Mat operator*(Mat &b) {
Mat res(n);
// 这里的res并不表示经过0条边的最短路, res只是保存最小值，为了方便全部初始化为inf
memset(res.a, 0x3f, sizeof res.a);
for (int k = 0; k < n; ++k)
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
res[i][j] = min(res[i][j], a[i][k] + b[k][j]);
// 这里并不是floyd, 因为a, b都没有更新
// 假设a[i][j], b[i][j]分别表示经过k1, k2条边后i到j的最短路
// 那么res[i][j]就表示经过k1+k2条边后i到j的最短路
return res;
}
Mat operator^(long long k) {
Mat res(n); // 经过0条边的最短路
memset(res.a, 0x3f, sizeof res.a);
for (int i = 0; i < n; ++i)
res[i][i] = 0;
Mat a = (*this);
while (k > 0) {
if (k & 1)
res = res * a;
k >>= 1;
a = a * a;
}
return res;
}
void print() {
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
printf("%d%c", a[i][j], " \n"[j == n - 1]);
}
};
int m, k, s, t;
Mat g;
map<int, int> id;
int get_id(int x) {
if (id.count(x))
return id[x];
int cnt = id.size(); // 这里如果写成return id[x] = id.size() - 1 poj上过不了
return id[x] = cnt;
}
int main() {
cin >> k >> m >> s >> t;
s = get_id(s);
t = get_id(t);
memset(g.a, 0x3f, sizeof g.a);
while (m--) {
int u, v, w;
cin >> w >> u >> v;
u = get_id(u);
v = get_id(v);
g[u][v] = g[v][u] = min(g[u][v], w);
}
g.n = (int)id.size();
g = g ^ k;
cout << g[s][t] << '\n';
return 0;
}
走廊泼水节 (最小生成树)
思路:要求加完边后最小生成树为原树, 那么kruskal过程中选的边就需要是原来的树边, 在kruskal将这些树边加入最小生成树的过程中, 对于某条边的两个端点, 如果不属于同个集合, 则需要加入该边, 为了使得选的边是原来的树边, 那么加入的边中连接这两个集合的边必须严格大于原来的树边的权值. 维护一个带权并查集, 并在kruskal过程中统计答案即可.
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 6005;
struct Edge{
int u, v, w;
bool operator<(const Edge&rhs) const { return w < rhs.w; }
Edge(int _u = 0, int _v = 0, int _w = 0):u(_u), v(_v), w(_w){}
}e[maxn];
int n, fa[maxn], cnt[maxn];
int find(int x) {
if (fa[x] == x) return x;
return fa[x] = find(fa[x]);
}
void solve() {
long long ans = 0;
cin >> n;
for (int i = 0; i < n - 1; ++i) {
cin >> e[i].u >> e[i].v >> e[i].w;
}
for (int i = 1; i <= n; ++i) fa[i] = i, cnt[i] = 1;
sort(e, e + n - 1);
for (int i = 0; i < n - 1; ++i) {
int u = e[i].u, v = e[i].v, w = e[i].w;
u = find(u), v = find(v);
if (u != v) {
ans += (1ll * cnt[u] * cnt[v] - 1) * (w + 1);
fa[v] = u;
cnt[u] += cnt[v];
}
}
cout << ans << '\n';
}
int main() {
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
新的开始(最小生成树)
思路:本题对于一个点, 要么建设发电站自供, 要么加入一个连通块并接上电网, 涉及点权和边权的比较, 利用超级源点, 将点权转化为边权，再跑一边prim
#include <iostream>
#include <cstring>
using namespace std;
const int maxn = 305;
int g[maxn][maxn], n, dist[maxn], vis[maxn];
int prim() {
memset(dist, 0x3f, sizeof dist);
memset(vis, 0, sizeof vis);
int sum = 0;
dist[0] = 0;
for (int i = 0; i < n + 1; ++i) {
int u = -1;
for (int j = 0; j <= n; ++j) if (!vis[j] &&(u == -1 || dist[u] > dist[j])) u = j;
vis[u] = 1;
sum += dist[u];
for (int j = 0; j <= n; ++j) if (!vis[j] && dist[j] > g[u][j]) dist[j] = g[u][j];
}
return sum;
}
int main() {
cin >> n;
for (int i = 1; i <= n; ++i) cin >> g[0][i], g[i][0] = g[0][i];
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
cin >> g[i][j];
cout << prim() << '\n';
return 0;
}
北极通讯网络 (最小生成树)
思路: 枚举d, 舍去大于d的边, 会形成若干个连通块, 再利用卫星设备连接各个连通块, 问题转化为求满足舍去大于d的边后, 形成的连通块个数小于等于卫星设备数量的最小的d, 可以使用二分答案, 或者从前往后枚举每条边, 如果当前连通块个数小于等于卫星设备数量, 那么此时的边权就是最小的d.
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn = 505, maxm = maxn * maxn / 2;
struct Edge{
int u, v;
double w;
Edge(int _u = 0, int _v = 0, double _w = 0):u(_u), v(_v), w(_w){}
bool operator < (const Edge&rhs) const {
return w < rhs.w;
}
}e[maxm];
int n, k, fa[maxn], m;
int find(int x) {
if (fa[x] == x) return x;
return fa[x] = find(fa[x]);
}
pair<int, int> pos[maxn];
double get_dist(pair<int, int>& u, pair<int, int>& v) {
return hypot(abs(u.first - v.first), abs(u.second - v.second));
}
int main() {
cin >> n >> k;
for (int i = 1; i <= n; ++i) cin >> pos[i].first >> pos[i].second;
for (int i = 1; i <= n; ++i) {
for (int j = i + 1; j <= n; ++j) {
e[m++] = Edge(i, j, get_dist(pos[i], pos[j]));
}
}
int cnt = n;
double ans = 0;
for (int i = 1; i <= n; ++i) fa[i] = i;
sort(e, e + m);
for (int i = 0; i < m; ++i) {
if(cnt <= k) break;
int u = e[i].u, v = e[i].v;
double w = e[i].w;
u = find(u), v = find(v);
if (u != v) {
fa[u] = v;
--cnt;
ans = w;
}
}
printf("%.2f\n", ans);
return 0;
}
秘密的牛奶运输 (严格次小生成树)
思路:求出最小生成树后, 枚举每一条非树边, 加入该边后, 会形成一个环, 删除环上除了该非树边的边权最大值, 如果新生成的生成树的权重大于最小生成树, 将其考虑进答案, 在这些符合权重大于最小生成树的生成树, 严格次小生成树就是这些生成树中权值最小的那一棵.
d1[u][v]表示最小生成树上u到v路径上边权的最大值, d2[u][v]表示最小生成树上u到v路径上边权的次大值(因为要求严格次小, 所以当最小生成树上u到v路径上边权的最大值等于加入的非树边时还需要考虑最小生成树上u到v路径上边权的次大值).
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
typedef long long ll;
const int maxn = 2005, maxm = 20005;
int n, m, d1[maxn][maxn], d2[maxn][maxn], fa[maxn];
struct Edge{
int u, v, w, t; // t = 1表该边是最小生成树的边, 区分树边和非树边
bool operator < (const Edge&rhs) const {
return w < rhs.w;
}
Edge(int _u = 0, int _v = 0, int _w = 0, int _t = 0):u(_u), v(_v), w(_w), t(_t){}
}edge[maxm];
vector<pair<int, int>> e[maxn]; // 保存最小生成树
int find(int x) {
if (fa[x] == x) return x;
return fa[x] = find(fa[x]);
}
void dfs(int u, int pa, int mx1, int d1[], int mx2, int d2[]) {
d1[u] = mx1, d2[u] = mx2;
for (int i = 0; i < (int)e[u].size(); ++i) {
int v = e[u][i].first, w = e[u][i].second;
if (v == pa) continue;
if (w > mx1) {
dfs(v, u, w, d1, mx1, d2);
} else if (w < mx1 && w > mx2) {
dfs(v, u, mx1, d1, w, d2);
} else {
dfs(v, u, mx1, d1, mx2, d2);
}
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 0; i < m; ++i)
scanf("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].w);
sort(edge, edge + m);
for (int i = 1; i <= n; ++i) fa[i] = i;
ll sum = 0;
for (int i = 0 ; i < m; ++i) {
int u = edge[i].u, v = edge[i].v, w = edge[i].w;
int fu = find(u), fv = find(v);
if (fu != fv) {
edge[i].t = 1;
fa[fu] = fv;
sum += w;
e[u].push_back(make_pair(v, w));
e[v].push_back(make_pair(u, w));
}
}
for (int i = 1; i <= n; ++i) dfs(i, -1, 0, d1[i], 0, d2[i]);
ll ans = 1e18;
for (int i = 0; i < m; ++i) {
if (edge[i].t == 0) {
int u = edge[i].u, v = edge[i].v;
int w = edge[i].w, w1 = d1[u][v], w2 = d2[u][v];
if (w > w1) {
ans = min(ans, sum - w1 + w);
} else if (w > w2) {
ans = min(ans, sum - w2 + w);
}
}
}
printf("%lld\n", ans);
return 0;
}
黑暗城堡(最短路径生成树)
思路: 先用dijkstra求出1到各点的最短路径长度dist[i], 然后根据求出的dist[i]进行建树, 将这颗最短路径生成树是以1号点为根的有根树, 然后根据dist[i]从小到大依次加入其他n-1个点, 然后统计加入每个点有多少种方式, 并利用乘法原理累乘.
加点过程: 根据dist[i]从小到大枚举每个点i(1除外), 我们需要从已经加入最短路径生成树的所有点中, 选取某个点u然后与点i连一条边, 使得dist[i] = dist[u] + w[u][i], 统计这样的点有多少个, 就有多少种连边方式(加点方式), 累成完答案后将点i加入最短路径生成树, 重复上述过程, 直到所有点加入树中.
#include <cstring>
#include <iostream>
using namespace std;
typedef long long ll;
const int maxn = 1005, mod = (1ll << 31) - 1;
int g[maxn][maxn], dist[maxn], vis[maxn], n, m;
void dijkstra(int s) {
memset(vis, 0, sizeof vis);
memset(dist, 0x3f, sizeof dist);
dist[s] = 0;
for (int i = 0; i < n; ++i) {
int u = -1;
for (int j = 1; j <= n; ++j)
if (!vis[j] && (u == -1 || dist[u] > dist[j]))
u = j;
vis[u] = 1;
for (int v = 1; v <= n; ++v)
if (!vis[v] && dist[v] > dist[u] + g[u][v])
dist[v] = dist[u] + g[u][v];
}
}
int main() {
cin >> n >> m;
memset(g, 0x3f, sizeof g);
for (int i = 1; i <= n; ++i)
g[i][i] = 0;
while (m--) {
int u, v, w;
cin >> u >> v >> w;
g[u][v] = g[v][u] = min(g[u][v], w);
}
dijkstra(1);
ll ans = 1;
memset(vis, 0, sizeof vis);
vis[1] = 1;
for (int i = 0; i < n - 1; ++i) {
int u = -1;
for (int j = 2; j <= n; ++j)
if (!vis[j] && (u == -1 || dist[u] > dist[j]))
u = j;
int cnt = 0;
for (int j = 1; j <= n; ++j)
if (vis[j] && dist[j] + g[j][u] == dist[u])
++cnt;
vis[u] = 1;
(ans *= cnt) %= mod;
}
cout << ans << '\n';
return 0;
}
Picnic Planning (有度数限制的最小生成树)
思路: 由于点以字符串标识, 先将其映射成整数, 设s代表"Park", 先不考虑与s相连的边, 会形成若干个连通块, 求出每个连通块的最小生成树的权值, 然后对于每棵最小生成树, 接一条最小边和s相连, 每连一条s的度数加1, 如果连完各棵最小生成树, s的度数大于度数限制, 那么无解. 否则, 我们尝试从s向某棵最小生成树连一条权值最小的边, 此时会成环, 删除环中与s不直接相连的权值最大的边, 那么会形成一个新生成树, 如果权值变小, 就更新答案, 如果不能变小, 此时的生成树就是满足度数限制的最小生成树.
#include <algorithm>
#include <cstring>
#include <iostream>
#include <map>
#include <string>
using namespace std;
const int maxn = 105, maxm = maxn * maxn, inf = 0x3f3f3f3f;
map<string, int> id;
struct Edge {
int u, v, w;
bool operator<(const Edge &rhs) const { return w < rhs.w; }
Edge(int _u = 0, int _v = 0, int _w = 0) : u(_u), v(_v), w(_w) {}
} e[maxm]; // 所有边
int n, m, k, s, fa[maxn], g[maxn][maxn], g2[maxn][maxn], minw[maxn],
point[maxn], deg;
// g[i][j]:边i-j的权值, g2[i][j]:生成树, inf表示不存在边i-j, minw[i]:连通块i中与s相连的边的最小值, point[i]:连通块i中与s相连的点
Edge maxe[maxn]; // maxe[i]:生成树中从s到i路径上不与s之间相连的边权最大值
int find(int x) {
if (fa[x] == x)
return x;
return fa[x] = find(fa[x]);
}
int get_id(const string &s) {
if (id[s])
return id[s];
return id[s] = ++n;
}
void dfs(int u, int pa) {
for (int i = 1; i <= n; ++i) {
if (i == s || i == pa || g2[u][i] == inf)
continue;
if (u != s) {
if (maxe[u].w > g[u][i])
maxe[i] = maxe[u];
else
maxe[i] = Edge(u, i, g[u][i]);
}
dfs(i, u);
}
}
int main() {
cin >> m;
memset(g, 0x3f, sizeof g);
memset(g2, 0x3f, sizeof g2);
for (int i = 0; i < m; ++i) {
string A, B;
int L;
cin >> A >> B >> L;
int u = get_id(A), v = get_id(B);
g[u][v] = g[v][u] = min(g[u][v], L);
e[i] = Edge(u, v, g[u][v]);
}
cin >> k;
s = get_id("Park");
for (int i = 1; i <= n; ++i)
g[i][i] = 0;
for (int i = 1; i <= n; ++i)
fa[i] = i;
int ans = 0;
sort(e, e + m);
for (int i = 0; i < m; ++i) {
int u = e[i].u, v = e[i].v, w = e[i].w;
if (u == s || v == s)
continue;
int fu = find(u), fv = find(v);
if (fu != fv) {
ans += w;
fa[fu] = fv;
g2[u][v] = g2[v][u] = w;
}
}
memset(minw, 0x3f, sizeof minw);
for (int i = 1; i <= n; ++i) {
if (i != s && g[s][i] != inf) {
int fi = find(i);
if (minw[fi] > g[s][i]) {
minw[fi] = g[s][i];
point[fi] = i;
}
}
}
for (int i = 1; i <= n; ++i)
if (minw[i] != inf)
ans += minw[i], ++deg, g2[s][point[i]] = g2[point[i]][s] = minw[i];
while (deg < k) {
memset(maxe, 0, sizeof maxe);
dfs(s, -1);
int mn = inf, v;
for (int i = 1; i <= n; ++i) {
if (i != s && mn > g[s][i] - maxe[i].w) {
mn = g[s][i] - maxe[i].w;
v = i;
}
}
if (mn >= 0)
break;
g2[s][v] = g2[v][s] = maxe[v].w;
g2[maxe[v].u][maxe[v].v] = g2[maxe[v].v][maxe[v].u] = inf;
ans += mn;
++deg;
}
printf("Total miles driven: %d\n", ans);
return 0;
}