说是有N个村庄,刚开始每个村庄的网络都是受损状态,于是派一个人去修理,修理过的村庄只能联系距离他们半径为D的村庄,当然他们可以通过一些村庄当中转站,联系。
输入先输入一个N表示有N个村庄,还有一个D表示每个村庄的最大通讯半径,接着有一系列的修复操作和查询操作,如果两个地方不通那么很明显应该输出FALL,否则SUCCESS。
题意已经很明确了,就是修复查询,修复好一个点后与其他修复后的点对比一下看看是否能连接成功。
/////////////////////////////////////////////////////////////////////////
时间用了3S,懒得优化了,优化方法可以搞一个数组转来保存已经修复的额点,这样判断起来少了很多冗余
#include<stdio.h>
const int maxn = 1005;
struct node
{
int x, y, ok;
}p[maxn];//保存所有的村庄,ok表示是否已经修复
int f[maxn];
int Len(node a, node b)//求两个村庄的距离
{
return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
int Find(int x)
{
if(f[x] != x)
f[x] = Find(f[x]);
return f[x];
}
int main()
{
int i, N, D, u, v;
char s[10];
scanf("%d%d", &N, &D);
D = D*D;//因为距离只做判断,所以直接用平方数判断更准确,避免小数
for(i=1; i<=N; i++)
{
scanf("%d%d", &p[i].x, &p[i].y);
p[i].ok = 0;
f[i] = i;
}
while(scanf("%s", s) != EOF)
{
if(s[0] == 'O')
{
scanf("%d", &u);
if(p[u].ok == 0)
{
p[u].ok = 1;
for(i=1; i<=N; i++)
{
if(u != i && p[i].ok && Len(p[i], p[u]) <= D)
{
v = Find(i);
int k = Find(u);
f[k] = v;
}
}
}
}
else
{
scanf("%d%d", &u, &v);
u = Find(u);
v = Find(v);
if(u != v)
printf("FAIL ");
else
printf("SUCCESS ");
}
}
return 0;
const int maxn = 1005;
struct node
{
int x, y, ok;
}p[maxn];//保存所有的村庄,ok表示是否已经修复
int f[maxn];
int Len(node a, node b)//求两个村庄的距离
{
return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
int Find(int x)
{
if(f[x] != x)
f[x] = Find(f[x]);
return f[x];
}
int main()
{
int i, N, D, u, v;
char s[10];
scanf("%d%d", &N, &D);
D = D*D;//因为距离只做判断,所以直接用平方数判断更准确,避免小数
for(i=1; i<=N; i++)
{
scanf("%d%d", &p[i].x, &p[i].y);
p[i].ok = 0;
f[i] = i;
}
while(scanf("%s", s) != EOF)
{
if(s[0] == 'O')
{
scanf("%d", &u);
if(p[u].ok == 0)
{
p[u].ok = 1;
for(i=1; i<=N; i++)
{
if(u != i && p[i].ok && Len(p[i], p[u]) <= D)
{
v = Find(i);
int k = Find(u);
f[k] = v;
}
}
}
}
else
{
scanf("%d%d", &u, &v);
u = Find(u);
v = Find(v);
if(u != v)
printf("FAIL ");
else
printf("SUCCESS ");
}
}
return 0;
}
重构了一下代码,试图弄出来并查集的模版,不过不是太理想
#include<stdio.h> const int maxn = 1e3+7; struct FindSets { int *Father, size; FindSets(int size) : size(size) { Father = new int[size+1]; for(int i=0; i<=size; i++) Father[i] = i; } ~FindSets() { delete[] Father; } int Find(int x) { if(Father[x] != x) Father[x] = Find(Father[x]); return Father[x]; } bool connect(int u, int v, bool need) {///判断两个点是否相连,如果需要相连则连接 u = Find(u); v = Find(v); if(need == true) Father[v] = u; return u == v; } }; struct point { int x, y, fine; }; bool Dis(point &a, point &b, int D) {///判断两点之间的距离是否大于D return ((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)) <= D*D; } void Repair(int u, int D, point p[], FindSets &fs) {///修复点u for(int i=1; i<=fs.size; i++) { if(p[i].fine == true && Dis(p[i], p[u], D)) fs.connect(i, u, true); } p[u].fine = true; } int main() { int N, D; scanf("%d%d", &N, &D); FindSets fs(N); point *p = new point[N+1](); for(int i=1; i<=N; i++) scanf("%d%d", &p[i].x, &p[i].y); int u, v; char op[10]; while(scanf("%s", op) != EOF) { if(op[0] == 'O') { scanf("%d", &u); Repair(u, D, p, fs); } else { scanf("%d%d", &u, &v); if(fs.connect(u, v, false) == true) printf("SUCCESS "); else printf("FAIL "); } } delete[] p; return 0; }