集训队 LPOJ round10 D Come Minion!
**
D Come Minion!**
题意：给定一个地点地图，地点之间的路线，以及沿途的试验，帮助星际忍者达到他们的目标。你必须避免任何忍者无法战胜的考验。然后告诉星际忍者他们是否能够到达目标并拯救世界。
Sample Input:
2
3
stairs
talking
staring
4 5
0 3 talking
0 1 abc
0 2 xyz
1 3 stairs
2 3 staring
3
fire
water
people
4 5
0 1 abc
0 2 water
1 2 fire
1 3 xyz
2 3 abc
Sample Output:
0
1
首先复习一波并查集：
初始化:
for(int i=1;i<=n;i++){
pre[i]=i;
}
查询（含路径压缩）：
int find(int x){
if(pre[x]==x) return x;
else return pre[x]=find(pre[x]);
}
合并：
void merge(int x,int y){
int fx=find(x),fy=find(y);
if(fx!=fy) pre[fx]=fy;
}
题解：
把能通过考验的边都连上即放入同一个集合（能互相到达），最后看0和n-1在不在同一个集合。
代码：
#include
#include
#include
#include
#include
总结：
虽然有自学过并查集，但是在实际运用中却无法想到，第一感觉是个图论题，感觉自己写不出来，就没有再深入思考了，其实用并查集就可以解决，在算法的运用上还很薄弱。
沐兮Krystal
原创文章 2获赞 2访问量 97
关注
私信
展开阅读全文
作者：沐兮Krystal
