- Link https://www.luogu.com.cn/problem/P2387
- Solution
感觉自己做完全靠蒙和猜, 尽管是正解但并不知道为什么. 看了题解才知道原来是生成树满足这个性质.
暴力可以枚举 \(max\{a\}\), 然后在此条件下找 \(max\{b\}\)最小的 \(1\)到 \(n\)的路径.
优化可以参照 kruskal 的思想.
先把所有边按 \(a_i\)从小到大排序. 维护一个 \(b\)的最小生成树. 依次枚举每条边, 那么此时 \(a_i\)就是全局最大的 \(a\). 如果加入这条边不形成环, 就直接加入. 如果形成环, 根据生成树的回路性质, 某个回路中的权值最大边恰好有一条不在最小生成树中 (引用自 luogu 题解). 所以找到环上 \(max\{b\}\), 和 \(b_i\) 做比较, 如果 \(b_i\)较小就用这条边替换.
答案就是 \(1\)和 \(n\)联通以后每次的 \(a_i+max\{b_k\}(k\in Path_{1\rightarrow n})\)取 \(min\).\(Path_{1\rightarrow n}\)指 \(1\)到 \(n\)的路径.
考虑为什么这样是对的. 如果这条边在 \(1\)到 \(n\)路径上, 显然是对的. 如果不在, 那么 \(1\)到 \(n\)路径上的 \(max\{a\}\)肯定不大于 \(a_i\), 那么一定在以前枚举过这条边, 更新过答案. 所以这一次并不会对答案造成影响.
- Code
- #include<bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- #define REP(i,a,b) for(int i=(a),ed=(b);i<=ed;++i)
- inline int read(){
- register int x=0,f=1;register char ch=getchar();
- while(!isdigit(ch)){if(ch=='-')f=0;ch=getchar();}
- while(isdigit(ch)){x=x*10+(ch^'0');ch=getchar();}
- return f?x:-x;
- }
- const int N=5e4+10,M=1e5+10;
- int n,m,ans=0x7fffffff,f[N];
- struct edge{int x,y,a,b;inline bool operator<(const edge &s){return a<s.a;}}e[M];
- inline int find(int x){return f[x]=(f[x]==x?f[x]:find(f[x]));}
- namespace LinkCutTree{
- const int _=N+M;
- int fa[_],ch[_][2],r[_],mx[_],v[_];
- inline int Max(int x,int y){return v[x]<v[y]?y:x;}
- inline void pushup(int x){mx[x]=Max(x,Max(mx[ch[x][0]],mx[ch[x][1]]));}
- inline void pushr(int x){swap(ch[x][0],ch[x][1]);r[x]^=1;}
- inline void pushdown(int x){if(r[x])pushr(ch[x][0]),pushr(ch[x][1]),r[x]=0;}
- inline int getdir(int x){return x==ch[fa[x]][1];}
- inline bool noroot(int x){return x==ch[fa[x]][0]||x==ch[fa[x]][1];}
- inline void rotate(int x){
- int f=fa[x],p=fa[f],k=getdir(x),s=ch[x][k^1];
- ch[x][k^1]=f;ch[f][k]=s;if(noroot(f))ch[p][getdir(f)]=x;
- fa[f]=x;fa[x]=p;if(s)fa[s]=f;
- pushup(f);
- }
- inline void splay(int x){
- static int stk[_];
- int tp=0,y=x;stk[++tp]=y;
- while(noroot(y))stk[++tp]=y=fa[y];
- while(tp)pushdown(stk[tp--]);
- for(int f=fa[x];noroot(x);rotate(x),f=fa[x])
- if(noroot(f))rotate(getdir(f)==getdir(x)?f:x);
- pushup(x);
- }
- inline void access(int x){
- for(int y=0;x;y=x,x=fa[x])
- splay(x),ch[x][1]=y,pushup(x);
- }
- inline void makeroot(int x){
- access(x),splay(x),pushr(x);
- }
- inline void split(int x,int y){
- makeroot(x);access(y);splay(y);
- }
- inline void cut(int x,int y){
- split(x,y);
- fa[x]=ch[y][0]=0;
- }
- }using namespace LinkCutTree;
- int main(){
- n=read(),m=read();
- REP(i,1,m)e[i]=(edge){read(),read(),read(),read()};
- sort(e+1,e+m+1);
- REP(i,1,n)f[i]=i;
- REP(t,1,m){
- if(e[t].x==e[t].y)continue;
- int x=find(e[t].x),y=find(e[t].y);
- if(x^y){
- f[x]=y;x=e[t].x,y=e[t].y;
- v[n+t]=e[t].b;
- makeroot(x);fa[fa[x]=n+t]=y;
- }
- else{
- x=e[t].x,y=e[t].y;
- split(x,y);int s=mx[y];
- if(v[s]>e[t].b){
- cut(x,s);cut(y,s);
- v[n+t]=e[t].b;
- makeroot(x);fa[fa[x]=n+t]=y;
- }
- }
- if(find(1)==find(n)){
- split(1,n);
- ans=min(ans,e[t].a+e[mx[n]-n].b);
- }
- }
- if(ans<(int)0x7fffffff)printf("%d\n",ans);
- else puts("-1");
- return 0;
- }
Luogu2387 [NOI2014]魔法森林
来源: http://www.bubuko.com/infodetail-3359847.html