NOI2014魔法森林
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
「输入样例1」
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
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。
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
题解
这题kruskal竟然可以拿70分0.0，噢spfa可以拿100分
学习一下LCT这题就是模板
按照一种权a排序后，然后不停加边，并用LCT维护1-n权b最大值即可
如果边的两端不连通，就直接加入这条边
连通的话加入形成环，删去环上最大值
边可以建成点，并往边的两端连边，在点上维护权值信息
70分
|
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 |
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #define ll long long #define inf 1000000000 using namespace std; inline ll read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m,ans,mn=inf; int fa[50005],disc[100005]; struct edge{int x,y,a,b;}e[100005]; int find(int x) { return x==fa[x]?x:fa[x]=find(fa[x]); } inline bool operator<(edge a,edge b) { return a.b<b.b; } inline bool cal(int x) { for(int i=1;i<=n;i++) fa[i]=i; for(int i=1;i<=m;i++) { if(e[i].a>x)continue; int p=find(e[i].x),q=find(e[i].y); if(p!=q) { fa[p]=q; ans=e[i].b; if(find(1)==find(n))return 1; } } return 0; } int main() { //freopen("forest.in","r",stdin); //freopen("forest.out","w",stdout); n=read();m=read(); for(int i=1;i<=m;i++) { e[i].x=read();e[i].y=read();e[i].a=read();e[i].b=read(); disc[i]=e[i].a; } sort(e+1,e+m+1); sort(disc+1,disc+m+1); for(int i=m;i;i--) { if(disc[i]==disc[i+1])continue; int t=disc[i]; ans=0; if(cal(t))mn=min(mn,t+ans); else break; } if(mn!=inf)printf("%d\n",mn); else printf("-1\n"); return 0; } |
100分
|
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 130 131 132 133 134 135 136 137 |
#include<cstdio> #include<iostream> #include<algorithm> #define inf 1000000000 #define ll long long using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int top,q[200005]; int n,m,ans=inf; int mx[200005],val[200005]; int p[200005],fa[200005],c[200005][2]; bool rev[200005]; struct data{ int u,v,a,b; }e[100005]; int find(int x) { return x==p[x]?x:p[x]=find(p[x]); } bool operator<(data a,data b) { return a.a<b.a; } bool isroot(int x) { return c[fa[x]][0]!=x&&c[fa[x]][1]!=x; } void update(int x) { int l=c[x][0],r=c[x][1]; mx[x]=x; if(val[mx[l]]>val[mx[x]])mx[x]=mx[l]; if(val[mx[r]]>val[mx[x]])mx[x]=mx[r]; } void pushdown(int x) { int l=c[x][0],r=c[x][1]; if(rev[x]) { rev[x]^=1;rev[l]^=1;rev[r]^=1; swap(c[x][0],c[x][1]); } } void rotate(int &x) { int y=fa[x],z=fa[y],l,r; if(c[y][0]==x)l=0;else l=1;r=l^1; if(!isroot(y)) { if(c[z][0]==y)c[z][0]=x; else c[z][1]=x; } fa[x]=z;fa[y]=x;fa[c[x][r]]=y; c[y][l]=c[x][r];c[x][r]=y; update(y);update(x); } void splay(int &x) { top=0;q[++top]=x; for(int i=x;!isroot(i);i=fa[i])q[++top]=fa[i]; while(top)pushdown(q[top--]); while(!isroot(x)) { int y=fa[x],z=fa[y]; if(!isroot(y)) { if(c[y][0]==x^c[z][0]==y)rotate(x); else rotate(y); } rotate(x); } } void access(int x) { for(int t=0;x;t=x,x=fa[x]) splay(x),c[x][1]=t,update(x); } void makeroot(int x) { access(x);splay(x);rev[x]^=1; } void link(int x,int y) { makeroot(x);fa[x]=y; } void cut(int x,int y) { makeroot(x);access(y);splay(y); c[y][0]=fa[x]=0;update(y); } int query(int x,int y) { makeroot(x);access(y);splay(y); return mx[y]; } int main() { n=read();m=read(); for(int i=1;i<=n;i++)p[i]=i; for(int i=1;i<=m;i++) { e[i].u=read();e[i].v=read();e[i].a=read();e[i].b=read(); } sort(e+1,e+m+1); int tot=0; for(int i=1;i<=m;i++) { int u=e[i].u,v=e[i].v,a=e[i].a,b=e[i].b; if(find(u)==find(v)) { int t=query(u,v); if(val[t]>e[i].b) { cut(t,e[t-n].u); cut(t,e[t-n].v); } else { if(find(1)==find(n))ans=min(ans,e[i].a+val[query(1,n)]); continue; } } else p[find(u)]=find(v); val[n+i]=e[i].b;mx[n+i]=n+i; link(u,n+i);link(v,n+i); if(find(1)==find(n))ans=min(ans,e[i].a+val[query(1,n)]); } if(ans==inf)puts("-1"); else printf("%d\n",ans); return 0; } |
计数器 9304217
OI 课件=>
OI 课件=>
黄学长，第125行那句话没用吧。。。
为什么
orz45分钟学会LCT
啥 。。。
其实可以用spfa水过。。。
orz暴力写错还有55分的爷
卧槽为何怒D
毕竟是神