A.吃饭路上也要锻炼，原 P3505 [POI2010] TEL-Teleportation
咱现在思路通了，代码实现可能得鸽一鸽。
两个强强的博客：https://www.cnblogs.com/stoorz/p/12182770.html，https://www.cnblogs.com/reywmp/p/14014611.html。
是很难的思维题，涉及乘法原理和图论，用到了分层思想。统计答案时不重不漏导致细节巨多。
要求最大建边数，肯定不能暴力一个一个加。使用去想怎么划分成不同的集合进行统计。
考虑将图分层。
分为五层，第一层是起点，最后一层是终点。与第一层（起点）相连的放第二层，同理与终点相连的放第四层。其余剩下的点在第三层。
1.首先每一层之间的点可以相互连，因为依旧是从层内穿过，始终只能增加距离。
2.考虑中间第三层怎么连边：
（1）与第二层连边。
（2）与第四层连边。
（3）层内的点或未被任何边连的点相连。
显然第三层不能与起点、终点直接相连。
于是发现，与第二层连边的点，不能再与第四层的点直接连边，否则会出现一条长度为 4 的路径。反之亦然。
最后答案的统计：
1.层内的点都可以连。
2.第三层的点，若可以与第二层相连，则与第二层全部连一遍。
3.第三层的点，对于与第四层相连的情况同上。
B.可达家统计，原：P4306 [JSOI2010] 连通数
1.爆搜可以过。（但我的赛事爆搜只有 20pts。赛后尝试写的爆搜在洛谷可以完美的过第一个 sub，但 hack 数据根本跑不动。唯一一个不是 T 的是 WA，遂没再尝试爆搜）。
2.缩点变成有向无环图进行 dp。
3.bitset 有很多很实用的函数，+ floyd。
说一下 bitset 的做法：
如果 i 能到达 j，那么 j 所能到达的点 i 都能到达。
所以将需要维护的边存到 bitset 里就可以直接从 j 传给 i。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2010;
int n;
ll ans;
bitset<N> a[N];
void floyd()
{
for(int i = 1; i <= n; i ++ )
for(int j = 1; j <= n; j ++ )
if(a[j][i]) a[j] |= a[i];
}
int main()
{
scanf("%d", &n);
char ch[N];
for(int i = 1; i <= n; i ++ )
{
scanf("%s", ch + 1);
for(int j = 1; j <= n; j ++ ) a[i][j] = ch[j] - '0';
a[i][i] = 1;
}
floyd();
printf("%lld", ans);
}
C.时空穿梭与高空滑索，原：P2573 [SCOI2012] 滑雪
考虑先建一个图，然后第一问用 dfs 扩展求能到达的个数。
第二问需要用最小生成树。为了最小生成树跑到的边都是能扩展到的，我们再重新建一个图，存从起点开始可以扩展到的点，来跑一遍 kruskal。
需要注意的是，再 kruskal 的排序中，我们以一条边的终点高度为第一关键字，以边权为第二关键字。这么做的目的，是因为你的终点高度越高才能扩展到更多的边。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e6 + 10;
const int inf = 0x7fffffff;
ll ans;
int n, m, sum = 1;
int h[N], vis[N], fa[N];
int idx, e[N], nxt[N], w[N], head[N];
int idxn;
struct node{int u, v, w;}edg[N];
bool cmp(node x, node y)
{
if(h[x.v] == h[y.v]) return x.w < y.w;
return h[x.v] > h[y.v];
}
void add(int x, int y, int z)
{
e[++ idx] = y;
w[idx] = z;
nxt[idx] = head[x];
head[x] = idx;
}
int fd(int x)
{
if(fa[x] == x) return x;
return fa[x] = fd(fa[x]);
}
void dfs(int x)
{
for(int i = head[x]; i; i = nxt[i])
{
edg[++ idxn].u = x;
edg[idxn].v = e[i];
edg[idxn].w = w[i];
if(! vis[e[i]])
{
sum ++;
vis[e[i]] = 1;
dfs(e[i]);
}
}
}
void kruskal()
{
sort(edg + 1 , edg + idxn + 1 , cmp);
for(int i = 1; i <= idxn; i ++ )
{
int xx = fd(edg[i].u), yy = fd(edg[i].v);
if(xx == yy) continue;
fa[xx] = yy;
ans += edg[i].w ;
}
}
int main()
{
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i ++ ) scanf("%d", &h[i]), fa[i] = i;
while(m -- )
{
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
if(h[x] >= h[y]) add(x, y, z);
if(h[x] <= h[y]) add(y, x, z);
}
vis[1] = 1;
dfs(1);
kruskal();
printf("%d %lld", sum, ans);
return 0;
}
需要思考：kruskal 的 sort 为什么要这么写。
以及本题另一个解法是用最小树形图，朱刘算法。
D.岗哨站在哨岗上，原：bzoj 4883.棋盘上的守卫
考察怎么把问题抽象建图的方法。怎样把网格图中，点的代价，变为二分图中边的代价。
最小生成树，但要特殊处理环：
如果选的边的两个点：
1.在同一连通块，且在一个环里，不能选。
2.如果两点都在环里，不能。
3，不连通，选，判断一侧有误环。
本题一些细节我现在还是不太懂，待实现。
本次模拟赛的 A、D 都是很有难度的。B、C 相对来说更典更好想。
标签：连边,idxn,idx,int,第三层,8.21,小记,模拟,edg From： https://www.cnblogs.com/Moyyer-suiy/p/17646744.html