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
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
第一个lct第二个spfa
lct：
这个基本算是lct裸题
但也学到了一点套路
如果要维护边权的话就将边看做一个点然后连接相应的两个点
至于这个点的编号？和输入的编号对应起来就好了，方便我们查找这个点对应的边的信息
这个题只需要每次将a相同的边的b权值加入树中，当前的答案就是a[i]+min(1~n路径上的最大值)
若连边连出环了怎么办？先将点x和y中最长的边cut掉再加入就好了
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<algorithm> 5 #define N (500000+100) 6 using namespace std; 7 struct node 8 { 9 int a,b,x,y; 10 }line[N*2]; 11 int Father[N],Son[N][2]; 12 int Max[N],Val[N],Rev[N]; 13 int n,m,sz; 14 bool cmp(node a,node b){return a.a<b.a;} 15 16 int Get(int x) {return Son[Father[x]][1]==x;} 17 int Is_root(int x) {return Son[Father[x]][1]!=x && Son[Father[x]][0]!=x;} 18 void Update(int x) 19 { 20 if (Val[x]>Val[Max[Son[x][0]]] && Val[x]>Val[Max[Son[x][1]]]) 21 Max[x]=x; 22 else 23 Max[x]=Val[Max[Son[x][0]]]>Val[Max[Son[x][1]]]?Max[Son[x][0]]:Max[Son[x][1]]; 24 } 25 26 void Rotate(int x) 27 { 28 int wh=Get(x); 29 int fa=Father[x],fafa=Father[fa]; 30 if (!Is_root(fa)) Son[fafa][Son[fafa][1]==fa]=x; 31 Father[fa]=x; Son[fa][wh]=Son[x][wh^1]; 32 Father[x]=fafa; Son[x][wh^1]=fa; 33 if (Son[fa][wh]) Father[Son[fa][wh]]=fa; 34 Update(fa);Update(x); 35 } 36 37 void Pushdown(int x) 38 { 39 if (Rev[x] && x) 40 { 41 if (Son[x][0]) Rev[Son[x][0]]^=1; 42 if (Son[x][1]) Rev[Son[x][1]]^=1; 43 swap(Son[x][0],Son[x][1]); 44 Rev[x]=0; 45 } 46 } 47 48 void Push(int x) 49 { 50 if (!Is_root(x)) Push(Father[x]); 51 Pushdown(x); 52 } 53 54 void Splay(int x) 55 { 56 Push(x); 57 for (int fa;!Is_root(x);Rotate(x)) 58 if (!Is_root(fa=Father[x])) 59 Rotate(Get(fa)==Get(x)?fa:x); 60 } 61 62 void Access(int x) {for (int y=0;x;y=x,x=Father[x]) Splay(x),Son[x][1]=y,Update(x);} 63 int Find_root(int x) {Access(x); Splay(x); while (Son[x][0]) x=Son[x][0]; return x;} 64 void Make_root(int x) {Access(x); Splay(x); Rev[x]^=1;} 65 void Link(int x,int y) {Make_root(x); Father[x]=y;} 66 void Cut(int x,int y) {Make_root(x); Access(y); Splay(y); Son[y][0]=Father[x]=0;} 67 68 void Add_line(int num,int x,int y,int l) 69 { 70 if (Find_root(x)!=Find_root(y)) 71 { 72 Link(x,num);Link(num,y); 73 Val[num]=l; 74 return; 75 } 76 Make_root(x); 77 Access(y); Splay(y); 78 if (Val[Max[y]]<l) return; 79 int t=Max[y]-n; 80 Cut(line[t].x,t+n);Cut(line[t].y,t+n); 81 Link(x,num);Link(num,y); 82 Val[num]=l; 83 } 84 85 int main() 86 { 87 int ans=0x7fffffff; 88 scanf("%d%d",&n,&m); 89 for (int i=1;i<=m;++i) 90 scanf("%d%d%d%d",&line[i].x,&line[i].y,&line[i].a,&line[i].b); 91 sort(line+1,line+m+1,cmp); 92 int s=1; 93 while (s<=m) 94 { 95 while (line[s].a==line[s+1].a) 96 Add_line(s+n,line[s].x,line[s].y,line[s].b),s++; 97 Add_line(s+n,line[s].x,line[s].y,line[s].b); 98 s++; 99 if (Find_root(1) !=Find_root(n)) continue; 100 Make_root(n); 101 Access(1); Splay(1); 102 ans=min(ans,line[s-1].a+Val[Max[1]]); 103 } 104 printf("%d",ans==0x7fffffff?-1:ans); 105 }
SPFA：
smg啊……一开始的想法是二分a和b……
后来又口胡了一种算法只有15分……
最后发现我还是too young too simple
第一次听说到SPFA动态加边（点）这种操作orz
----------------以下题解-------------------
因为边权有两个，求起来是十分麻烦的
而正解好像要写LCT，然而我并不会
（别问我为什么知道的，因为这道题我翻的题解比你不知道多到哪里去了orz）
所以那我们就把边a排序，然后将边按a从小到大加入，再按b为权值跑SPFA
每次加一条边的时候，将边两边的端点入队再SPFA。
而且因为边是按a从小到大加入的，所以后面dis情况会包含前面的情况，dis数组就不用每次memset每次重新求了
#include<iostream> #include<cstdio> #include<queue> #include<cstring> #include<algorithm> using namespace std; struct node1 { int to,next,a,b; }edge[200020]; struct node2 { int a,b,num; }node; struct node3 { int u,v,l1,l2; }line[100001]; int head[50001],num_edge,dis[50001]; int n,m,maxn,ans=10000000; bool used[50001]; queue <int>q; void add(int u,int v,int l1,int l2)//加边 { ++num_edge; edge[num_edge].to=v; edge[num_edge].next=head[u]; edge[num_edge].a=l1; edge[num_edge].b=l2; head[u]=num_edge; } void spfa(int re,int fun)//动态加点，将新边的两个端点re和fun入队 { used[re]=true; used[fun]=true; q.push(re); q.push(fun); while (!q.empty()) { int x=q.front(); q.pop(); for (int i=head[x];i!=0;i=edge[i].next) if (max(edge[i].b,dis[x])<dis[edge[i].to]) { dis[edge[i].to]=max(edge[i].b,dis[x]); if (!used[edge[i].to]) { used[edge[i].to]=true; q.push(edge[i].to); } } used[x]=false; } } bool cmp(node3 a,node3 b)//按a权值排序 { return a.l1<b.l1; } int main() { int i; scanf("%d%d",&n,&m); for (i=1;i<=m;++i) scanf("%d%d%d%d",&line[i].u,&line[i].v,&line[i].l1,&line[i].l2); sort(line+1,line+m+1,cmp); memset(dis,0x3f,sizeof(dis)); dis[1]=0; q.push(1); used[1]=true; for (i=1;i<=m;++i)//按a从小到大加边 { add(line[i].u,line[i].v,line[i].l1,line[i].l2); add(line[i].v,line[i].u,line[i].l1,line[i].l2); spfa(line[i].u,line[i].v); ans=min(ans,dis[n]+line[i].l1); } if (ans==10000000) printf("-1"); else printf("%d",ans); }