天天看點
傳回

UOJ #3(【NOI2014】魔法森林-LCT區間最值)#3. 【NOI2014】魔法森林

#3. 【NOI2014】魔法森林

統計

  • 描述
  • 送出
  • 自定義測試

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

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

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

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

輸入格式

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

接下來 m 行，第 i+1 行包含4個正整數 xi,yi,ai,bi ，描述第 i 條無向邊。其中 xi 與 yi 為該邊兩個端點的标号， ai 與 bi 的含義如題所述。

注意資料中可能包含重邊與自環。

輸出格式

輸出一行一個整數：如果小E可以成功拜訪到隐士，輸出小E最少需要攜帶的守護精靈的總個數；如果無論如何小E都無法拜訪到隐士，輸出“ -1 ”（不含引号）。

樣例一

input 

4 5
1 2 19 1
2 3 8 12
2 4 12 15
1 3 17 8
3 4 1 17

output 

32

explanation

如果小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 個守護精靈。

樣例二

input 

3 1
1 2 1 1

output 

-1

explanation

小E無法從1号節點到達3号節點，故輸出-1。

樣例三

見樣例資料下載下傳

限制與約定

測試點編号 n m ai,bi
1 2≤n≤5 0≤m≤10 1≤ai,bi≤10
2
3
4 2≤n≤500 0≤m≤3000 1≤ai,bi≤50000
5
6
7 2≤n≤5000 0≤m≤10000
8
9
10
11 2≤n≤50000 0≤m≤100000

1≤ai≤30

1≤bi≤50000
12
13
14
15 1≤ai,bi≤50000
16
17
18
19
20

時間限制： 3s

空間限制： 512MB

把邊用ai排序

直接用LCT去維護圖

如果形成環，就删除這個環上的bi最大邊

#include<bits/stdc++.h>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=next[p])  
#define Lson (x<<1)
#define Rson ((x<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,127,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define INF (2139062143)
#define F (100000007)
#define MAXN (250000+10)
#define MAXM (200000+10)
#define mp make_pair  
#define fi first
#define se second
typedef long long ll;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return (a-b+(a-b)/F*F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}

int n,m;

class LCT
{
public:
    int father[MAXN],siz[MAXN];
    int ch[MAXN][];
    bool root[MAXN];
    bool rev[MAXN];
    ll val[MAXN];
    pair<ll,int> maxv[MAXN];
    void mem(int n)
    {
        MEM(father) MEM(siz) MEM(root)
        For(i,n+) siz[i]=root[i]=,maxv[i]=mp(,i);    root[]=;
        MEM(ch)  MEM(rev)
        MEM(val)
    }

    void set(int x,ll bi){
        val[x]=bi;
        maxv[x]=mp(bi,x); 
    }

    void pushdown(int x)
    {
        if (!x) return ; 
        if (rev[x]) {
            if (ch[x][]) rev[ch[x][]]^=;
            if (ch[x][]) rev[ch[x][]]^=;
            swap(ch[x][],ch[x][]);
            rev[x]^=;
        } 
    }
    void maintain(int x)
    {
        siz[x]=siz[ch[x][]]+siz[ch[x][]]+;
        maxv[x]=max(max(maxv[ch[x][]],maxv[ch[x][]]),mp(val[x],x)); 

    }
    void rotate(int x)
    {
        int y=father[x],kind=ch[y][]==x;

        ch[y][kind]=ch[x][!kind];
        if (ch[y][kind]) {
            father[ch[y][kind]]=y;
        }
        father[x]=father[y];
        father[y]=x;
        ch[x][!kind]=y;
        if (root[y])
        {
            root[x]=;root[y]=;
        }
        else
        {
            ch[father[x]][ ch[father[x]][]==y ] = x;
        }
        maintain(y);maintain(x);
    }

    void P(int x)
    {
        if (!root[x]) P(father[x]);
        pushdown(x);
    }

    void splay(int x)
    {
        P(x);
        while(!root[x])
        {
            int y=father[x];
            int z=father[y];
            if (root[y]) rotate(x);
            else if ( (ch[y][]==x)^(ch[z][]==y) )
            {
                rotate(x); rotate(x);
            } 
            else 
            {
                rotate(y); rotate(x);
            }
        } 
    }



    int access(int x)
    {
        int y=;
        do
        {
            splay(x);
            if (ch[x][]) root[ch[x][]]=;
            ch[x][]=y;
            if (y) root[y]=;       
            maintain(x);
            y = x;
            x=father [x]; 
        } while (x) ;
        return y;
    }

    void cut(int x)
    {
        access(x);
        splay(x);

        father[ch[x][]]=;
        root[ch[x][]]=;
        ch[x][]=;
        maintain(x);
    }

    void join(int x,int y)
    {
        make_root(x);
        access(y);
        splay(y);
        ch[y][]=x;
        father[x]=y;
        maintain(y);
        root[x]=;
    }
    void reverse(int x){
        rev[x]^=;   // 标記記完後迅速處理 
    }
    void make_root(int x){
        access(x);splay(x);
        reverse(x);pushdown(x);
    }
    int get_root(int x){
        access(x);
        splay(x);
        do {
            pushdown(x);
            if (ch[x][]) x=ch[x][];
            else break;
        }while();
        return x;
    }

    bool find(int x,int y)
    {
        while (father[x]) x=father[x];
        while (father[y]) y=father[y];
        return x==y; 
    }

    pair<ll,int> query(int x,int y) {
        make_root(x);
        access(y);
        splay(y);
        return maxv[y];
    }

}S;

struct Edge{
    int x,y,a,b;
    friend bool operator<(Edge a,Edge b) {
        return a.a!=b.a? a.a<b.a : a.b<b.b; 
    }
    void scan(){
        scanf("%d%d%d%d",&x,&y,&a,&b);
    }
}e[MAXM];


int main()
{
    freopen("bzoj3669.in","r",stdin);
//  freopen(".out","w",stdout);

    scanf("%d%d",&n,&m);
    S.mem(n+m);
    For(i,m) {
        e[i].scan();     
    }
    sort(e+,e++m);
    For(i,m) S.set(n+i,e[i].b);



    ll ans=INF;
    For(i,m) {
        if (e[i].x==e[i].y) continue;
        if (S.find(e[i].x,e[i].y)) {
            pair<ll,int> p= S.query(e[i].x,e[i].y);
            if (p.fi<=e[i].b) continue;
            int u=e[p.se-n].x,v=e[p.se-n].y; 
            S. make_root(p.se);
            S.cut(u); S.cut(v);
        } 

        S.join(e[i].x,n+i); 
        S.join(e[i].y,n+i); 

        if (!S.find(,n)) continue; 
        ll nowans=e[i].a+S.query(,n).first;

        ans=min(ans,nowans);

    }

    if (ans==INF) puts("-1");
    else printf("%d\n",(int)ans); 



    return ;
}
lct uoj
上一篇: RocketMQ的NameServer執行流程學習梳理
下一篇: SpringBoot 啟動參數設定環境變量、JVM參數、tomcat遠端調試

繼續閱讀