首页 > 代码库 > csu1010: Water Drinking
csu1010: Water Drinking
/*
本题的题意:
沙漠中有很多骆驼和一个池塘,0表示池塘,1-N表示骆驼,
输入的两个数表示两只骆驼,其中前面的那一头靠近池塘,
所有的骆驼队列不交叉不相连,求站在队尾但是离水井最近的骆驼编号
经过分析最后还是要先构造一个树,然后寻找离0最近的一个点,当结果是相等的级别的时候将结果返回最小的那个值
*/
参考代码:
1 #include<stdio.h> 2 #include<string.h> 3 #define maxn 100010 4 5 int pre[maxn], dis[maxn]; 6 //pre 数组代表当前骆驼的前一个骆驼, dis 数组代表当前骆驼到水井的距离 7 int main() 8 { 9 int n;10 while(scanf("%d", &n) != EOF){11 int x, y, i, ans, mind;12 memset(dis, 0, sizeof(dis));13 //父节点初始化 并查集必备14 for(i = 0; i < n; i++)15 pre[i] = i;16 for(i = 0; i < n; i++){17 scanf("%d %d", &x, &y);18 pre[y] = x;19 dis[x] = 1;20 }21 for(mind = n + 1, ans = i = 0; i <= n; i++){//注意:mind的初始值要大于n22 //如果dis[i]为0 即该节点无子节点23 if(!dis[i]){24 x = i; //x 是一个临时变量25 //如果这个节点有父节点 递归求出距离26 while(pre[x] != x){27 x = pre[x];28 dis[i]++;29 }30 //找出最大距离所在的骆驼31 if(!x && dis[i] < mind){32 mind = dis[i];33 ans = i;34 }35 }36 }37 printf("%d\n", ans);38 }39 return 0;40 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。