A.加速器 洛谷原题指路：P4822 [BJWC2012] 冻结
就是一个分层图的板子。建 k 层图，然后相邻的两层相连时边权除以二即可。
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, m, k;
int vis[N], ans[N];
int idx, head[N], w[N], nxt[N], e[N];
struct node{
int u, dis;
bool operator <(const node& x) const{
return x.dis < dis;
}
};
void add(int x, int y, int z)
{
e[++ idx] = y;
w[idx] = z;
nxt[idx] = head[x];
head[x] = idx;
}
void dij()
{
priority_queue<node> q;
q.push((node){1, 0});
while(q.size())
{
int x = q.top().u;
q.pop();
vis[x] = 1;
for(int i = head[x]; i; i = nxt[i])
{
if(! vis[e[i]] && ans[e[i]] > ans[x] + w[i])
{
ans[e[i]] = ans[x] + w[i];
q.push((node){e[i], ans[e[i]]});
}
}
}
}
int main()
{
scanf("%d%d%d", &n, &m, &k);
while(m -- )
{
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
for(int j = 0; j <= k; j ++ ) add(j * n + x, j * n + y, z), add(j * n + y, j * n + x, z);
for(int j = 0; j < k; j ++ ) add(j * n + x, (j + 1) * n + y, z / 2), add(j * n + y, (j + 1) * n + x, z / 2);
}
for(int i = 1; i <= n * k + n; i ++ ) ans[i] = 0x7fffffff;
ans[1] = 0;
dij();
int minn = 0x7fffffff;
for(int i = 0; i <= k; i ++ ) minn = min(minn, ans[i * n + n]);
printf("%d", minn);
return 0;
}
B.没有矛盾的舞会 洛谷原题指路：P2607 [ZJOI2008] 骑士
只要你会 P1352 没有上司的舞会 就发现是一样的套路，唯一的区别是 P1352 有 n 个点 n - 1 条边，是一棵树，而本题有 n 个点，必然存在一条边。这就是基环树了（去掉基环树里的环，它就是一颗普通的树）。
基环树是图不是树。
那我们要做的就是破环为链，然后将得到的两个链跑 dp 求一个 max，其余思路与 P1352 相同。
C.奶牛串门 洛谷原题指路：P3469 [POI2008] BLO-Blockade
需要讨论这个点是否是割点，用 tarjan 缩点同时记录连通块大小，利用乘法原理统计。
D.过路费 洛谷原题指路：P2245 星际导航
需要最小生成树。
一种做法是 kruskal + lca。
另一种老师刚讲的 kruskal 同构树，你会发现神奇的性质，然后就能做了。