A - Wireless Network-poj2236（简单并查集）
生活随笔
收集整理的這篇文章主要介紹了
A - Wireless Network-poj2236（简单并查集）
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
說是有N個村莊，剛開始每個村莊的網(wǎng)絡都是受損狀態(tài)，于是派一個人去修理，修理過的村莊只能聯(lián)系距離他們半徑為D的村莊，當然他們可以通過一些村莊當中轉(zhuǎn)站，聯(lián)系。
輸入先輸入一個N表示有N個村莊，還有一個D表示每個村莊的最大通訊半徑，接著有一系列的修復操作和查詢操作，如果兩個地方不通那么很明顯應該輸出FALL，否則SUCCESS。
題意已經(jīng)很明確了，就是修復查詢，修復好一個點后與其他修復后的點對比一下看看是否能連接成功。
/////////////////////////////////////////////////////////////////////////
時間用了3S，懶得優(yōu)化了，優(yōu)化方法可以搞一個數(shù)組轉(zhuǎn)來保存已經(jīng)修復的額點，這樣判斷起來少了很多冗余
#include<stdio.h> const int maxn = ; struct node
{
int x, y, ok;
}p[maxn];//保存所有的村莊，ok表示是否已經(jīng)修復 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[]; scanf("%d%d", &N, &D); D = D*D;//因為距離只做判斷，所以直接用平方數(shù)判斷更準確，避免小數(shù) for(i=; i<=N; i++)
{
scanf("%d%d", &p[i].x, &p[i].y);
p[i].ok = ;
f[i] = i;
} while(scanf("%s", s) != EOF)
{
if(s[] == 'O')
{
scanf("%d", &u); if(p[u].ok == )
{
p[u].ok = ;
for(i=; 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\n");
else
printf("SUCCESS\n");
}
} return ;
}
重構(gòu)了一下代碼，試圖弄出來并查集的模版，不過不是太理想
#include<stdio.h> const int maxn = 1e3+; struct FindSets
{
int *Father, size; FindSets(int size)
: size(size)
{
Father = new int[size+];
for(int i=; 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=; 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+](); for(int i=; i<=N; i++)
scanf("%d%d", &p[i].x, &p[i].y); int u, v;
char op[]; while(scanf("%s", op) != EOF)
{
if(op[] == 'O')
{
scanf("%d", &u);
Repair(u, D, p, fs);
}
else
{
scanf("%d%d", &u, &v);
if(fs.connect(u, v, false) == true)
printf("SUCCESS\n");
else
printf("FAIL\n");
}
} delete[] p; return ;
}
總結(jié)
以上是生活随笔為你收集整理的A - Wireless Network-poj2236（简单并查集）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： VS中的配置管理器
- 下一篇： 初识RabbitMQ