首页 > 代码库 > BZOJ3669 (动态树)
BZOJ3669 (动态树)
Problem 魔法森林 (NOI2014)
题目大意
给n个点,m条边的无向图,每条边有两个权值a,b。
求一条从1-->n的路径,使得这条路径上max(a)+max(b)最小。输出最小值即可。
解题分析
将边按照权值a从小到大排序后,依次加边,用lct维护一棵最小生成树。
具体做法是如果所加边u-->v导致形成了一个环,那么比较一下u-->v路径中的最大值和这条边的b权值大小,来决定取那条边。
处理边权的一个做法,将每条边看成一个新的点,向其两端的点连边。
参考程序
1 #include <map> 2 #include <set> 3 #include <stack> 4 #include <queue> 5 #include <cmath> 6 #include <ctime> 7 #include <string> 8 #include <vector> 9 #include <cstdio> 10 #include <cstdlib> 11 #include <cstring> 12 #include <cassert> 13 #include <iostream> 14 #include <algorithm> 15 #pragma comment(linker,"/STACK:102400000,102400000") 16 using namespace std; 17 18 #define N 200008 19 #define E 400008 20 #define LL long long 21 #define lson l,m,rt<<1 22 #define rson m+1,r,rt<<1|1 23 #define clr(x,v) memset(x,v,sizeof(x)); 24 #define bitcnt(x) __builtin_popcount(x) 25 #define rep(x,y,z) for (int x=y;x<=z;x++) 26 #define repd(x,y,z) for (int x=y;x>=z;x--) 27 const int mo = 1000000007; 28 const int inf = 0x3f3f3f3f; 29 const int INF = 2000000000; 30 /**************************************************************************/ 31 int n,m; 32 int fa[N],val[N],mx[N],rev[N],c[N][2],st[N]; 33 34 struct line{ 35 int u,v,a,b; 36 bool operator < (const line &k) const{ 37 return a<k.a; 38 } 39 }eg[E]; 40 bool isroot(int k){ 41 return c[fa[k]][0]!=k && c[fa[k]][1]!=k; 42 } 43 void pushup(int x){ 44 int l=c[x][0],r=c[x][1]; 45 mx[x]=x; 46 if (val[mx[l]]>val[mx[x]]) mx[x]=mx[l]; 47 if (val[mx[r]]>val[mx[x]]) mx[x]=mx[r]; 48 } 49 void pushdown(int x){ 50 int l=c[x][0],r=c[x][1]; 51 if (rev[x]){ 52 if (l) rev[l]^=1; 53 if (r) rev[r]^=1; 54 rev[x]^=1; 55 swap(c[x][0],c[x][1]); 56 } 57 } 58 void rotate(int x){ 59 int y=fa[x],z=fa[y],l,r; 60 if (c[y][0]==x) l=0; else l=1; r=l^1; 61 if (!isroot(y)){ 62 if (c[z][0]==y) c[z][0]=x; else c[z][1]=x; 63 } 64 fa[x]=z; fa[y]=x; fa[c[x][r]]=y; 65 c[y][l]=c[x][r]; c[x][r]=y; 66 pushup(y); pushup(x); 67 } 68 void splay(int x){ 69 int top=0; st[++top]=x; 70 for (int i=x;!isroot(i);i=fa[i]) st[++top]=fa[i]; 71 while (top) pushdown(st[top--]); 72 while (!isroot(x)){ 73 int y=fa[x],z=fa[y]; 74 if (!isroot(y)){ 75 if (c[y][0]==x^c[z][0]==y) rotate(x); 76 else rotate(y); 77 } 78 rotate(x); 79 } 80 } 81 void access(int x){ 82 int t=0; 83 while (x){ 84 splay(x); 85 c[x][1]=t; 86 pushup(x); 87 t=x; x=fa[x]; 88 } 89 } 90 void rever(int x){ 91 access(x); splay(x); rev[x]^=1; 92 } 93 void link(int u,int v){ 94 rever(u); fa[u]=v; 95 } 96 void cut(int u,int v){ 97 rever(u); access(v); splay(v); fa[c[v][0]]=0; c[v][0]=0; pushup(v); 98 } 99 int find(int u){100 access(u); splay(u);101 while (c[u][0]) u=c[u][0];102 return u;103 }104 int query(int u,int v){105 rever(u); access(v); splay(v); return mx[v];106 }107 108 int main(){109 scanf("%d%d",&n,&m);110 rep(i,1,m) scanf("%d%d%d%d",&eg[i].u,&eg[i].v,&eg[i].a,&eg[i].b);111 sort(eg+1,eg+m+1);112 int ans=INF;113 rep(i,1,m){114 int u=eg[i].u,v=eg[i].v,a=eg[i].a,b=eg[i].b;115 int flag=1;116 if (find(u)==find(v)){117 int t=query(u,v);118 if (b<val[t]){119 cut(t,eg[t-n].u);120 cut(t,eg[t-n].v);121 }122 else flag=0;123 }124 if (flag) {125 val[i+n]=b; mx[n+i]=n+i;126 link(i+n,u); 127 link(i+n,v);128 }129 if (find(1)==find(n)){130 int t=query(1,n);131 ans=min(ans,val[t]+a);132 }133 }134 printf("%d\n",ans==INF?-1:ans);135 }
BZOJ3669 (动态树)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。