HDU 1856 More is better

。。。

30次提交2次AC

这道题告诉我一个道理：交题要在评测机高兴的时候交（大雾）

其实是好好看题啦

话说输入0输出1 2333333333333333333333333333

邪道：直接map+并查集

路径压缩时把val[]所表示的高度改为子孙数即可

映射是好用但1e6*10组数据*并查集的O(1~n)*操作常数e+O(ne)就危险的紧，不推荐使用

 1 #include<iostream>
 2 #include<map>
 3 using namespace std;
 4 #define FOR(i,j,k) for(int i=j;i<=k;i++)
 5 #define FORD(i,j,k) for(int i=j;i>=k;i--)
 6 #define LL long long
 7 #define maxn 100010
 8 int father[maxn],val[maxn],maxfriend[maxn];
 9 int n,x,y,k,maxv,XX,YY;
10 bool flag;
11 map<int,int> ID;
12 int setfind(int xx)
13 {
14     int fa=father[xx];
15     if(fa==xx) return fa;
16     else return father[xx]=setfind(fa);
17 }
18 void setunion(int xx,int yy)
19 {
20     int X=setfind(xx);
21     int Y=setfind(yy);
22     if(X==Y) return;
23     if(maxfriend[X]>maxfriend[Y]) 
24     {
25     father[Y]=X;
26     maxfriend[X]+=maxfriend[Y];
27     if(maxfriend[X]>maxv) maxv=maxfriend[X];
28     }
29     else 
30     {
31     father[X]=Y;
32     maxfriend[Y]+=maxfriend[X];
33     if(maxfriend[Y]>maxv) maxv=maxfriend[Y];
34     }
35     return;
36 }
37 int main()
38 {
39 while(cin>>n)
40 {
41     maxv=1;
42     k=0;
43     flag=true;
44     FOR(i,1,n)
45     {
46         cin>>x>>y;
47         if(!ID.count(x)) {k++; ID[x]=k; father[k]=k; XX=k;/*val[k]=1;*/maxfriend[k]=1;}else XX=ID[x];
48         if(!ID.count(y)) {k++; ID[y]=k; father[k]=k; YY=k;/*val[k]=1;*/maxfriend[k]=1;}else YY=ID[y];
49         setunion(XX,YY);
50     }
51     cout<<maxv<<endl;
52     ID.clear();
53 }
54 return 0;
55 }

血统测试代码

飞鞋道：Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 327680/102400 K (Java/Others)

所以直接开1e7+10的数组，抛弃map

其他部分一样

就不放这样的代码了，其他博客有