@Dmaxiya
2020-08-25T00:40:29.000000Z
字数 17011
阅读 1102
Hello_World
给一棵 个节点的无色的树上色,对于每一次上色,选择一个点后,可以将这个点所对应的子树都图上同一种颜色,现在给定树的结构,问最少需要上几次颜色,能够使得每个节点的颜色和题目表示的颜色相同。
从根节点(下标为 的节点)开始往下 ,只要父节点和子节点的颜色不同,就将答案加一,最后输出答案。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 10000 + 100;
int n, tmp;
int color[maxn];
vector<int> G[maxn];
int dfs(int x) {
int ret = 0;
int len = G[x].size();
for(int i = 0; i < len; ++i) {
int pos = G[x][i];
ret += dfs(pos);
ret += (color[pos] != color[x]);
}
return ret;
}
int main() {
#ifdef LOCAL
freopen("test.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
#endif // LOCAL
ios::sync_with_stdio(false);
while(scanf("%d", &n) != EOF) {
for(int i = 1; i <= n; ++i) {
G[i].clear();
}
for(int i = 2; i <= n; ++i) {
scanf("%d", &tmp);
G[tmp].push_back(i);
}
for(int i = 1; i <= n; ++i) {
scanf("%d", &color[i]);
}
printf("%d\n", dfs(1) + 1);
}
return 0;
}
从所有的胜利者向失败者连一条有向边,然后进行拓扑排序(最开始将所有入度为零的点加入队列,再进行宽搜,对于每个弹出队列的点,将它的后继节点的入度减一,如果某个后继节点的入度为零,则进入队列),由于题目要求输出字典序最小的,所以将队列改成优先队列即可。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 600;
int n, m, u, v;
int cnt, ans[maxn];
vector<int> G[maxn];
int deg[maxn];
priority_queue<int, vector<int>, greater<int> > que;
void topsort() {
cnt = 0;
for(int i = 1; i <= n; ++i) {
if(deg[i] == 0) {
que.push(i);
}
}
while(!que.empty()) {
int tmp = que.top();
que.pop();
ans[cnt++] = tmp;
int len = G[tmp].size();
for(int i = 0; i < len; ++i) {
int pos = G[tmp][i];
--deg[pos];
if(deg[pos] == 0) {
que.push(pos);
}
}
}
}
int main() {
#ifdef LOCAL
freopen("test.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
#endif // LOCAL
ios::sync_with_stdio(false);
while(scanf("%d%d", &n, &m) != EOF) {
for(int i = 1; i <= n; ++i) {
G[i].clear();
}
for(int i = 0; i < m; ++i) {
scanf("%d%d", &u, &v);
G[u].push_back(v);
++deg[v];
}
topsort();
for(int i = 0; i < cnt; ++i) {
if(i != 0) {
printf(" ");
}
printf("%d", ans[i]);
}
printf("\n");
}
return 0;
}
故事太长略去,就是在一个 的迷宫内找到任意两点最短距离的最大值。
这题是裸的求树的直径(从任意一点开始,找到离这个点最远的点 ,再从 点找到另一个离 点最远的点 , 和 之间的距离就是树的直径)的题目,但是树上是没有环的,所以求路径长度就是最短路径,这题相当于是有环的图,所以就按照题目要求求出任意两点最短路径,作为“树”上距离,然后求直径就行了。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 1000 + 100;
struct Node {
int x, y;
Node() {}
Node(int xx, int yy) {
x = xx;
y = yy;
}
};
int T, n, m, x, y;
char str[maxn][maxn];
queue<Node> que;
int step[maxn][maxn];
const int dir[4][2] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
bool in(int x, int y) {
return x >= 0 && x < n && y >= 0 && y < m;
}
void bfs() {
memset(step, -1, sizeof(step));
step[x][y] = 0;
que.push(Node(x, y));
while(!que.empty()) {
Node tmp = que.front();
que.pop();
for(int i = 0; i < 4; ++i) {
int xx = tmp.x + dir[i][0];
int yy = tmp.y + dir[i][1];
if(in(xx, yy) && step[xx][yy] == -1 && str[xx][yy] == '.') {
step[xx][yy] = step[tmp.x][tmp.y] + 1;
que.push(Node(xx, yy));
if(step[xx][yy] > step[x][y]) {
x = xx;
y = yy;
}
}
}
}
}
int main() {
#ifdef LOCAL
freopen("test.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
#endif // LOCAL
ios::sync_with_stdio(false);
scanf("%d", &T);
while(T--) {
scanf("%d%d", &m, &n);
for(int i = 0; i < n; ++i) {
scanf("%s", str[i]);
for(int j = 0; j < m; ++j) {
if(str[i][j] == '.') {
x = i;
y = j;
}
}
}
bfs();
bfs();
printf("Maximum rope length is %d.\n", step[x][y]);
}
return 0;
}
题解题目已经给出。
这题数据出水了,没有用并查集判连通块也被你们过了,但是后面如果碰到判断欧拉路的问题,一定要记得先判连通块。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 10000 + 100;
int n, m, u, v;
bool flag;
int fa[maxn], deg[maxn];
void Init() {
flag = true;
memset(deg, 0, sizeof(deg));
for(int i = 1; i <= n; ++i) {
fa[i] = i;
}
}
int Find(int x) {
return (x == fa[x]? x: fa[x] = Find(fa[x]));
}
void unit(int x, int y) {
int xx = Find(x);
int yy = Find(y);
fa[xx] = yy;
}
int main() {
#ifdef LOCAL
freopen("test.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
#endif // LOCAL
ios::sync_with_stdio(false);
while(scanf("%d%d", &n, &m) != EOF) {
Init();
for(int i = 0; i < m; ++i) {
scanf("%d%d", &u, &v);
unit(u, v);
++deg[u];
++deg[v];
}
for(int i = 2; i <= n; ++i) {
if(Find(i) != Find(1)) {
flag = false;
break;
}
}
if(!flag) {
printf("Part\n");
continue;
}
int cnt = 0;
for(int i = 1; i <= n; ++i) {
cnt += (deg[i] % 2);
}
if(cnt == 0 || cnt == 2) {
printf("Full\n");
} else {
printf("Part\n");
}
}
return 0;
}
题解题目已经给出,主要代码也在第一页给出。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 5000 + 100;
struct Node {
int pos;
int Index;
Node() {}
Node(int p, int I) {
pos = p;
Index = I;
}
};
struct Edge {
int u, v;
};
int n, m, cnt, u, v;
int deg[maxn];
bool vis[maxn];
Edge ans[maxn];
vector<Node> G[maxn];
void dfs(int x) {
int len = G[x].size();
for(int i = 0; i < len; ++i) {
int pos = G[x][i].pos;
int Index = G[x][i].Index;
if(!vis[Index]) {
vis[Index] = true;
dfs(pos);
ans[cnt].u = x;
ans[cnt++].v = pos;
}
}
}
int main() {
#ifdef LOCAL
freopen("test.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
#endif // LOCAL
ios::sync_with_stdio(false);
while(scanf("%d%d", &n, &m) != EOF) {
cnt = 0;
memset(vis, 0, sizeof(vis));
for(int i = 1; i <= n; ++i) {
G[i].clear();
deg[i] = 0;
}
for(int i = 0; i < m; ++i) {
scanf("%d%d", &u, &v);
G[u].push_back(Node(v, i));
G[v].push_back(Node(u, i));
++deg[u];
++deg[v];
}
for(int i = 1; i <= n; ++i) {
if(deg[i] % 2 == 1) {
u = i;
break;
}
}
dfs(u);
for(int i = cnt - 1; i >= 0; --i) {
printf("%d ", ans[i].u);
}
printf("%d\n", ans[0].v);
}
return 0;
}
题解题目已经给出。这题涉及到位运算可能不太熟悉,其实位运算的 ~ 和逻辑运算符的 非常类似,只是将数字转化为二进制数后进行按位“与或非”,这里以 和 为例:
还有两个是左移和右移运算符,对于正数,左移运算符将 的所有二进制位向高位移动,溢出部分直接舍去,低位补 ,右移运算符将 的所有二进制位向低位移动,溢出部分直接社区,高位补 ,负数只是将补 改为补 ,这里以 为例:
还有一个不太好理解的可能就是为什么题目用那样的构图方法,我看起来感觉题目已经说得很清楚了,如果有什么问题的话可以私戳我,说明具体是哪个地方没看懂。
这题的过题代码就加一些注释吧。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = (1 << 15); // 实际上只需要 1 << 14,可以想一想为什么
struct Node {
int pos; // 表示节点所代表的数字,就是图示中的两位二进制数,范围:[0,(1<<14)-1]
int weight; // 表示边权,就是图示中的三位二进制数,范围:[0,(1<<15)-1]
Node() {}
Node(int p, int w) {
pos = p;
weight = w;
}
};
int n, cnt;
int ans[maxn];
vector<Node> G[maxn];
bool vis[maxn];
// 寻找欧拉路经
void dfs(int x) {
int len = G[x].size();
for(int i = 0; i < len; ++i) {
int pos = G[x][i].pos;
int weight = G[x][i].weight;
if(!vis[weight]) {
vis[weight] = true;
dfs(pos);
ans[cnt++] = weight;
}
}
}
int main() {
#ifdef LOCAL
freopen("test.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
#endif // LOCAL
ios::sync_with_stdio(false);
while(scanf("%d", &n) != EOF) {
cnt = 0;
memset(vis, 0, sizeof(vis));
int up = (1 << (n - 1)); // 节点范围为 [0,(1<<(n-1))-1]
for(int i = 0; i < up; ++i) {
G[i].clear();
}
for(int i = 0; i < up; ++i) {
G[i].push_back(Node(((i << 1) & (~up)), (i << 1)));
G[i].push_back(Node((((i << 1) & (~up)) | 1), (i << 1 | 1)));
// 这里取 ~up 只是一巧合,实际上应该是 ~(1<<(n-1))(恰好等于 up),与上这个值的作用是去掉 i<<1 的最高位
}
dfs(0);
for(int i = cnt - 1; i >= 0; --i) {
printf("%d", (ans[i] & 1));
// 输出欧拉路径,其实这里于上的值可以为 [1,1<<1,1<<2,...,1<<(n-1)],因为是环上的 01 是循环的,所以取边权的任意位都是对的
}
printf("\n");
}
return 0;
}
单源最短路裸题。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 300;
struct Node {
int pos;
int dis;
Node() {}
Node(int p, int d) {
pos = p;
dis = d;
}
};
bool operator<(const Node &a, const Node &b) {
return a.dis > b.dis;
}
int INF;
int n, m, u, v, d, s, t;
int dis[maxn];
vector<Node> G[maxn];
priority_queue<Node> que;
void dij(int s) {
memset(dis, 0x3f, sizeof(dis));
dis[s] = 0;
que.push(Node(s, 0));
while(!que.empty()) {
Node tmp = que.top();
que.pop();
int len = G[tmp.pos].size();
for(int i = 0; i < len; ++i) {
int pos = G[tmp.pos][i].pos;
d = G[tmp.pos][i].dis;
if(dis[pos] > dis[tmp.pos] + d) {
dis[pos] = dis[tmp.pos] + d;
que.push(Node(pos, dis[pos]));
}
}
}
}
int main() {
#ifdef LOCAL
freopen("test.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
#endif // LOCAL
ios::sync_with_stdio(false);
memset(&INF, 0x3f, sizeof(int));
while(scanf("%d%d", &n, &m) != EOF) {
for(int i = 0; i < n; ++i) {
G[i].clear();
}
for(int i = 0; i < m; ++i) {
scanf("%d%d%d", &u, &v, &d);
G[u].push_back(Node(v, d));
G[v].push_back(Node(u, d));
}
scanf("%d%d", &s, &t);
dij(s);
if(dis[t] == INF) {
printf("-1\n");
} else {
printf("%d\n", dis[t]);
}
}
return 0;
}
故事太长。问题就是在一个 个节点, 条边的有向图上,求从起点到所有车站的花费 ,以及从所有车站回到起点的花费总和。
找起点到其他所有点的最短路,就直接从起点开始跑一遍最短路,找所有其他点到起点的花费总和,可以将所有边反向,然后从起点开始跑一遍最短路。注意虽然每一条最短路最大值为 ,但是所有最短路的总和就要爆 了,所以计算最短路的过程中可以用 ,而求和的时候必须用 储存。
一不小心找了一道卡常题,失误失误,不过看你们被 的地方好像不是很难处理,虽然数据量比较大,但是不卡 ,用 又不取消同步被卡,就是自己的问题了。这题我被卡的地方是开了两个邻接链表数组,只开一个的话就能过,比较玄学就是了。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 1000000 + 100;
struct Node {
int pos;
int dis;
Node() {}
Node(int p, int d) {
pos = p;
dis = d;
}
};
bool operator<(const Node &a, const Node &b) {
return a.dis > b.dis;
}
int T, n, m;
int u[maxn], v[maxn], d[maxn];
LL ans;
int dis[maxn];
vector<Node> G[maxn];
priority_queue<Node> que;
void Clear() {
for(int i = 1; i <= n; ++i) {
G[i].clear();
}
}
void dij(int s) {
memset(dis, 0x3f, sizeof(int) * (n + 1));
dis[s] = 0;
que.push(Node(s, 0));
while(!que.empty()) {
Node tmp = que.top();
que.pop();
int len = G[tmp.pos].size();
for(int i = 0; i < len; ++i) {
int pos = G[tmp.pos][i].pos;
int d = G[tmp.pos][i].dis;
if(dis[pos] > tmp.dis + d) {
dis[pos] = tmp.dis + d;
que.push(Node(pos, dis[pos]));
}
}
}
for(int i = 1; i <= n; ++i) {
ans += dis[i];
}
}
int main() {
#ifdef LOCAL
freopen("test.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
#endif // LOCAL
ios::sync_with_stdio(false);
scanf("%d", &T);
while(T--) {
ans = 0;
scanf("%d%d", &n, &m);
Clear();
for(int i = 0; i < m; ++i) {
scanf("%d%d%d", &u[i], &v[i], &d[i]);
G[u[i]].push_back(Node(v[i], d[i]));
}
dij(1);
Clear();
for(int i = 0; i < m; ++i) {
G[v[i]].push_back(Node(u[i], d[i]));
}
dij(1);
printf("%lld\n", ans);
}
return 0;
}
在一个 个节点, 条边的有向图中,从给定的 个点中,找到这些点到终点 最短路径的最小值。
同样地,每条边都反向构图,然后从 点开始跑一遍最短路。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 1000 + 100;
struct Node {
int pos;
int dis;
Node() {}
Node(int p, int d) {
pos = p;
dis = d;
}
};
bool operator<(const Node &a, const Node &b) {
return a.dis > b.dis;
}
int INF;
int n, m, s, u, v, d, w, ans;
int dis[maxn];
vector<Node> G[maxn];
priority_queue<Node> que;
void dij() {
dis[s] = 0;
que.push(Node(s, 0));
while(!que.empty()) {
Node tmp = que.top();
que.pop();
int len = G[tmp.pos].size();
for(int i = 0; i < len; ++i) {
int pos = G[tmp.pos][i].pos;
d = G[tmp.pos][i].dis;
if(dis[pos] > tmp.dis + d) {
dis[pos] = tmp.dis + d;
que.push(Node(pos, dis[pos]));
}
}
}
}
int main() {
#ifdef LOCAL
freopen("test.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
#endif // LOCAL
ios::sync_with_stdio(false);
memset(&INF, 0x3f, sizeof(int));
while(scanf("%d%d%d", &n, &m, &s) != EOF) {
for(int i = 1; i <= n; ++i) {
G[i].clear();
dis[i] = INF;
}
for(int i = 0; i < m; ++i) {
scanf("%d%d%d", &u, &v, &d);
G[v].push_back(Node(u, d));
}
dij();
ans = INF;
scanf("%d", &w);
for(int i = 0; i < w; ++i) {
scanf("%d", &u);
ans = min(ans, dis[u]);
}
if(ans == INF) {
printf("-1\n");
} else {
printf("%d\n", ans);
}
}
return 0;
}
裸题,但是不是多源最短路,而是最长路,安全系数的计算方式为乘法。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const double eps = 1e-6;
const int maxn = 1000 + 100;
int n, q, u, v;
double G[maxn][maxn];
bool zero(const double &x) {
return fabs(x) < eps;
}
int main() {
#ifdef LOCAL
freopen("test.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
#endif // LOCAL
ios::sync_with_stdio(false);
while(scanf("%d", &n) != EOF) {
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= n; ++j) {
scanf("%lf", &G[i][j]);
}
}
for(int k = 1; k <= n; ++k) {
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= n; ++j) {
G[i][j] = max(G[i][j], G[i][k] * G[k][j]);
}
}
}
scanf("%d", &q);
for(int i = 0; i < q; ++i) {
scanf("%d%d", &u, &v);
if(zero(G[u][v])) {
printf("What a pity!\n");
} else {
printf("%.3f\n", G[u][v]);
}
}
}
return 0;
}
在一个 个节点的图上, 将按顺序破坏图上所有的 条边,问每破坏一条边,剩余的连通块有多少个。
将破坏的顺序反过来,变成加边的顺序,就可以用并查集统计连通块的个数了。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 10000 + 100;
const int maxm = 100000 + 100;
struct Node {
int u, v;
};
int n, m;
Node node[maxm];
int fa[maxn], ans[maxm];
void Init() {
for(int i = 0; i < n; ++i) {
fa[i] = i;
}
}
int Find(int x) {
return (x == fa[x]? x: fa[x] = Find(fa[x]));
}
void unit(int x, int y) {
int xx = Find(x);
int yy = Find(y);
fa[xx] = yy;
}
int main() {
#ifdef LOCAL
freopen("test.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
#endif // LOCAL
ios::sync_with_stdio(false);
while(scanf("%d%d", &n, &m) != EOF) {
Init();
for(int i = 1; i <= m; ++i) {
scanf("%d%d", &node[i].u, &node[i].v);
}
int cnt = n;
ans[m] = cnt;
for(int i = m; i >= 1; --i) {
int u = node[i].u;
int v = node[i].v;
if(Find(u) != Find(v)) {
--cnt;
unit(u, v);
}
ans[i - 1] = cnt;
}
for(int i = 1; i <= m; ++i) {
printf("%d\n", ans[i]);
}
}
return 0;
}
裸的最小生成树问题,用克鲁斯卡尔就可以解决。最后注意要先判是否能够全连通。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 200;
struct Node {
int u, v;
int dis;
};
bool operator<(const Node &a, const Node &b) {
return a.dis < b.dis;
}
int n, m, ans;
int fa[maxn];
Node node[maxn];
void Init() {
ans = 0;
for(int i = 1; i <= n; ++i) {
fa[i] = i;
}
}
int Find(int x) {
return (x == fa[x]? x: fa[x] = Find(fa[x]));
}
void unit(int x, int y) {
int xx = Find(x);
int yy = Find(y);
fa[xx] = yy;
}
int main() {
#ifdef LOCAL
freopen("test.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
#endif // LOCAL
ios::sync_with_stdio(false);
while(scanf("%d%d", &m, &n), m != 0) {
Init();
for(int i = 0; i < m; ++i) {
scanf("%d%d%d", &node[i].u, &node[i].v, &node[i].dis);
}
sort(node, node + m);
for(int i = 0; i < m; ++i) {
int u = node[i].u;
int v = node[i].v;
if(Find(u) != Find(v)) {
unit(u, v);
ans += node[i].dis;
}
}
int f = Find(1);
bool flag = true;
for(int i = 1; i <= n; ++i) {
if(Find(i) != f) {
flag = false;
break;
}
}
if(flag) {
printf("%d\n", ans);
} else {
printf("?\n");
}
}
return 0;
}
有 个卫星和 个哨站,如果某一个位于点 的哨站上有卫星,就可以与其他任何一个有卫星的哨站相互通信,如果没有,就只能和距离自己不超过 的其他哨站通信,问要使得所有哨站之间相互通信,这个 的最小值是多少。
要求最短的 ,就是在完全图上求最小生成树上距离最大的边,但是由于有卫星的哨站可以与任何其他有卫星的哨站联系,而不受距离限制,所以如果把每个有卫星的哨站分到不同的连通块里,也能使所有哨站相互通信。为使 最小,可以将生成树中最长的几条边去掉,去完边后,在不同的连通块内的任意一点放卫星。由于树上删边,删一条边多一个连通块,所以最多可以删 条边。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 600;
struct Node {
int u, v;
int dis;
};
bool operator<(const Node &a, const Node &b) {
return a.dis < b.dis;
}
struct Point {
int x, y;
};
double ans;
int T, s, p, cnt;
Node node[maxn * maxn];
Point point[maxn];
int fa[maxn];
int get_dis(int i, int j) {
int dx = point[i].x - point[j].x;
int dy = point[i].y - point[j].y;
return dx * dx + dy * dy;
}
void Init() {
for(int i = 0; i < p; ++i) {
fa[i] = i;
}
}
int Find(int x) {
return (x == fa[x]? x: fa[x] = Find(fa[x]));
}
void unit(int x, int y) {
int xx = Find(x);
int yy = Find(y);
fa[xx] = yy;
}
int main() {
#ifdef LOCAL
freopen("test.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
#endif // LOCAL
ios::sync_with_stdio(false);
scanf("%d", &T);
while(T--) {
cnt = 0;
scanf("%d%d", &s, &p);
Init();
for(int i = 0; i < p; ++i) {
scanf("%d%d", &point[i].x, &point[i].y);
for(int j = 0; j < i; ++j) {
node[cnt].u = i;
node[cnt].v = j;
node[cnt].dis = get_dis(i, j);
++cnt;
}
}
sort(node, node + cnt);
int cnt_ans = 0;
for(int i = 0; i < cnt; ++i) {
int u = node[i].u;
int v = node[i].v;
if(Find(u) != Find(v)) {
++cnt_ans;
unit(u, v);
if(cnt_ans == p - s) {
ans = sqrt((double)node[i].dis);
break;
}
}
}
printf("%.2f\n", ans);
}
return 0;
}