8.29 模拟赛小记。
A.时间复杂度，洛谷原题指路：P1522 [USACO2.4] 牛的旅行 Cow Tours
首先为啥从 100pts -> 88-> 77。因为打完第一遍之后感觉思路不太对，少考虑了一个部分，然后加了一个并查集。挂分是因为连通块合并写挂了（基础还能错是我有罪）。所以属实没想到第一遍能 AC，那份码在洛谷上会被 hack 掉，oj 数据这么弱啊 qwq。
后来看原发现我在远古时期（指两年前）就提交过，但思路同第一份一样错了所以也被 hack 了。没记错的话是一本通上有这道题，但那上面的思路考虑的就不全，书上的码会被卡掉。题外话，怪不得现在入门都不看一本通了。
以下是正文。
求将两个不在同一牧场的点连到一起后新牧场直径的最小值，先考虑用并查集预处理连通块。
暴力的枚举，先跑 floyd 初始化。然后用 mx[i] 表示从 i 号点出发到距离它最远的点的距离，t[i] 表示 i 号连通块的直径（该连通块内所有点的 mx[i] 的 max）。
最后考虑依次枚举考虑如果两个点 i、j 不在同一连通块中，它们之间如果连起来后得到的新牧场的直径大小。
新牧场的直径大小考虑三种情况，i 号连通块的直径，j 号联通块的直径，i 号点能到的最远距离加上 j 号点能到的最远距离再加上 i、j 之间的距离。
即 minn = min(minn, max(mx[i] + mx[j] + dis(i, j), max(t[fd(i)], t[fd(j)])));
#include<bits/stdc++.h>
using namespace std;
typedef double db;
const int N = 202;
const db inf = 0x3fffffff;
char c[N];
int n, m;
int fa[N];
db x[N], y[N];
db f[N][N], mx[N], t[N];
db dis(int i, int j) {return sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));}
int fd(int x)
{
if(fa[x] == x) return x;
return fa[x] = fd(fa[x]);
}
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i ++ )
{
fa[i] = i;
scanf("%lf%lf", &x[i], &y[i]);
}
for(int i = 1; i <= n; i ++ )
{
scanf("%s", c + 1);
for(int j = 1; j <= n; j ++ )
{
if(c[j] == '1')
{
f[i][j] = dis(i, j);
fa[fd(i)] = fd(j);
}
else if(i != j) f[i][j] = inf;
}
}
for(int k = 1; k <= n; k ++ )
for(int i = 1; i <= n; i ++ )
for(int j = 1; j <= n; j ++ ) f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
for(int i = 1; i <= n; i ++ )
{
for(int j = 1; j <= n; j ++ ) if(fd(i) == fd(j)) mx[i] = max(mx[i], f[i][j]);
t[fd(i)] = max(t[fd(i)], mx[i]);
}
db minn = inf;
for(int i = 1; i <= n; i ++ )
for(int j = 1; j <= n; j ++ )
if(fd(i) != fd(j))
{
minn = min(minn, max(mx[i] + mx[j] + dis(i, j), max(t[fd(i)], t[fd(j)])));
}
printf("%.6lf", minn);
return 0;
}
B.“快速米”变速自行车-认真分析数据范围，洛谷原题指路：P1613 跑路
一看到 2^k 就想到倍增了，还是很好想的。f[i][j][k] 表示从 i 到 j 行驶 \(2 ^ k\) 是否能到达，若 \(2 ^ {k - 1}\) 能到达则 \(2^k\) 也可以。再跑一遍 floyd 就可以。
以及，你考虑输出 1 是能骗很多分的。想一想就会发现其他答案的数据会比较难造。
#include<bits/stdc++.h>
using namespace std;
const int N = 55;
const int K = 70;
int n, m, s, t;
int f[N][N][K], dis[N][N];
int main()
{
scanf("%d%d", &n, &m);
memset(dis, 0x3f, sizeof dis);
for(int i = 1; i <= m; i ++ )
{
scanf("%d%d", &s, &t);
f[s][t][0] = 1;
dis[s][t] = 1;
}
for(int t = 0; t < 64; t ++ )
for(int i = 1; i <= n; i ++ )
for(int j = 1; j <= n; j ++ )
for(int k = 1; k <= n; k ++ )
if(f[i][k][t] && f[k][j][t])
{
f[i][j][t + 1] = 1;
dis[i][j] = 1;
}
for(int k = 1; k <= n; k ++ )
for(int i = 1; i <= n; i ++ )
for(int j = 1; j <= n; j ++ )
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
printf("%d", dis[1][n]);
}
C.最短路-认真读题防陷阱，洛谷原题指路：P2886 [USACO07NOV] Cow Relays G
1.要读好题，本题的输入顺序是数 w, u, v。
2.oj 上输出 -1 有 14pts。我赛时一直在调 A 导致忘了交码了。
让你正好走 n 条边。边数为 100，n 为 1e6，直接跑 floyd 一定会超时。所以考虑优化重复跑的过程，不难想到倍增。
然后就会发现是跑很多遍 floyd，跑了之后更新矩阵、再跑。会发现这个过程有点类似于矩阵乘法。不会矩阵乘法快速幂的请移步去看板子：P3390 【模板】矩阵快速幂。
floyd 和矩阵乘法都有 3 个 for，这就有点异曲同工之妙了。
所以以类似矩阵乘法的方式，快速幂里面套跑 floyd 的新矩阵每次转移就好力！
注意：
1.一共需要转移 n - 1 次而不是 n 次。
2.边数只有 100，给的点编号却有 1000，所以需要离散化。
3.oj 上需要判断 -1，洛谷上不用。
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
const int inf = 0x3f3f3f3f;
int n, t, s, e;
int tot, v[N];
struct M{
int a[120][120];
M operator *(const M &x) const
{
M b;
memset(b.a, inf, sizeof b.a);
for(int k = 1; k <= tot; k ++ )
for(int i = 1; i <= tot; i ++ )
for(int j = 1; j <= tot; j ++ )
b.a[i][j] = min(b.a[i][j], a[i][k] + x.a[k][j]);
return b;
}
}dis, ans;
int main()
{
memset(dis.a, inf, sizeof dis.a);
scanf("%d%d%d%d", &n, &t, &s, &e);
while(t -- )
{
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
if(! v[y]) v[y] = ++ tot;
if(! v[z]) v[z] = ++ tot;
dis.a[v[y]][v[z]] = dis.a[v[z]][v[y]] = x;
}
n --;
ans = dis;
while(n)
{
if(n & 1) ans = ans * dis;
dis = dis * dis;
n >>= 1;
}
printf("%d", ans.a[v[s]][v[e]]);
return 0;
}