Description

為了得到書法大家的真傳，小 E 同學下定決心去拜訪住在魔法森林中的隱士。魔法森林可以被看成一個包含 n 個節點 m 條邊的無向圖，節點標號為1,2,3, … , n，邊標號為 1,2,3, … , m。初始時小 E 同學在 1 號節點，隱士則住在 n 號節點。小 E 需要通過這一片魔法森林，才能夠拜訪到隱士。

魔法森林中居住了一些妖怪。每當有人經過一條邊的時候，這條邊上的妖怪就會對其發起攻擊。 幸運的是， 在 1 號節點住著兩種守護精靈： A 型守護精靈與B 型守護精靈。小 E 可以借助它們的力量，達到自己的目的。

只要小 E 帶上足夠多的守護精靈， 妖怪們就不會發起攻擊了。具體來說， 無向圖中的每一條邊 ei 包含兩個權值 ai 與 bi 。 若身上攜帶的 A 型守護精靈個數不少于 ai ，且 B 型守護精靈個數不少于 bi ，這條邊上的妖怪就不會對通過這條邊的人發起攻擊。當且僅當通過這片魔法森林的過程中沒有任意一條邊的妖怪向小 E 發起攻擊，他才能成功找到隱士。

由于攜帶守護精靈是一件非常麻煩的事，小 E 想要知道， 要能夠成功拜訪到隱士，最少需要攜帶守護精靈的總個數。守護精靈的總個數為 A 型守護精靈的個數與 B 型守護精靈的個數之和。

Input

輸入文件的第 1 行包含兩個整數 n, m，表示無向圖共有 n 個節點， m 條邊。

接下來 m 行，第 i + 1 行包含 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

Sample Output

【樣例輸出 1】

32

【樣例輸出 2】

-1

Data Constraint

Solution

• 先按邊的 a 值排序，從小到大依次加入圖中。

• 若邊連接的是兩個不同的連通塊，則直接連通。

• 否則就從生成樹中找到最大的那條邊，刪掉，改為連當前的邊。

• 這個操作用 LCT 維護即可。

• 若連接后 1 和 n 是聯通的，就更新一下答案即可。

• 注意由于權值在邊上，所以要新開一個點作為權值，再連向兩個端點。

• 時間復雜度 O(M log (N+M)) 。

Code

#include<cstdio> #include<algorithm> #include<cctype> using namespace std; const int N=2e5+3; struct data {int x,y,a,b; }a[N]; int ans=N,top; int fa[N],s[N][2],st[N],mx[N],num[N]; bool rev[N]; inline int read() {int X=0,w=0; char ch=0;while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();return w?-X:X; } inline bool cmp(data x,data y) {return x.a<y.a; } inline int max(int x,int y) {return x>y?x:y; } inline bool pd(int x) {return x==s[fa[x]][1]; } inline bool isroot(int x) {return s[fa[x]][0]^x && s[fa[x]][1]^x; } inline void modify(int x) {if(x) swap(s[x][0],s[x][1]),rev[x]^=1; } inline void update(int x) {num[x]=mx[num[s[x][0]]]>mx[num[s[x][1]]]?num[s[x][0]]:num[s[x][1]];if(mx[x]>mx[num[x]]) num[x]=x; } inline void down(int x) {if(rev[x]){modify(s[x][0]),modify(s[x][1]);rev[x]=false;} } inline void rotate(int x) {int y=fa[x],w=pd(x);if(s[y][w]=s[x][w^1]) fa[s[x][w^1]]=y;if((fa[x]=fa[y]) && !isroot(y)) s[fa[y]][pd(y)]=x;s[fa[y]=x][w^1]=y;update(y); } inline void splay(int x) {for(int y=st[top=1]=x;!isroot(y);y=fa[y]) st[++top]=fa[y];while(top) down(st[top--]);for(int y;!isroot(x);rotate(x))if(!isroot(y=fa[x])) rotate(pd(x)==pd(y)?y:x);update(x); } inline void access(int x) {for(int y=0;x;x=fa[y=x]) splay(x),s[x][1]=y,update(x); } inline void mkroot(int x) {access(x),splay(x),modify(x); } inline void link(int x,int y) {mkroot(x),fa[x]=y; } inline void cut(int x,int y) {mkroot(x),access(y),splay(y);s[y][0]=fa[x]=0; } inline int get(int x) {access(x),splay(x);int y=x;while(s[y][0]) y=s[y][0];return y; } int main() {int n=read(),m=read();for(int i=1;i<=m;i++) a[i].x=read(),a[i].y=read(),a[i].a=read(),a[i].b=read();sort(a+1,a+1+m,cmp);for(int i=1;i<=m;i++){int x=a[i].x,y=a[i].y,z=i+n;mx[num[z]=z]=a[i].b;if(get(x)^get(y)) link(x,z),link(y,z); else{mkroot(x),access(y),splay(y);if(a[i].b<mx[num[y]]){int p=num[y];cut(p,a[p-n].x),cut(p,a[p-n].y);link(z,x),link(z,y);}}if(get(1)==get(n)){mkroot(n),access(1),splay(1);if(a[i].a+mx[num[1]]<ans) ans=a[i].a+mx[num[1]];}}printf("%d",ans==N?-1:ans);return 0; } 與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的BZOJ 3669 . JZOJ 3754. 【NOI2014】魔法森林的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。