好不容易终于做完了，（最后一题是黑题并且还是数学不想做）所谓“做了不总结==没做”，特此写一下常用函数和思路吧。
一些基本模板函数：
long long findroot(long long x) {
return x == rt[x] ? x : rt[x] = findroot(rt[x]);
}
void un(long long x, long long y) {
rt[findroot(x)] = findroot(y);
}
int kruskal() {
sort(Alledge.begin(), Alledge.end(), cmp);
int ans = 0;
int total = 0;
for (auto it : Alledge) {
int xr = findroot(it.u), yr = findroot(it.v);
if (xr != yr) {
un(xr, yr);
MSTedge.push_back({ it.u,it.v,it.w,it.pos });
ans += it.w;
total++;
}
}
return ans;
}
Alledge就是所有的边，MSTedge就是用以最小生成树的边。显然MSTedge包含于Alledge。
题E~G都是最小生成树的模板题，就不多说了，套上面的函数就行了......
这个博客会按个人主观难度来排序题目。
I - 公路修建问题
洛谷：https://www.luogu.com.cn/problem/P2323
“ 花费最多的一条公路的花费尽可能的少 ”，可以二分......具体一点就是二分修路的花费。因为花费和道路类型是独立的，在我给出的花费上界内，如果能有k条以上一级路并且能够连通，那么就是true;否则false。
排序：
sort(e + 1, e + 1 + cnt, cmp);
这里二分的就是花费，l=1是最小边权，r=30000是题目给出的最大边权。
int l = 1, r = 30000;
while (l < r) {
int mid = (l + r) >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
check函数要完成如下任务：
1.找到在指定最大边权（花费、上界）的边的位置。
2.进行kruskal算法，判断是否满足之前提到的两个条件：1.有生成树；2.有k个以上的一级道路。（多了说明可以换成2级，这个任务在二分时完成）
要保证有k个以上一级道路，我们跑两次kruskal（后面有道题也是，通过多次跑kruskal解决）
一次是尽量选一级道路，一次是再仍未连通时选二级道路。
如果最后:一级道路<k或未成树，返回false。否则返回true。
bool check(int ma) {
for (int i = 1; i <= n; i++) {
father[i] = i;
}
//cout << "now check " << ma << endl;
int r = cnt, l = 1;
while (l < r) {
//cout << "l and r: " << l << " " << r << endl;
int mid = (l + r + 1) >> 1;
if (e[mid].val <= ma) l = mid;
else r = mid - 1;
}
int total = 0;
int type1 = 0;
vector<answer> isitans;
for (int i = 1; i <= r; i++) {
if (e[i].type == 2) continue;
int xr = findroot(e[i].from), yr = findroot(e[i].to);
if (xr != yr) {
//cout << "link: " << xr << " " << yr << endl;
un(xr, yr);
isitans.push_back({ e[i].type,e[i].pos });
total++;
type1++;
//cout << "type1++, now is " << type1 << endl;
}
if (total >= (n - 1) and type1 >= k) {
ans.clear();
for (answer& it : isitans) {
ans.push_back({ it.type,it.pos });
}
return true;
}
}
for (int i = 1; i <= r; i++) {
if (e[i].type == 1) continue;
int xr = findroot(e[i].from), yr = findroot(e[i].to);
if (xr != yr) {
//cout << "link: " << xr << " " << yr << endl;
un(xr, yr);
isitans.push_back({ e[i].type,e[i].pos });
total++;
}
if (total >= (n - 1) and type1 >= k) {
ans.clear();
for (answer& it : isitans) {
ans.push_back({ it.type,it.pos });
}
return true;
}
}
return false;
}
ans就是存ans...
完整代码：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct edge {
int from, to, val, type, pos;
}e[40005];
struct answer {
int type, pos;
};
int father[20005] = { 0 };
int n, m, k;
int cnt = 0;
vector<answer> ans;
bool cmp(edge& a, edge& b) {
return a.val < b.val || (a.val == b.val and a.type < b.type);
}
bool cmpans(answer& a, answer& b) {
return a.pos < b.pos;
}
int findroot(int x) {
return father[x] == x ? x : father[x] = findroot(father[x]);
}
void un(int a, int b) {
father[findroot(a)] = findroot(b);
}
bool check(int ma) {
for (int i = 1; i <= n; i++) {
father[i] = i;
}
//cout << "now check " << ma << endl;
int r = cnt, l = 1;
while (l < r) {
//cout << "l and r: " << l << " " << r << endl;
int mid = (l + r + 1) >> 1;
if (e[mid].val <= ma) l = mid;
else r = mid - 1;
}
int total = 0;
int type1 = 0;
vector<answer> isitans;
for (int i = 1; i <= r; i++) {
if (e[i].type == 2) continue;
int xr = findroot(e[i].from), yr = findroot(e[i].to);
if (xr != yr) {
//cout << "link: " << xr << " " << yr << endl;
un(xr, yr);
isitans.push_back({ e[i].type,e[i].pos });
total++;
type1++;
//cout << "type1++, now is " << type1 << endl;
}
if (total >= (n - 1) and type1 >= k) {
ans.clear();
for (answer& it : isitans) {
ans.push_back({ it.type,it.pos });
}
return true;
}
}
for (int i = 1; i <= r; i++) {
if (e[i].type == 1) continue;
int xr = findroot(e[i].from), yr = findroot(e[i].to);
if (xr != yr) {
//cout << "link: " << xr << " " << yr << endl;
un(xr, yr);
isitans.push_back({ e[i].type,e[i].pos });
total++;
}
if (total >= (n - 1) and type1 >= k) {
ans.clear();
for (answer& it : isitans) {
ans.push_back({ it.type,it.pos });
}
return true;
}
}
return false;
}
int main()
{
cin >> n >> k >> m;
m--;
int x, y, v, nv;
for (int i = 1; i <= m; i++) {
cin >> x >> y >> v >> nv;
e[++cnt].from = x, e[cnt].to = y, e[cnt].val = v, e[cnt].type = 1, e[cnt].pos = i;
e[++cnt].from = x, e[cnt].to = y, e[cnt].val = nv, e[cnt].type = 2, e[cnt].pos = i;
}
sort(e + 1, e + 1 + cnt, cmp);
int l = 1, r = 30000;
while (l < r) {
int mid = (l + r) >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
cout << l << endl;
sort(ans.begin(), ans.end(), cmpans);
for (answer it : ans) {
cout << it.pos << " " << it.type << endl;
}
return 0;
}
J - 免费道路
洛谷https://www.luogu.com.cn/problem/P3623
上一题的威力加强版，相当于要求刚好k个一级道路。大概不能用二分，其余思路与上一题相同：先尽量用二级道路看看能不能成树，如果这个过程中用到了一级，那就先把这条路存起来。下次初始化并查集后，在kruskal前用上。
如何让程序有时后尽量用一级，有时候尽量用二级呢？在排序上做手脚就行了。
对kruskal算法有了更深的认识：
bool cmp(Edge& a, Edge& b) {
return a.w < b.w;
}
bool recmp(Edge& a, Edge& b) {
return a.w > b.w;
}
完整代码（评价为最水紫题）
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
struct Edge
{
int u, v, w, pos;
};
bool cmp(Edge& a, Edge& b) {
return a.w < b.w;
}
bool recmp(Edge& a, Edge& b) {
return a.w > b.w;
}
int n, m, k;
int cnt;
int root[20005] = { 0 };
vector<Edge> Alledge;
vector<Edge> MSTedge;
vector<Edge> Ansedge;
set<int> use;
int findroot(int x) {
return x == root[x] ? x : root[x] = findroot(root[x]);
}
void un(int x, int y) {
root[findroot(x)] = findroot(y);
}
int kruskal() {
sort(Alledge.begin(), Alledge.end(), cmp);
int ans = 0;
int total = 0;
for (auto it : Alledge) {
int xr = findroot(it.u), yr = findroot(it.v);
if (xr != yr) {
un(xr, yr);
if (it.w) Ansedge.push_back({ it.u,it.v,it.w,it.pos });
ans += it.w;
total++;
}
}
if (total < n - 1) {
cout << "no solution";
exit(0);
}
return ans;
}
int ans_kruskal() {
sort(Alledge.begin(), Alledge.end(), recmp);
for (int i = 1; i <= n; i++) root[i] = i;
for (auto it : Ansedge) {
int xr = findroot(it.u), yr = findroot(it.v);
if (xr != yr) {
un(xr, yr);
}
}
for (auto it : Alledge) {
if (cnt == k and it.w) continue;
int xr = findroot(it.u), yr = findroot(it.v);
if (xr != yr) {
un(xr, yr);
cnt += it.w;
Ansedge.push_back({ it.u,it.v,it.w,it.pos });
}
}
return 0;
}
int main() {
cin >> n >> m >> k;
for (int i = 1; i <= n; i++) root[i] = i;
int x, y, t;
for (int i = 1; i <= m; i++) {
cin >> x >> y >> t;
t ^= 1;
Alledge.push_back({ x,y,t,i });
}
cnt = kruskal();
if (cnt > k) {
cout << "no solution";
return 0;
}
ans_kruskal();
if (cnt < k) {
cout << "no solution";
return 0;
}
for (auto it : Ansedge) {
cout << it.u << " " << it.v << " " << (it.w ^ 1) << endl;
}
return 0;
}
K - 最小生成树计数
模板题，考察对高斯公式的运用。
涉及到的知识点有：1.矩阵树定理（求行列式）；2.缩点。
矩阵树定理见：https://oi-wiki.org/graph/matrix-tree/，主要用以求生成树个数。
缩点：将当前所计算的边权以外，最小生成树需要的边所连的点给连上，并将他们所在的每个联通域视作一个点。
遍历所有边权即可。
long long gE(long long n) {
long long ans = 1, w = 1;
for (long long i = 2; i <= n; i++) {
for (long long j = i + 1; j <= n; j++) {
while (Laplace[i][i]) {
long long div = Laplace[j][i] / Laplace[i][i];
for (long long k = i; k <= n; k++) {
Laplace[j][k] = (Laplace[j][k] - (div * Laplace[i][k]) % mod + mod) % mod;
}
swap(Laplace[i], Laplace[j]);
w = -w;
}
swap(Laplace[i], Laplace[j]);
w = -w;
}
}
for (long long i = 2; i <= n; i++) ans = ans * Laplace[i][i] % mod;
ans *= w;
return (ans + mod) % mod;
}
完整代码：
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
using namespace std;
struct Edge
{
long long from, to, val, id;
}e[1005];
long long srt[105] = { 0 };
long long rt[105] = { 0 };
long long Degree[105][105] = { 0 };
long long Adjacency[105][105] = { 0 };
long long Laplace[105][105] = { 0 };
long long n, m;
map<long long, vector<long long>> cnt;
set<long long> use;
vector<long long> use_edge;
const long long mod = 31011;
vector<Edge> use_kk;
bool cmp(Edge& a, Edge& b) {
return a.val < b.val;
}
long long findroot(long long x) {
return rt[x] == x ? x : rt[x] = findroot(rt[x]);
}
void un(long long x, long long y) {
rt[findroot(x)] = findroot(y);
}
void kruskal() {
for (long long i = 0; i < m; i++) {
long long xr = findroot(use_kk[i].from), yr = findroot(use_kk[i].to);
if (xr != yr) {
un(xr, yr);
use.insert(use_kk[i].val);
use_edge.push_back(use_kk[i].id);
}
}
}
void init_Laplace() {
for (long long i = 1; i <= n; i++) {
srt[i] = rt[i] = i;
for (long long j = 1; j <= n; j++) {
Laplace[i][j] = Degree[i][j] = Adjacency[i][j] = 0;
}
}
}
long long gE(long long n) {
long long ans = 1, w = 1;
for (long long i = 2; i <= n; i++) {
for (long long j = i + 1; j <= n; j++) {
while (Laplace[i][i]) {
long long div = Laplace[j][i] / Laplace[i][i];
for (long long k = i; k <= n; k++) {
Laplace[j][k] = (Laplace[j][k] - (div * Laplace[i][k]) % mod + mod) % mod;
}
swap(Laplace[i], Laplace[j]);
w = -w;
}
swap(Laplace[i], Laplace[j]);
w = -w;
}
}
for (long long i = 2; i <= n; i++) ans = ans * Laplace[i][i] % mod;
ans *= w;
return (ans + mod) % mod;
}
int main()
{
cin >> n >> m;
long long x, y, w;
for (long long i = 1; i <= n; i++) rt[i] = i;
for (long long i = 1; i <= m; i++) {
cin >> x >> y >> w;
e[i].from = x, e[i].to = y, e[i].val = w;
e[i].id = i;
cnt[e[i].val].push_back(i);
use_kk.push_back({ x,y,w,i });
}
sort(use_kk.begin(), use_kk.end(), cmp);
kruskal();
long long ans = 1;
for (auto& it : cnt) { //it.first:边权，it.second:使用的边的集合。
if (!use.count(it.first)) continue;//没用过就跳。
init_Laplace();
long long val = it.first;
vector<long long> same_edge_index = it.second;
for (auto it : use_edge) {
if (e[it].val == val) continue;//现在要查的不能连。
un(e[it].from, e[it].to);//连
//cout << "link " << e[it].from << " " << e[it].to << " cost " << e[it].val << endl;
}
long long len = 0;
for (long long i = 1; i <= n; i++) {
if (rt[i] == i) srt[i] = ++len;//统计有几个独立点。
}
for (long long i = 1; i <= n; i++) srt[i] = srt[findroot(i)];//给每个不独立的找独立点作为父亲。
for (long long i : same_edge_index) {
long long x = srt[e[i].from], y = srt[e[i].to];
//cout << "link " << e[i].from << " " << e[i].to << " cost " << e[i].val << endl;
Adjacency[x][y]++;
Adjacency[y][x]++;
Degree[x][x]++;
Degree[y][y]++;
}
for (long long i = 1; i <= len; i++) {
for (long long j = 1; j <= len; j++) {
Laplace[i][j] = Degree[i][j] - Adjacency[i][j];
}
}
/*
if (val == 3) {
for (long long i = 1; i <= len; i++) {
for (long long j = 1; j <= len; j++) {
cout << Laplace[i][j] << " ";
}
cout << endl;
}
}*/
//cout << gE(len) << endl;
ans = (ans * gE(len) % mod) % mod;
}
cout << ans;
return 0;
}
L - 严格次小生成树
模板题，见https://oi-wiki.org/graph/mst/。涉及到了LCA、在LCA的过程维护最大值和次大值。
kruskal求出树后：
dfs建表：
void dfs(long long now, long long from) {
st_root[now][0] = from;
dep[now] = dep[from] + 1;
st_2thmax[now][0] = -1e18;
for (long long i = 1; i <= 32; i++) {
st_root[now][i] = st_root[st_root[now][i - 1]][i - 1];
long long val[4] = { st_max[now][i - 1],st_max[st_root[now][i - 1]][i - 1],
st_2thmax[now][i - 1],st_2thmax[st_root[now][i - 1]][i - 1] };
sort(val, val + 4);
st_max[now][i] = val[3];
long long _2th = 2;
while (_2th >= 0 and val[_2th] == val[3]) _2th--;
st_2thmax[now][i] = _2th >= 0 ? val[_2th] : -1e18;
}
for (long long i = 0; i < e[now].size(); i++) {
if (e[now][i].v == from) continue;
st_max[e[now][i].v][0] = e[now][i].w;
dfs(e[now][i].v, now);
}
}
LCA:
long long LCA(long long x, long long y) {
if (dep[x] > dep[y]) swap(x, y);
long long dis = dep[y] - dep[x];
for (long long j = 0; dis; j++, dis >>= 1)
if (dis & 1) y = st_root[y][j];
if (x == y) return y;
for (long long j = 32; y != x and j >= 0; --j) {
if (st_root[x][j] != st_root[y][j]) {
x = st_root[x][j];
y = st_root[y][j];
}
}
return st_root[y][0];
}
查询关于某边的次大值：注意使用该函数的前提是：b一定是a的祖先。
long long query(long long a, long long b, long long w) {
long long res = -1e18;
for (long long i = 32; i >= 0; i--) {
if (dep[st_root[a][i]] >= dep[b]) {
if (w > st_max[a][i]) res = max(res, st_max[a][i]);
else res = max(res, st_2thmax[a][i]); //即w==st_max[a][i]时
a = st_root[a][i];
}
}
return res;
}
遍历边：
for (auto it : Alledge) {
if (!use.count(it.pos)) {
long long lca = LCA(it.u, it.v);
long long a = query(it.u, lca, it.w);
long long b = query(it.v, lca, it.w);
if (max(a, b) > -1e18) {
ans = min(ans, MST_sum - max(a, b) + it.w);
}
}
}
!use.count(it.pos)保证：使用的是不在最小生成树的边；以这个边所连两点，先查询公共祖先，再查询两个点到祖先路径上的关于it.w的次大值，求max就是a->b的关于it.w的次大值。
注意：it.w肯定是>=a->b路径上的所有边的，否则这个树就不是最小生成树，因为可以被it替换以创造最小生成树。在query中，其实便是就it.w=还是it.w>的情况讨论。
完整代码：
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
struct Edge
{
long long u, v, w, pos;
};
bool cmp(Edge& a, Edge& b) {
return a.w < b.w;
}
vector<Edge> e[300005];
vector<Edge> Alledge;
vector<Edge> MSTedge;
set<long long> use;
long long st_root[100005][33] = { 0 };
long long st_max[100005][33] = { 0 };
long long st_2thmax[100005][33] = { 0 };
long long dep[100005] = { 0 };
long long root[100005] = { 0 };
void dfs(long long now, long long from) {
st_root[now][0] = from;
dep[now] = dep[from] + 1;
st_2thmax[now][0] = -1e18;
for (long long i = 1; i <= 32; i++) {
st_root[now][i] = st_root[st_root[now][i - 1]][i - 1];
long long val[4] = { st_max[now][i - 1],st_max[st_root[now][i - 1]][i - 1],
st_2thmax[now][i - 1],st_2thmax[st_root[now][i - 1]][i - 1] };
sort(val, val + 4);
st_max[now][i] = val[3];
long long _2th = 2;
while (_2th >= 0 and val[_2th] == val[3]) _2th--;
st_2thmax[now][i] = _2th >= 0 ? val[_2th] : -1e18;
}
for (long long i = 0; i < e[now].size(); i++) {
if (e[now][i].v == from) continue;
st_max[e[now][i].v][0] = e[now][i].w;
dfs(e[now][i].v, now);
}
}
long long LCA(long long x, long long y) {
if (dep[x] > dep[y]) swap(x, y);
long long dis = dep[y] - dep[x];
for (long long j = 0; dis; j++, dis >>= 1)
if (dis & 1) y = st_root[y][j];
if (x == y) return y;
for (long long j = 32; y != x and j >= 0; --j) {
if (st_root[x][j] != st_root[y][j]) {
x = st_root[x][j];
y = st_root[y][j];
}
}
return st_root[y][0];
}
long long findroot(long long x) {
return x == root[x] ? x : root[x] = findroot(root[x]);
}
void un(long long x, long long y) {
root[findroot(x)] = findroot(y);
}
long long kruskal() {
long long ans = 0;
sort(Alledge.begin(), Alledge.end(), cmp);
for (auto it : Alledge) {
long long xr = findroot(it.u), yr = findroot(it.v), val = it.w;
if (xr != yr) {
un(xr, yr);
ans += it.w;
MSTedge.push_back({ it.u,it.v,it.w,it.pos });
use.insert(it.pos);
}
}
return ans;
}
long long query(long long a, long long b, long long w) {
long long res = -1e18;
for (long long i = 32; i >= 0; i--) {
if (dep[st_root[a][i]] >= dep[b]) {
if (w != st_max[a][i]) res = max(res, st_max[a][i]);
else res = max(res, st_2thmax[a][i]);
a = st_root[a][i];
}
}
return res;
}
int main()
{
long long n, m;
cin >> n >> m;
long long x, y, w;
for (long long i = 1; i <= n; i++) root[i] = i;
for (long long i = 1; i <= m; i++) {
cin >> x >> y >> w;
Alledge.push_back({ x,y,w,i });
}
long long MST_sum = kruskal();
//cout << MST_sum;
for (auto& it : MSTedge) {
e[it.u].push_back({ it.u,it.v,it.w,it.pos });
e[it.v].push_back({ it.v,it.u,it.w,it.pos });
}
dfs(1, 0);
long long ans = 1e18;
for (auto it : Alledge) {
if (!use.count(it.pos)) {
long long lca = LCA(it.u, it.v);
long long a = query(it.u, lca, it.w);
long long b = query(it.v, lca, it.w);
if (max(a, b) > -1e18) {
ans = min(ans, MST_sum - max(a, b) + it.w);
}
}
}
cout << ((ans == 1e18) ? -1 : ans) << endl;
return 0;
}
A - 丁香之路
第I题和第J题的威力加强加强版。现在我们边有边权，又有必须要经过的边，现在要最小化花费，怎么办呢？
好在这个图的边权有一个良好性质：比如，如果我要在1到9之间连边，那么连1-9和连1-2-3-4-5-6-7-8-9，花费是一样的，而且显然连1-2-3-4-5-6-7-8-9更好。
因为不能通过改边权的手脚来kruskal，我们只能假设：那些必要边已被连上。
问题一：如何计算连上必要边的花费？
达：按照题目所给规则加起来即可。
问题二：这些边可能没被连在一起（不形成路径）。如何使它们相连？
答：正如上文所说的那个性质，我们将点从小到大排序。回想一下，“遍历所有边”和哪个问题很像？没错，欧拉回路。我们要在s点和n点之间连虚边（不计算花费的边）。这条虚边的作用，就是让s点和n点之间形成连通块，变成解欧拉回路的题，在每个奇数度的点之间，按照类似1-2-3-4-5-6-7-8-9（1和9是奇数度）的方式连边，多多益善，尽量变成大的连通块，方便后续我们让这些连通块连通。
现在，我们有了几个连通块，现在只要把它们连通就行了。有些朋友会想到缩点，但这里是缩不了的，因为边权和点的序号有关。
我们再把点按序号从小到大遍历，以当前的最近的有度数的点作为待连点，与下一个不同连通域的点相连。由于有时候会出现1-9属于同一连通域，而5-6-7-8属于同一连通域，此时直接贪心是不可行的，所以全部边都选上，再排序跑一边kruskal才行。
vector<edge> e;
for (int i = 1; i <= n; i++) {
if (deg[i]) {
if (pre && findroot(srt[i]) != findroot(srt[pre]))
e.push_back({ srt[i], srt[pre], abs(i - pre) });
pre = i;
}
}
为什么最后每个连接：连通块的边权要加两次？
我们的目标是，求经过某些必要边，从起点s到n的欧拉路径（回路），其中s和n构成一个起始连通块。另一个连通块走完后，我们肯定要回到原来的连通块（因为s和n在同一连通块），这时候，到另一个连通块时，走了那条边一次，回来，又走了一次。所以要加两次。
sort(e.begin(), e.end(), cmp);
for (int i = 0; i < e.size(); i++) {
int xr = findroot(e[i].from), yr = findroot(e[i].to);
if (xr != yr) {
un(xr, yr), ans += e[i].val * 2;
}
}
完整代码（其实也不长）：
#include<algorithm>
#include <iostream>
#include <vector>
using namespace std;
int n, m, s;
const int N = 2505;
struct edge {
int from, to, val;
};
bool cmp(edge a, edge b) {
return a.val < b.val;
}
int rt[2505] = { 0 };
int srt[2505] = { 0 };
int low = 0;
int deg[2505] = { 0 };
int sdeg[2505] = { 0 };
int findroot(int x)
{
return x == rt[x] ? x : rt[x] = findroot(rt[x]);
}
void un(int x, int y) {
rt[findroot(x)] = findroot(y);
}
void solve(int t) {
{
for (int i = 1; i <= n; i++)rt[i] = i, deg[i] = sdeg[i];
deg[s]++, deg[t]++;
un(srt[s], srt[t]);
int ans = low, pre = 0;
for (int i = 1; i <= n; i++)
if (deg[i] % 2) {
un(srt[i], srt[i + 1]);
deg[i]++, deg[i + 1]++;
ans++;
}
vector<edge> e;
for (int i = 1; i <= n; i++) {
if (deg[i]) {
if (pre && findroot(srt[i]) != findroot(srt[pre]))
e.push_back({ srt[i], srt[pre], abs(i - pre) });
pre = i;
}
}
sort(e.begin(), e.end(), cmp);
for (int i = 0; i < e.size(); i++) {
int xr = findroot(e[i].from), yr = findroot(e[i].to);
if (xr != yr) {
un(xr, yr), ans += e[i].val * 2;
}
}
cout << ans << " ";
}
}
int main()
{
cin >> n >> m >> s;
for (int i = 1; i <= n; i++)rt[i] = i;
int x, y;
for (int i = 1; i <= m; i++) {
cin >> x >> y;
sdeg[x]++, sdeg[y]++;
low += abs(x - y);
un(x, y);
}
for (int i = 1; i <= n; i++) srt[i] = findroot(i);
for (int i = 1; i <= n; i++) solve(i);
return 0;
}
srt的意思是static root。
(相对与rt(root)来说......)
sdeg的意思是static degree。
(相对与deg来说......)
B - Make It Connected
数学题。每个点有自己的点权，边权是两个点权的相加。
给这些点按点权排序，给边也按边权排序。
对于排序的点，用l和r两个指针（l<r）找到当前最小连点权，对于排序的边，用一个指针i即可，贪心选择已有边还是直接建边。(为什么这样行？因为kruskal的原理就是这个......)
显然l=1,r=2时是点权之和最小的。尽量只推r，r推到最后再推l（但没有这种可能，因为如果r推到最后，图肯定已经连通了......）
所以其它点只要与点权最小点连通就行了......
但这是蒟蒻我做这道题的代码的思路，所以请读者自行优化......（删去l就行了......）
while (total < n - 1) {
if (i > m or cost[l].val + cost[r].val < e[i].w) {
xr = findroot(cost[l].pos), yr = findroot(cost[r].pos), val = cost[l].val + cost[r].val;
if (xr != yr) {
un(xr, yr);
total++;
ans += val;
}
else {
if (r < n) r++;
else l++;
}
}
else {
xr = findroot(e[i].u), yr = findroot(e[i].v), val = e[i].w;
i++;
if (xr != yr) {
un(xr, yr);
total++;
ans += val;
}
}
}
完整代码：
#include <iostream>
#include <algorithm>
using namespace std;
struct edge
{
unsigned long long u, v, w;
}e[200005];
struct Cost {
unsigned long long val, pos;
}cost[200005];
bool cmpEdge(edge& a, edge& b) {
return a.w < b.w;
}
bool cmpCost(Cost& a, Cost& b) {
return a.val < b.val;
}
unsigned long long n, m;
unsigned long long root[200005] = { 0 };
unsigned long long findroot(unsigned long long x) {
return root[x] == x ? x : root[x] = findroot(root[x]);
}
void un(unsigned long long x, unsigned long long y) {
root[findroot(x)] = findroot(y);
}
int main()
{
cin >> n >> m;
for (unsigned long long i = 1; i <= n; i++) {
cin >> cost[i].val;
cost[i].pos = i;
root[i] = i;
}
for (unsigned long long i = 1; i <= m; i++) {
cin >> e[i].u >> e[i].v >> e[i].w;
}
sort(cost + 1, cost + 1 + n,cmpCost);
sort(e + 1, e + 1 + m, cmpEdge);
unsigned long long total = 0;
unsigned long long ans = 0;
unsigned long long xr, yr, val;
unsigned long long l = 1, r = 2;
unsigned long long i = 1;
while (total < n - 1) {
if (i > m or cost[l].val + cost[r].val < e[i].w) {
xr = findroot(cost[l].pos), yr = findroot(cost[r].pos), val = cost[l].val + cost[r].val;
if (xr != yr) {
un(xr, yr);
total++;
ans += val;
}
else {
if (r < n) r++;
else l++;
}
}
else {
xr = findroot(e[i].u), yr = findroot(e[i].v), val = e[i].w;
i++;
if (xr != yr) {
un(xr, yr);
total++;
ans += val;
}
}
}
std::cout << ans;
return 0;
}
C - Takeout Delivering
数学题。总花费定义为最大边和次大边之和。
评价为——从1到n跑dijkstra，再从n到1跑dijkstra,跑dijkstra的过程就是尽量选最小边的过程，因此记录到每个顶点的最大边，枚举每一条边，记该边连的点是u和v，如果从1到u的最大边和从n到v的最大边都小于它，那么这条边可能就是最大边，1到u和v到n的最大边中有一个就是次大边。
最后最小化这个连接u、v的最大边即可(因为它可能不在dijkstra的路径上，最小化获得的就是在的。)
所以这和最小生成树有什么关系......
代码：
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstdio>
using namespace std;
struct edge
{
vector<pair<long long, long long>> link;
}e[300005];
struct node
{
long long dis, pos;
bool operator >(const node& a) const { return dis > a.dis; }
};
long long vis[300005] = { 0 };
long long dis1[300005] = { 0 };
long long disn[300005] = { 0 };
long long n, m;
priority_queue<node, vector<node>, greater<node>> pq;
void dij(long long s,long long dis[]) {
fill(dis + 1, dis + n + 1, 1e12);
fill(vis + 1, vis + n + 1, 0);
dis[s] = 0;
pq.push({ 0,s });
while (!pq.empty())
{
long long d = pq.top().dis, pos = pq.top().pos;
pq.pop();
if (vis[pos]) continue;
vis[pos] = 1;
for (auto& it : e[pos].link) {
long long v = it.first, w = it.second;
if (vis[v] or max(d, w) >= dis[v]) continue;
dis[v] = max(d, w);
pq.push({ dis[v],v });
}
}
}
int main() {
scanf("%lld%lld", &n, &m);
long long u, v, w;
for (long long i = 1; i <= m;i++) {
scanf("%lld%lld%lld", &u, &v, &w);
e[u].link.push_back({ v,w });
e[v].link.push_back({ u,w });
}
dij(1, dis1);
dij(n, disn);
long long res = 1e12;
for (long long i = 1; i <= n; i++) {
for (long long j = 0; j < e[i].link.size(); j++) {
long long u = i, v = e[i].link[j].first, w = e[i].link[j].second;
if (max(dis1[u], disn[v]) <= w)
res = min(res, w + max(dis1[u], disn[v]));
if (max(disn[u], dis1[v]) <= w)
res = min(res, w + max(disn[u], dis1[v]));
}
}
cout << res;
return 0;
}
dijkstra获得的是个树，好像还是最小生成树。所以也算是最小生成树算法（？）
D - A Simple MST Problem
数学题。两点之间的距离定义为它们公倍数的不同素因子的个数，求最小生成树。
l<r。若1属于这个范围，全部往1连即可（对于这些数学问题，1一直都是比较特殊的）。
若1不属于：
1.对于每一个数，连接其倍数的代价最小。
2.若连接质数，代价仅仅+1。
3.若没质数，说明范围小，直接穷举。
所以：
先将每个数与它的倍数连接起来。
此时分成若干连通块。将各个连通块与质数相连即可。
为什么行？因为贪心是kruskal算法的原理......
代码：
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <numeric>
#include <set>
#define MAXN 1000000
using namespace std;
struct Edge
{
long long u, v;
};
long long l, r, t;
long long rt[MAXN + 1] = { 0 };
vector<int> w(MAXN + 1, 1);
vector<int> cnt(MAXN + 1, 0);
vector<bool> is_prime(MAXN + 1, 1);
vector<int> prime;
//vector<Edge> e;
long long findroot(long long x) {
return x == rt[x] ? x : rt[x] = findroot(rt[x]);
}
void un(long long x, long long y) {
rt[findroot(x)] = findroot(y);
}
void Es() {
is_prime[0] = is_prime[1] = 0;
for (int i = 2; i <= MAXN; i++) {
if (is_prime[i]) {
prime.push_back(i);
for (int j = i; j <= MAXN; j += i) {
is_prime[j] = 0;
w[j] *= i;
cnt[j]++;
}
}
}
}
int main()
{
Es();
cin >> t;
while (t--) {
cin >> l >> r;
int ans = 0;
if (l == 1) {
for (int i = 2; i <= r; i++) ans += cnt[i];
cout << ans << endl;
continue;
}
int p = *lower_bound(prime.begin(), prime.end(), l);
if (p > r) {
vector<Edge> e[50];
for (int i = l; i <= r; i++) {
for (int j = i + 1; j <= r; j++) {
int val = cnt[i] + cnt[j] - cnt[gcd(i, j)];
e[val].push_back({ i,j });
}
}
for (int i = l; i <= r; i++) rt[i] = i;
for (int i = 0; i < 50; i++) {
for (auto [u, v] : e[i]) {
int xr = findroot(u), yr = findroot(v);
if (xr != yr) {
un(xr, yr);
ans += i;
}
}
}
cout << ans << endl;
continue;
}
set<int> s;
for (int i = l; i <= r; i++) {
if (i == p) continue;
if (w[i] == p) ans++;
else {
if (s.count(w[i])) ans += cnt[i];
else s.insert(w[i]);
}
}
vector<int> vis(r + 1, 0);
for (auto it : s) {
if (vis[it]) ans += cnt[it];
else {
ans += cnt[it] + cnt[p] - cnt[gcd(it, p)];
for (int i = it; i <= r; i+=it) vis[i] = 1;
}
}
cout << ans << endl;
}
return 0;
}
cnt是不同素因子的计数，w是不同素因子的乘积，方便后面对权重的计算。w(lcm(x,y)) = w(x)+w(y)-w(gcd(x,y))。读者思考一下就能理解它是对的，但是如果我在考场上，肯定已经直接跳过了......
因为它本质是数学题......
M - 地震后的幻想乡
数学题。
真不想做。
没做。
所以没代码。
标签：val,int,long,st,2025,哈工大,ACM,root,findroot From： https://www.cnblogs.com/tomorin/p/18679927