首页 > 代码库 > HDU 1512 并查集+左偏树

HDU 1512 并查集+左偏树

2024-07-12 09:04:05   228人阅读

Monkey King

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 3105    Accepted Submission(s): 1330


Problem Description
Once in a forest, there lived N aggressive monkeys. At the beginning, they each does things in its own way and none of them knows each other. But monkeys can‘t avoid quarrelling, and it only happens between two monkeys who does not know each other. And when it happens, both the two monkeys will invite the strongest friend of them, and duel. Of course, after the duel, the two monkeys and all of there friends knows each other, and the quarrel above will no longer happens between these monkeys even if they have ever conflicted.

Assume that every money has a strongness value, which will be reduced to only half of the original after a duel(that is, 10 will be reduced to 5 and 5 will be reduced to 2).

And we also assume that every monkey knows himself. That is, when he is the strongest one in all of his friends, he himself will go to duel.
 

 

Input
There are several test cases, and each case consists of two parts.

First part: The first line contains an integer N(N<=100,000), which indicates the number of monkeys. And then N lines follows. There is one number on each line, indicating the strongness value of ith monkey(<=32768).

Second part: The first line contains an integer M(M<=100,000), which indicates there are M conflicts happened. And then M lines follows, each line of which contains two integers x and y, indicating that there is a conflict between the Xth monkey and Yth.

 

 

Output
For each of the conflict, output -1 if the two monkeys know each other, otherwise output the strongness value of the strongest monkey in all friends of them after the duel.
 

 

Sample Input
5
20
16
10
10
4
5
2 3
3 4
3 5
4 5
1 5
 
 
Sample Output
8
5
5
-1
10
 
 
 
题目意思：
森林有n只猴子，每只猴子有个强度值，一开始谁也不认识谁，他们之间会有争斗，争斗的两个猴子请自己朋友中最强的猴子代替自己打架（如果没朋友只能自己打。。苦逼。。），打架的两只猴子的强度值都减半取整，然后打架的两方都成为朋友了。  如果输入的两只猴子已经是朋友，那么输出-1，否则输出打架后两群猴子中最大的强度值。
 
看到朋友，就想起了并查集，每次打斗都选出最高强度值进行减半，这不就是堆么。然后两群猴子合并成一群猴子，答案就很显然了：并查集+左偏树。
 
 
代码：
 
 
 1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <iostream> 5 #define N 100005 6 using namespace std; 7  8  9 struct node{10     int l, r;11     int dis;12     int val;13     int f;14 }tree[N];15 16 int findroot(int p);17 int merge(int x,int y);18 int del(int x);19 void solve(int x,int y);20 21 22 main()23 {24     int n, m, i, j, k;25     while(scanf("%d",&n)==1){26         for(i=1;i<=n;i++){27             scanf("%d",&tree[i].val);28             tree[i].l=tree[i].r=tree[i].dis=0;29             tree[i].f=i;30         }31         int x, y;32         scanf("%d",&m);33         while(m--){34             scanf("%d %d",&x,&y);35             int fx=findroot(x);36             int fy=findroot(y);37             if(fx==fy){38                 printf("-1\n");39                 continue;40             }41             solve(fx,fy);42         }43     }44 }45 46 int findroot(int p){47     int r=p;48     while(r!=tree[r].f){49         r=tree[r].f;50     }51     return r;52 }53 54 int merge(int x,int y){55     if(x==0) return y;56     if(y==0) return x;57     if(tree[x].val<tree[y].val) swap(x,y);58     tree[x].r=merge(tree[x].r,y);59     tree[tree[x].r].f=x;60     if(tree[tree[x].r].dis>tree[tree[x].l].dis) swap(tree[x].l,tree[x].r);61     if(!tree[x].r) tree[x].dis=0;62     else tree[x].dis=tree[tree[x].r].dis+1;63     return x;64 }65 66 int del(int x){67     int left=tree[x].l;68     int right=tree[x].r;69     tree[left].f=left;70     tree[right].f=right;71     tree[x].l=tree[x].r=tree[x].dis=0;72     return merge(left,right);73 }74 75 void solve(int x,int y){76     tree[x].val/=2;77     tree[y].val/=2;78     int left=del(x);79     int right=del(y);80     left=merge(left,x);81     right=merge(right,y);82     int num=merge(left,right);83     printf("%d\n",tree[num].val);84 }

 


联系
我们