bzoj 3669 lct维护最小生成树

大概题意：给一个无向图，有a,b两种边权，找一条从1到n的路径，使得max(a[i])+max(b[i])最小a[i],b[i]表示该路径上的边的对应权。

如果用类似最短路的DP来做，显然每个点的状态就必须是一个集合，保存的是一个下凸的点集，表示到达这个点的最小的a,b，这样肯定会挂，但该该种做法已经无法再优化或减少状态了。

考虑枚举其中一个权值b0,然后只考虑所有b权值小于等于b0的边，然后变成简单的问题，因为这个b0不满足二分三分之类的性质，所以肯定不能每次重建图，跑DP，最终的做法是从小到大枚举一维权值，然后不断地加边进入边，维护一个当前图的最小生成树（用LCT实现）。

收获：

　　1、如果一个东西不满足二分三分，可以尝试从动态的角度，暴力枚举，用数据结构保证复杂度。

 /**************************************************************

     Problem: 3669

     User: idy002

     Language: C++

     Result: Accepted

     Time:6680 ms

     Memory:12536 kb

 ****************************************************************/

 #include <cstdio>

 #include <algorithm>

 #define oo 0x3f3f3f3f

 #define N 200010

 using namespace std;

 struct Edge {

     int u, v, a, b;

     Edge(){}

     Edge( int u, int v, int a, int b ):u(u),v(v),a(a),b(b){}

     bool operator<( const Edge &e ) const { return b<e.b; }

 };

 struct LCT {

     int son[N][], pre[N], pnt[N], rtg[N], ntot;

     int trash[N], stot;

     int val[N], vmx[N], vnd[N], uu[N], vv[N];

     inline int newnode( int p, int va, int u, int v ) {

         int nd = stot ? trash[stot--] : ++ntot;

         pre[nd] = p;

         son[nd][] = son[nd][] = pnt[nd] = ;

         rtg[nd] = ;

         val[nd] = vmx[nd] = va;

         vnd[nd] = nd;

         uu[nd] = u;

         vv[nd] = v;

         return nd;

     }

     void update( int nd ) {

         vmx[nd] = val[nd];

         vmx[nd] = max( vmx[nd], vmx[son[nd][]] );

         vmx[nd] = max( vmx[nd], vmx[son[nd][]] );

         if( vmx[nd]==val[nd] )

             vnd[nd] = nd;

         else if( vmx[nd]==vmx[son[nd][]] )

             vnd[nd] = vnd[son[nd][]];

         else

             vnd[nd] = vnd[son[nd][]];

     }

     void rotate( int nd, int d ) {

         int p = pre[nd];

         int s = son[nd][!d];

         int ss = son[s][d];

         son[nd][!d] = ss;

         son[s][d] = nd;

         if( p ) son[p][ nd==son[p][] ] = s;

         else pnt[s]=pnt[nd], pnt[nd]=;

         pre[nd] = s;

         pre[s] = p;

         if( ss ) pre[ss] = nd;

         update(nd);

         update(s);

     }

     void bigp( int nd ) {

         if( pre[nd] ) bigp(pre[nd]);

         if( rtg[nd] ) {

             rtg[son[nd][]] ^= ;

             rtg[son[nd][]] ^= ;

             swap( son[nd][], son[nd][] );

             rtg[nd] = ;

         }

     }

     void splay( int nd, int top= ) {

         bigp(nd);

         while( pre[nd]!=top ) {

             int p=pre[nd];

             int nl=nd==son[p][];

             if( pre[p]==top ) {

                 rotate( p, nl );

             } else {

                 int pp=pre[p];

                 int pl=p==son[pp][];

                 if( nl==pl ) {

                     rotate( pp, pl );

                     rotate( p, nl );

                 } else {

                     rotate( p, nl );

                     rotate( pp, pl );

                 }

             }

         }

     }

     void access( int nd ) {

         int u = nd;

         int v = ;

         while( u ) {

             splay( u );

             int s=son[u][];

             if( s ) {

                 pre[s] = ;

                 pnt[s] = u;

             }

             son[u][] = ;

             if( v ) {

                 pre[v] = u;

                 pnt[v] = ;

             }

             son[u][] = v;

             update(u);

             v = u;

             u = pnt[u];

         }

         splay( nd );

     }

     void makeroot( int u ) {

         access(u);

         rtg[u] ^= ;

     }

     void init( int n ) {

         ntot = n;

         val[] = -;

     }

     int findroot( int u ) {

         while( pre[u] ) u=pre[u];

         while( pnt[u] ) {

             u=pnt[u];

             while( pre[u] ) u=pre[u];

         }

         return u;

     }

     bool sameroot( int u, int v ) {

         return findroot(u)==findroot(v);

     }

     int query( int s, int t ) {

         makeroot(s);

         access(t);

         return vmx[t];

     }

     void addedge( int u, int v, int w ) {

 //      fprintf( stderr, "addedge( %d %d %d )\n", u, v, w );

         if( sameroot(u,v) ) {

             if( query(u,v)<=w ) return;

             makeroot(u);

             access(v);

             int nd = vnd[v];

             int l = uu[nd];

             int r = vv[nd];

             makeroot(l);

             access(r);

             bigp(l);

             int e = son[r][];

             while( son[e][] ) e=son[e][];

             splay(e);

             pre[l] = pre[r] = ;

             trash[++stot] = e;

         }

         makeroot(u);

         makeroot(v);

         int nd = newnode(,w,u,v);

         pnt[u] = nd;

         pnt[v] = nd;

     }

     void print() {

         fprintf( stderr, "\n" );

         for( int i=; i<=ntot; i++ ) {

             int nd = i;

             for( int j=; j<=stot; j++ )

                 if( i==trash[j] )

                     goto Next;

             fprintf( stderr, "%d pnt=%d pre=%d ls=%d rs=%d rtg=%d val=%d vmx=%d vnd=%d uu=%d vv=%d\n",

                     nd, pnt[nd], pre[nd], son[nd][], son[nd][], rtg[nd], val[nd], vmx[nd], vnd[nd], uu[nd], vv[nd] );

 Next:;

         }

     }

 }T;

 int n, m;

 Edge edge[N];

 int main() {

     scanf( "%d%d", &n, &m );

     for( int i=,u,v,a,b; i<=m; i++ ) {

         scanf( "%d%d%d%d", &u, &v, &a, &b );

         edge[i] = Edge(u,v,a,b);

     }

     sort( edge+, edge++m );

     T.init(n);

     int ans = oo;

     for( int i=,j; i<=m; i=j ) {

         for( j=i; j<=m; j++ ) {

             if( edge[j].b==edge[i].b )

                 T.addedge(edge[j].u,edge[j].v,edge[j].a);

             else break;

         }

         if( !T.sameroot(,n) ) continue;

         ans = min( ans, edge[i].b+T.query(,n) );

     }

     printf( "%d\n", ans==oo ? - : ans );

 }

巴特西

bzoj 3669 lct维护最小生成树

最新文章

热门文章