BZOJ 3669 魔法森林

Orz 黄学长。还好了，这次学的是用LCT来维护一个最小生成树，应该也不难啊！简单来说，就是当边Ei，j 的加入会使 i 到 j 形成一个环的时候，把这个环上的最长边去掉。而且也只能去掉最长边（我是傻逼，一开始想把所有的比Ei，j大的边去掉的，但仔细一想，其实这样会破坏其他点的连通情况，对吧？所以为了使这个环中的所有点都还是连通的，所以只能把最长边去掉）那如果我们想要加入的这条边本来就是最长边的时候，那我们就不加入咯！还有啊！那个因为这道题有两个指标一个是a ，一个是b，对吧？其实这个思想很简单啦！（其实我以前也曾看过，看到不会，纯属健忘。）就是我们先把 a 排序，使得a 从小往大排列，然后，我们就把一条条地往这里面加边，不难了，如果1 到 n 连通的时候，我们就查询一下， LCT中最大的b是多少就行了？又因为 a 是递增的，所以当前的a值就是最大的a值咯！

加油吧！

另外，这份代码跑了4400毫秒，然而下面那份跑了5000毫秒，然而蒟蒻看不出差距在哪？有大神看出来了，请指教啊！

  1 #include<cstdio>
  2 #include<iostream>
  3 #include<algorithm>
  4 #define inf 0x7fffffff
  5 #define lc c[k][0]
  6 #define rc c[k][1]
  7 #define rep(i,j,k) for(int i = j; i <= k; i++)
  8 #define maxn 152333
  9 using namespace std;
 10  
 11 int read()
 12 {
 13     int s = 0, t = 1; char c = getchar();
 14     while( !isdigit(c) ){
 15         if( c == '-' ) t = -1; c = getchar(); 
 16     }
 17     while( isdigit(c) ){
 18         s = s * 10 + c - '0'; c = getchar();
 19     }
 20     return s * t;
 21 } 
 22  
 23 struct edge{
 24 int u, v, a, b;
 25 bool operator < (const edge&rhs ) const{
 26     return a < rhs.a;
 27 }
 28 } e[100233];
 29  
 30 int q[maxn], mx[maxn], val[maxn], c[maxn][2], pa[maxn];
 31 bool rev[maxn]; 
 32  
 33 bool root(int x)
 34 {
 35     int k = pa[x];
 36     return lc != x && rc != x;
 37 }
 38  
 39 void pushdown(int k)
 40 {
 41     if( rev[k] ){
 42         rev[lc] ^= 1, rev[rc] ^= 1, rev[k] ^= 1;
 43         swap(lc,rc);
 44     }
 45 }
 46  
 47 void maintain(int k)
 48 {
 49     mx[k] = k;
 50     if( val[mx[lc]] > val[mx[k]] ) mx[k] = mx[lc];
 51     if( val[mx[rc]] > val[mx[k]] ) mx[k] = mx[rc];
 52 }
 53  
 54 void rorate(int k)
 55 {
 56     int fa = pa[k], gfa = pa[fa];
 57     int l = c[fa][1] == k, r = l ^ 1;
 58     if( !root(fa) ){
 59         c[gfa][c[gfa][1] == fa] = k;
 60     }   
 61     pa[fa] = k, pa[k] = gfa, c[fa][l] = c[k][r], pa[c[k][r]] = fa;
 62     c[k][r] = fa; maintain(fa), maintain(k);
 63 }
 64  
 65 void splay(int k)
 66 {
 67     int top = 0;
 68     q[++top] = k; for( int x = k; !root(x); x = pa[x] ){
 69         q[++top] = pa[x];
 70     }
 71     while( top ) pushdown(q[top--]);
 72     while( !root(k) ){
 73         int fa = pa[k], gfa = pa[fa];
 74         if( !root(fa) ){
 75             if( c[fa][0] == k ^ c[gfa][0] == fa ) rorate(k);
 76             else rorate(fa);
 77         }
 78         rorate(k);
 79     }
 80 }
 81  
 82 void access(int k)
 83 {
 84     for(int t = 0; k; t = k, k = pa[k])
 85       splay(k), rc = t, maintain(k);
 86 }
 87  
 88 void makeroot(int x)
 89 {
 90     access(x), splay(x), rev[x] ^= 1;
 91 }
 92  
 93 void link(int x,int y)
 94 {
 95     makeroot(x), pa[x] = y;
 96 }
 97  
 98 void split(int x,int y)
 99 {
100     makeroot(x), access(y), splay(y); c[y][0] = pa[x] = 0; maintain(y); //记得重新处理y 
101 }
102  
103 int query(int x,int y)
104 {
105     makeroot(x), access(y), splay(y);
106     return mx[y];
107 }
108  
109 int fa[50233], rank[50233];
110 int find(int x)
111 {
112     return fa[x] == x ? x : fa[x] = find(fa[x]);
113 }
114 bool uni(int x,int y)
115 {
116     int kx = find(x), ky = find(y);
117     if( kx != ky ){
118         if( rank[kx] > rank[ky] ) fa[ky] = kx, rank[x]++;
119         else rank[ky]++, fa[kx] = ky;
120         return 1;
121     }
122     else return 0;
123 }
124  
125 bool tong(int x,int y)
126 {
127     x = find(x), y = find(y);
128     return x == y;
129 }
130  
131 int main()
132 {
133     int n = read(), m = read(); int ans = inf;
134     rep(i,1,n) fa[i] = i;
135     rep(i,1,m){
136         e[i].u = read(), e[i].v = read(), e[i].a = read(), e[i].b = read();
137     }
138     sort(e+1,e+m+1);
139     rep(i,1,m){
140         int s = e[i].u, t = e[i].v;
141         if( !uni(s,t) ){
142             int bian = query(s,t);
143             if( val[bian] > e[i].b ){
144                 split(e[bian-n].u,bian); split(e[bian-n].v,bian);
145             } 
146             else continue;
147         }
148         val[i+n] = e[i].b, mx[i+n] = i+n; link(i+n,s), link(i+n,t);
149         if( tong(1,n) ) ans = min(ans,e[i].a+val[query(1,n)]);
150     }
151     if( ans != inf ) printf("%d
", ans);
152     else printf("%d
", -1);
153     return 0;
154 }

5000毫秒的

  1  
  2 #include<cstdio>
  3 #include<iostream>
  4 #include<algorithm>
  5 #define rep(i,j,k) for(int i = j; i <= k; i++)
  6 #define lc c[k][0]
  7 #define rc c[k][1]
  8 #define maxn 152333
  9 #define inf 0x7fffffff
 10 using namespace std;
 11  
 12 struct edge{
 13 int u, v, a, b;
 14 bool operator < (const edge&rhs ) const
 15 {
 16     return a < rhs.a;
 17 }
 18 } e[100233];
 19  
 20 int read()
 21 {
 22     int s =0, t = 1; char c = getchar();
 23     while( !isdigit(c) ){
 24         if( c == '-' ) t = -1; c = getchar(); 
 25     }
 26     while( isdigit(c) ){
 27         s = s * 10 + c - '0'; c = getchar();
 28     }
 29     return s * t;
 30 }
 31  
 32 int c[maxn][2], pa[maxn], mx[maxn], val[maxn];
 33 bool rev[maxn];
 34  
 35 bool root(int x)
 36 {
 37     int k = pa[x];
 38     return lc != x && rc != x; 
 39 }
 40  
 41 void pushdown(int k)
 42 {
 43     if( rev[k] ){
 44         rev[k] ^= 1, rev[lc] ^= 1, rev[rc] ^= 1;
 45         swap(lc,rc);
 46     }
 47 }
 48  
 49 void maintain(int k)
 50 {
 51     mx[k] = k;
 52     if( val[mx[lc]] > val[mx[k]] ) mx[k] = mx[lc];
 53     if( val[mx[rc]] > val[mx[k]] ) mx[k] = mx[rc];
 54 }
 55  
 56 void rorate(int k)
 57 {
 58     int fa = pa[k], gfa = pa[fa];
 59     int l = c[fa][1] == k, r = l ^ 1;
 60     if( !root(fa) ){
 61         c[gfa][c[gfa][1] == fa] = k;
 62     }
 63     c[fa][l] = c[k][r], pa[c[k][r]] = fa, c[k][r] = fa;
 64     pa[k] = gfa, pa[fa] = k; maintain(fa), maintain(k);
 65 }
 66 int q[maxn];
 67 void splay(int k)
 68 {
 69     int top = 0;
 70     q[++top] = k;
 71     for(int x = k; !root(x); x = pa[x])
 72         q[++top] = pa[x];
 73     while( top ) pushdown(q[top--]);
 74     while( !root(k) ){
 75         int fa = pa[k], gfa = pa[fa];
 76         if( !root(fa) ){
 77             if( c[gfa][1] == fa ^ c[fa][1] == k ) rorate(k);
 78             else rorate(fa);
 79         }
 80         rorate(k);
 81     }
 82 }
 83  
 84 void access(int k)
 85 {
 86     for(int t = 0; k; t = k, k = pa[k])
 87        splay(k), rc = t, maintain(k);
 88 }
 89  
 90 void makeroot(int k)
 91 {
 92     access(k), splay(k); rev[k] ^= 1;
 93 }
 94  
 95 void link(int x,int y)
 96 {
 97     makeroot(x), pa[x]= y; 
 98 }
 99  
100 void split(int x,int y)
101 {
102     makeroot(x); access(y), splay(y);
103     pa[x] = c[y][0] = 0; maintain(y);
104 }
105  
106 int query(int x,int y)
107 {
108     makeroot(x); access(y), splay(y);
109     return mx[y];
110 }
111  
112 int fa[50233], rank[50233];
113 int find(int x)
114 {
115     return x == fa[x] ? x : fa[x] = find(fa[x]);
116 }
117  
118 bool uni(int x,int y)
119 {
120     x = find(x), y = find(y);
121     if( x != y ){
122         if( rank[x] > rank[y] ) rank[x]++, fa[y] = x;
123         else rank[y]++, fa[x] = y; 
124         return 1;
125     }
126     else return 0;
127 }
128  
129 bool tong(int x,int y)
130 {
131     x = find(x), y = find(y);
132     if( x != y ) return 0; else return 1;
133 }
134  
135 int main()
136 {
137     int n = read(), m = read(), ans = inf;
138     rep(i,1,n) fa[i] = i;
139     rep(i,1,m) e[i].u = read(), e[i].v = read(), e[i].a = read(), e[i].b = read();
140     sort(e+1,e+m+1);
141     rep(i,1,m){
142         int u = e[i].u, v = e[i].v;
143         if( !uni(u,v) ){
144             int t = query(u,v);
145             if( val[t] > e[i].b ){
146                 split(e[t-n].u,t); split(e[t-n].v,t);
147             }
148             else continue;
149         }
150         val[i+n] = e[i].b, mx[i+n] = i + n; 
151         link(u,i+n); link(v,i+n); 
152         if( tong(1,n) ) ans = min(ans,e[i].a+val[query(1,n)]);
153     }
154     if( ans == inf ) cout<<-1<<endl;
155     else cout<<ans<<endl;
156     return 0;
157 }