Description
为了得到书法大家的真传，小E同学下定决心去拜访住在魔法森林中的隐士。魔法森林可以被看成一个包含个N节点M条边的无向图，节点标号为1..N，边标号为1..M。初始时小E同学在号节点1，隐士则住在号节点N。小E需要通过这一片魔法森林，才能够拜访到隐士。
魔法森林中居住了一些妖怪。每当有人经过一条边的时候，这条边上的妖怪就会对其发起攻击。幸运的是，在号节点住着两种守护精灵：A型守护精灵与B型守护精灵。小E可以借助它们的力量，达到自己的目的。
只要小E带上足够多的守护精灵，妖怪们就不会发起攻击了。具体来说，无向图中的每一条边Ei包含两个权值Ai与Bi。若身上携带的A型守护精灵个数不少于Ai，且B型守护精灵个数不少于Bi，这条边上的妖怪就不会对通过这条边的人发起攻击。当且仅当通过这片魔法森林的过程中没有任意一条边的妖怪向小E发起攻击，他才能成功找到隐士。
由于携带守护精灵是一件非常麻烦的事，小E想要知道，要能够成功拜访到隐士，最少需要携带守护精灵的总个数。守护精灵的总个数为A型守护精灵的个数与B型守护精灵的个数之和。
Input
第1行包含两个整数N,M，表示无向图共有N个节点，M条边。 接下来M行，第行包含4个正整数Xi,Yi,Ai,Bi，描述第i条无向边。其中Xi与Yi为该边两个端点的标号，Ai与Bi的含义如题所述。 注意数据中可能包含重边与自环。
Output
输出一行一个整数：如果小E可以成功拜访到隐士，输出小E最少需要携带的守护精灵的总个数；如果无论如何小E都无法拜访到隐士，输出“-1”（不含引号）。
Sample Input
4 5
1 2 19 1
2 3 8 12
2 4 12 15
1 3 17 8
3 4 1 17【输入样例2】3 1
1 2 1 1
Sample Output
【输出样例1】
32
【样例说明1】
如果小E走路径1→2→4，需要携带19+15=34个守护精灵；
如果小E走路径1→3→4，需要携带17+17=34个守护精灵；
如果小E走路径1→2→3→4，需要携带19+17=36个守护精灵；
如果小E走路径1→3→2→4，需要携带17+15=32个守护精灵。
综上所述，小E最少需要携带32个守护精灵。
【输出样例2】
-1
【样例说明2】
小E无法从1号节点到达3号节点，故输出-1。
HINT
2<=n<=50,000
0<=m<=100,000
1<=ai ,bi<=50,000
Solution
将边按Ai排序，然后LCT维护以Bi为值的最小生成树即可。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 |
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> using namespace std; const int N=150010,M=100100; int n,m,Tree[N],Max[N],rev[N],fa[N],son[N][2],Stack[N]; struct node{int u,v,a,b;}Edge[M]; bool cmp(node a,node b) { return a.a<b.a;} bool isRoot(int x) { return (son[fa[x]][0]!=x)&&(son[fa[x]][1]!=x);} void update(int x) { Max[x]=x; if (Tree[Max[son[x][0]]]>Tree[Max[x]]) Max[x]=Max[son[x][0]]; if (Tree[Max[son[x][1]]]>Tree[Max[x]]) Max[x]=Max[son[x][1]]; } void pushdown(int x) { if (rev[x]) { if (son[x][0]) rev[son[x][0]]^=1; if (son[x][1]) rev[son[x][1]]^=1; swap(son[x][0],son[x][1]); rev[x]=0; } } void Rotate(int x) { int y=fa[x],z=fa[y],l,r; if (son[y][0]==x) l=0;else l=1; r=l^1; if (!isRoot(y)) { if (son[z][0]==y) son[z][0]=x;else son[z][1]=x; } fa[x]=z;fa[y]=x;fa[son[x][r]]=y; son[y][l]=son[x][r];son[x][r]=y; update(y);update(x); } void splay(int x) { int top=0;Stack[++top]=x; for (int i=x;!isRoot(i);i=fa[i]) Stack[++top]=fa[i]; for (;top;top--) pushdown(Stack[top]); while (!isRoot(x)) { int y=fa[x],z=fa[y]; if (!isRoot(y)) { if ((son[y][0]==x)^(son[z][0]==y)) Rotate(x); else Rotate(y); } Rotate(x); } } void access(int x) { for (int i=0;x;i=x,x=fa[x]) { splay(x); son[x][1]=i; update(x); } } void MakeRoot(int x) { access(x); splay(x); rev[x]^=1; } int compuse(int x,int y) { MakeRoot(x); access(y); splay(y); return y; } int GetRoot(int x) { access(x); splay(x); while (son[x][0]) x=son[x][0]; return x; } void link(int x,int y) { MakeRoot(x); fa[x]=y; } void cut(int x,int y) { MakeRoot(x); access(y); splay(y); son[y][0]=fa[x]=0; update(y); } int main() { scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) Max[i]=i,Tree[i]=0; for (int i=1;i<=m;i++) scanf("%d%d%d%d",&Edge[i].u,&Edge[i].v,&Edge[i].a,&Edge[i].b); sort(Edge+1,Edge+m+1,cmp); int ans=1<<29; for (int i=1;i<=m;i++) { int u=Edge[i].u,v=Edge[i].v; Tree[n+i]=Edge[i].b;Max[n+i]=n+i; if (GetRoot(u)==GetRoot(v)) { int id=compuse(u,v); if (Tree[Max[id]]>Tree[n+i]) { int j=Max[id]-n; cut(Edge[j].u,j+n);cut(j+n,Edge[j].v); link(u,n+i);link(v,n+i); } }else link(u,n+i),link(v,n+i); if (GetRoot(1)==GetRoot(n)) { int id=compuse(1,n); ans=min(ans,Edge[i].a+Tree[Max[id]]); } } if (ans==1<<29) puts("-1"); else printf("%d\n",ans); return 0; } |
Orz