傳送門
前置知識: d i j k s t r a 或 ( k r u s k a l , L i n k − C u t − T r e e ) dijkstra或(kruskal,Link-Cut-Tree) dijkstra或(kruskal,Link−Cut−Tree)
思路：
因為有兩個條件，是以我們可以類似dp那麼先固定一個，再跑spfa求瓶頸路。
同時很明顯可以二分優化。(當然，這還不夠優秀)
時間複雜度大緻為 O ( l o g 2 m ∗ m ∗ n ) ( m ∗ n 都 會 炸 了 ) O(log_2m*m*n)(m*n都會炸了) O(log2m∗m∗n)(m∗n都會炸了)
下面提供兩種正解：
- 動态加點 d i j k s t r a dijkstra dijkstra
- 用 k r u s k a l kruskal kruskal求瓶頸生成樹
1. d i j k s t r a dijkstra dijkstra
我們以b為第一關鍵字排序邊，然後維護最小生成樹。
對于a呢，因為多加一條邊，是以隻有邊的兩個端點可以再貢獻1~n的瓶頸路。
每次加完邊後，答案就為剛加邊的b值+1~n的瓶頸路長度。
代碼by ZZY大佬：
// luogu-judger-enable-o2
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#include<ctype.h>
using namespace std;
struct node3
{
int id,d;
friend bool operator <(node3 x,node3 y)
{
return x.d>y.d;//實際上是小根堆
}
};
priority_queue<node3> f;//堆
int n,m,len=0,ans=2147483647;
struct node1{int x,y,z1,z2;} d[100010];
struct node2{int x,y,z,next;} a[200010];
int last[50010],dis[50010];
bool bz[50010];
inline char getc()//fread優化
{
static char buf[1<<18],*fs,*ft;
return(fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<18,stdin)),fs==ft)?EOF:*fs++;
}
inline int read()
{
char ch=getc(),f=1;
int x=0;
for(;!isgraph(ch);ch=getc());
if(ch=='-') f=-1,ch=getc();
for(;isdigit(ch);ch=getc())
x=((x+(x<<2))<<1)+(ch^0x30);
return x*f;
}
bool cmp(node1 x,node1 y)
{
return x.z1<y.z1;
}
void ins(int x,int y,int z)
{
a[++len]=(node2){x,y,z,last[x]}; last[x]=len;
}
int dijkstra(int st1,int st2)//不完全的dijkstra，同學們可以手打堆來保證堆頂的dis最優。這樣每個點就隻用進一次堆了
{
f.push((node3){st1,dis[st1]});
f.push((node3){st2,dis[st2]});
while(!f.empty())
{
int x=f.top().id;
f.pop();
for(int i=last[x];i;i=a[i].next)
{
int y=a[i].y;
if(dis[y]>max(dis[x],a[i].z))
{
dis[y]=max(dis[x],a[i].z);
if(!bz[y]) f.push((node3){y,dis[y]}),bz[y]=true;
}
}
bz[x]=false;
}
return dis[n];
}
int main()
{
n=read(),m=read();
for(int i=1;i<=m;i++)
d[i].x=read(),d[i].y=read(),d[i].z1=read(),d[i].z2=read();
sort(d+1,d+m+1,cmp);
memset(dis,63,sizeof(dis));
dis[1]=0;
bool flag=false;
for(int i=1;i<=m;i++)
{
if(d[i].z1>=ans) break;
if(d[i].x==d[i].y) continue;
ins(d[i].x,d[i].y,d[i].z2);
ins(d[i].y,d[i].x,d[i].z2);
if(d[i].x==1||d[i].y==1) flag=true;
if(flag) ans=min(ans,d[i].z1+dijkstra(d[i].x,d[i].y));//
}
printf("%d",ans<(int)1e9?ans:-1);
}
提問： 1. 為什麼 d i s dis dis不用每次都 m e m s e t memset memset
~~~~~~~~~~ 2. 如果加的這題邊對瓶頸路沒有貢獻會不會影響答案。
回答：
1.每次 m e m s e t memset memset整個圖都要重跑，複雜度太大。為了保證正确性，加兩個端點，使得這條邊對圖有貢獻就行。
2.分兩種情況讨論：
（1）：這條邊對瓶頸路有貢獻
這樣的話，顯然直接加就行。
（2）：這條邊對瓶頸路無貢獻
這種情況說明這條邊沒有之前的邊優秀，因為每加一條邊就更新一下答案，是以之前就已經更新了較優值，對結果無影響。
2.我們要用生成樹做。
因為b的上限越大，邊越多。（廢話）
是以我們可以按邊的b sort，再求a的瓶頸生成樹。
引理：一個無向圖的最小生成樹一定為瓶頸生成樹。（但瓶頸生成樹不一定為最小生成樹）
證明：可用反證法。假設最小生成樹不為瓶頸生成樹，設最小生成樹的最大邊長度為a，瓶頸路生成樹的最大邊長度為b，則有a>b,那麼瓶頸生成樹的每一條邊都小于a，我們把長度為a的邊（端點為x，y）斷開，換成瓶頸生成樹中連接配接x,y所屬聯通塊的邊，那麼生成樹的大小更小，與最小生成樹的定義沖突，故原命題成立。
是以我們用 k r u s k a l kruskal kruskal維護a的最小生成樹就行。
本題需要動态加邊，是以要用LCT.
因為我們在找1~n的瓶頸路長度時，不能保證1 ~ n的路徑的深度嚴格遞增，是以要換根( m a k e r o o t ( ) makeroot() makeroot())，LCT就是有根樹。
又因為要算邊權，但把邊權放給子節點的方法，由于換根而不能做。是以我們定義多m個點，把邊權壓到這些點上，其他點無權。那麼我們就把求邊權轉化為了求點權。
#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
#define g getchar()
#define lc tr[x].son[0]
#define rc tr[x].son[1]
using namespace std;
const int N=15e4+10,M=1e5+10;//N的範圍需注意
void qr(int &x)
{
char c=g;bool v=x=0;
while(!(isdigit(c)||c=='-'))c=g;//isdigit傳回bool值表示是否為十進制中的字元.isdigit(c)同'0'<=c&&c<='9'
if(c=='-')v=1,c=g;
while(isdigit(c))x=x*10+c-'0',c=g;
if(v)x=-x;
}
struct edge{int x,y,a,b;}a[M];//邊
bool cmp(edge x,edge y){return x.b<y.b;}
int d[N];
struct node{int f,son[2],p;bool v;}tr[N];//p為子樹内d的最大值的标号
void update(int x)
{
tr[x].p=x;
if(lc&&d[tr[x].p]<d[tr[lc].p])tr[x].p=tr[lc].p;
if(rc&&d[tr[x].p]<d[tr[rc].p])tr[x].p=tr[rc].p;
}
void fz(int x)//翻轉
{
tr[x].v=0;swap(lc,rc);
tr[lc].v^=1;tr[rc].v^=1;
}
bool rt(int x){return tr[tr[x].f].son[0]!=x&&tr[tr[x].f].son[1]!=x;}//是否為splay的根
void wh(int x)
{
if(!rt(x))wh(tr[x].f);
if(tr[x].v)fz(x);
}
void rotate(int x,int w)
{
int f=tr[x].f,ff=tr[f].f,r,R;
r=tr[x].son[w];R=f;
tr[R].son[1-w]=r;
if(r)tr[r].f=R;
r=x;R=ff;
if(tr[R].son[0]==f)tr[R].son[0]=r;
else if(tr[R].son[1]==f)tr[R].son[1]=r;
tr[r].f=R;
r=f;R=x;
tr[R].son[w]=r;
tr[r].f=R;
update(f);
update(x);
}
void splay(int x)
{
wh(x);
while(!rt(x))
{
int f=tr[x].f;
if(rt(f))rotate(x,tr[f].son[0]==x);
else
{
int ff=tr[f].f,a=(tr[f].son[0]==x),b=(tr[ff].son[0]==f);
if(a^b)rotate(x,a),rotate(x,b);
else rotate(f,a),rotate(x,a);
}
}
}
void access(int x){for(int y=0;x;x=tr[y=x].f)splay(x),rc=y,update(x);}
void makeroot(int x){access(x);splay(x);tr[x].v^=1;}
int find_root(int x)
{
access(x);splay(x);
while(lc)x=lc;
return x;
}
void split(int x,int y){makeroot(y);access(x);splay(x);}
void link(int x,int y){makeroot(x);tr[x].f=y;access(x);}
void cut(int x,int y){split(x,y);rc=tr[y].f=0;update(x);}
int query(int x,int y){split(x,y);return tr[x].p;}
int fa[N],s[N];//s為子樹大小
int findfa(int x){return fa[x]==x?x:fa[x]=findfa(fa[x]);}
void merge(int x,int y)
{
x=findfa(x);y=findfa(y);
if(s[x]<s[y]){fa[x]=y;s[y]+=s[x];}
else {fa[y]=x;s[x]+=s[y];}
}
int main()
{
int n,m,x,y,z,b;
qr(n);qr(m);
for(int i=1;i<=n;i++)fa[i]=i,s[i]=1;
for(int i=1;i<=m;i++)
qr(x),qr(y),qr(z),qr(b),a[i]=(edge){x,y,z,b};
sort(a+1,a+m+1,cmp);
for(int i=1;i<=m;i++)d[n+i]=a[i].a;
//因為這是一棵無根樹，是以不能把邊權壓到子節點，我們需要多定義m個點，把邊權壓到這些點上，其他點的權為0就行
int ans=N;
for(int i=1;i<=m;i++)
{
x=a[i].x;y=a[i].y;bool v=1;
if(findfa(x)==findfa(y))//再加邊就會形成回路。如果最大權的邊較大，就換下
{
z=query(x,y);
if(d[z]>a[i].a)cut(a[z-n].x,z),cut(z,a[z-n].y);
else v=0;
}
else merge(x,y);
if(v)link(a[i].x,i+n),link(i+n,a[i].y);
if(findfa(1)==findfa(n))
ans=min(ans,a[i].b+d[query(1,n)]);
}
if(ans==N)puts("-1");
else printf("%d\n",ans);
return 0;
}
![最小生成樹-Kruskal（克魯斯卡爾）算法+了解+證明；[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)