日月卦長的解題紀錄: 11月 2015

2015年11月25日星期三

[ zerojudge ] b483:史蒂芙的觀察日記 (link cut tree)

題目:
http://zerojudge.tw/ShowProblem?problemid=b483

解法:
動態加邊的最小生成森林
每增加一條邊後，如果產生環，可以利用迴路性質將環上的最大邊刪除，這個操作可以用link cut tree完成，因為link cut tree無法維護邊權，所以我們把邊轉化成點，也就是在兩個點之間的邊改成一個點，分別連到這兩個點，而他的權重就是邊的權重，類似於這樣:
u-v -> u-k-v，k存的是uv邊的邊權
如此一來只要想辦法維護好原來的那些點權讓他們不會影響到邊權即可

code:

#include<bits/stdc++.h>
#define MAXN 200005
using namespace std;
struct edge{
    int s,t,w;
}e[MAXN/2];
struct splay_tree{
    int pa,ch[2];
    bool rev;
    int ma;
    splay_tree():pa(0),rev(0),ma(0){ch[0]=ch[1]=0;}
}node[MAXN];
int v[MAXN];
int n,m;
inline bool isroot(int x){
    return node[node[x].pa].ch[0]!=x&&node[node[x].pa].ch[1]!=x;
}
inline void up(int x){
    int lc=node[x].ch[0],rc=node[x].ch[1];
    node[x].ma=(v[node[lc].ma]>v[node[rc].ma])?node[lc].ma:node[rc].ma;
    node[x].ma=v[x]>v[node[x].ma]?x:node[x].ma;
}
inline void down(int x){
    if(node[x].rev){
        if(node[x].ch[0])node[node[x].ch[0]].rev^=1;
        if(node[x].ch[1])node[node[x].ch[1]].rev^=1;
        std::swap(node[x].ch[0],node[x].ch[1]);
        node[x].rev^=1;
    }
}
void push_down(int x){
    if(!isroot(x))push_down(node[x].pa);
    down(x);
}
inline void rotate(int x){
    int y=node[x].pa,z=node[y].pa,d=(node[y].ch[1]==x);
    node[x].pa=z;
    if(!isroot(y))node[z].ch[node[z].ch[1]==y]=x;
    node[y].ch[d]=node[x].ch[d^1];
    node[node[y].ch[d]].pa=y;
    node[y].pa=x,node[x].ch[d^1]=y;
    up(y);
    up(x);
}
inline void splay(int x){
    push_down(x);
    while(!isroot(x)){
        int y=node[x].pa;
        if(!isroot(y)){
            int z=node[y].pa;
            if((node[z].ch[0]==y)^(node[y].ch[0]==x))rotate(y);
            else rotate(x);
        }
        rotate(x);
    }
}
inline int access(int x){
    int last=0;
    while(x){
        splay(x);
        node[x].ch[1]=last;
        up(x);
        last=x;
        x=node[x].pa;
    }
    return last;
}
inline void make_root(int x){
    access(x),splay(x);
    node[x].rev^=1;
}
inline void add(int x){
    int s=e[x].s,t=e[x].t;
    make_root(t),node[t].pa=x+n;
    node[x+n].pa=s;
    v[x+n]=e[x].w;
    node[x+n].ma=x+n;
}
inline void del(int x){
    int u=e[x].s,v=e[x].t;
    make_root(u);
    access(v),splay(v);
    node[v].ch[0]=0;
    node[v].ma=node[u].ma=0;
    node[u].pa=node[x+n].pa=0;
    node[u].ch[1]=0;
}
inline int find_root(int x){
    x=access(x);
    while(node[x].ch[0])x=node[x].ch[0];
    splay(x);
    return x;
}
int ans;
inline void insert(int x){
    int u=e[x].s,v=e[x].t,w=e[x].w;
    if(find_root(u)!=find_root(v))add(x),ans+=w;
    else{
        make_root(u),access(v),splay(v);
        if(e[node[v].ma-n].w>w){
            ans-=e[node[v].ma-n].w;
            del(node[v].ma-n);
            ans+=w;
            add(x);
        }
    }
}
int main(){
    for(int cnt=1;~scanf("%d%d",&n,&m);++cnt){
        printf("Case #%d\n",cnt);
        for(int i=0;i<n+m+1;++i){
            node[i].ch[0]=node[i].ch[1]=0;
            node[i].ma=node[i].pa=0;
            node[i].rev=0;
            v[i]=0;
        }
        ans=0;
        for(int i=1;i<=m;++i){
            scanf("%d%d%d",&e[i].s,&e[i].t,&e[i].w);
            insert(i);
            printf("%d\n",ans);
        }
    }
    return 0;
}

2015年11月21日星期六

[ sphere online judge ] SPOJ QTREE - Query on a tree 使用 link-cut tree

題目:
http://www.spoj.com/problems/QTREE/

解法:
這題可以用除了link-cut tree以外的方法來做，速度也會比較快，但是最近在研究link-cut tree，所以就試著用link-cut tree解了。
首先，對於題目給的樹，利用BFS將每個點設成單獨一個樹鏈(之後再access操作的時候就會連起來了，不用擔心)，並每個點都記錄連到父母那條邊的權重，用edge_node陣列記錄每條邊被記錄在哪個點內。因為每個點是紀錄連到父母節點邊的權重，所以不可以有換根的情形發生。修改邊時利用edge_node陣列把要修改的點找出來然後直接修改，查詢則在access的過程中完成。
記住這題node不可以用vector來做，會TLE不知道為什麼

code:

#include<bits/stdc++.h>
using namespace std;
struct splay_tree{
    int ch[2],pa;
    int data,ma;
    splay_tree():pa(0),data(0x80000000),ma(0x80000000){ch[0]=ch[1]=0;}
}node[10005];
inline bool isroot(int x){
    return node[node[x].pa].ch[0]!=x&&node[node[x].pa].ch[1]!=x;
}
inline void up(int x){
    node[x].ma=node[x].data;
    if(node[x].ch[0])node[x].ma=max(node[node[x].ch[0]].ma,node[x].ma);
    if(node[x].ch[1])node[x].ma=max(node[node[x].ch[1]].ma,node[x].ma);
}
inline void rotate(int x){
    int y=node[x].pa,z=node[y].pa,d=(node[y].ch[1]==x);
    node[x].pa=z;
    if(!isroot(y))node[z].ch[node[z].ch[1]==y]=x;
    node[y].ch[d]=node[x].ch[d^1];
    node[node[y].ch[d]].pa=y;
    node[y].pa=x,node[x].ch[d^1]=y;
    up(y);
    up(x);
}
inline void splay(int x){
    while(!isroot(x)){
        int y=node[x].pa;
        if(!isroot(y)){
            int z=node[y].pa;
            if((node[z].ch[0]==y)^(node[y].ch[0]==x))rotate(y);
            else rotate(x);
        }
        rotate(x);
    }
}
inline void access(int x,bool is){
    int last=0;
    while(x){
        splay(x);
        if(!node[x].pa&&is){
            printf("%d\n",max(node[last].ma,node[node[x].ch[1]].ma));
        }
        node[x].ch[1]=last;
        up(x);
        last=x;
        x=node[x].pa;
    }
}
struct EDGE{
    int a,b,c;
}e[10005];
int n;
vector<pair<int ,int > >G[10005];
int pa[10005],edge_node[10005];
inline void bfs(int root){
    std::queue<int > q;
    for(int i=1;i<=n;++i)pa[i]=0;
    q.push(root);
    while(q.size()){
        int u=q.front();
        q.pop();
        for(int i=0;i<(int)G[u].size();++i){
            int v=G[u][i].first;
            if(v!=pa[u]){
                pa[v]=u;
                node[v].pa=u;
                node[v].data=e[G[u][i].second].c;
                edge_node[G[u][i].second]=v;
                up(v);
                q.push(v);
            }
        }
    }
}
char s[10];
int t,a,b;
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(int i=1;i<=n;++i){
            G[i].clear();
            node[i].ch[0]=node[i].ch[1]=node[i].pa=0;
            node[i].data=node[i].ma=0x80000000;
        }
        for(int i=1;i<n;++i){
            scanf("%d%d%d",&e[i].a,&e[i].b,&e[i].c);
            G[e[i].a].push_back(make_pair(e[i].b,i));
            G[e[i].b].push_back(make_pair(e[i].a,i));
        }
        bfs(1);
        while(scanf("%s",s)&&s[0]!='D'){
            scanf("%d%d",&a,&b);
            if(s[0]=='C'){
                a=edge_node[a];
                splay(a);
                node[a].data=b;
                up(a);
            }else{
                access(a,0);
                access(b,1);
            }
        }
    }
    return 0;
}

2015年11月16日星期一

[ codeforces ] 2014 ACM-ICPC Asia Tokyo Regional Contest Problem F 最小生成樹上的必然邊

題目:
http://codeforces.com/gym/100803
給一張圖，找出一些邊，在這張圖的所有最小生成樹中一定會包含它
輸出這些邊的各數及權值總和

解法:
先找出一顆最小生成樹，根據迴路性質，這棵樹上插入其他原本不再最小生成樹上的邊，會形成一個環，刪除環上任意一個與原本插入的邊權值相同的邊，那這顆新產生的樹依然是最小生成樹。因此把每條不再最小生成樹上的邊都檢查一遍，如果會造成某些樹上的邊有機會被刪除，就把這條邊標記，最後剩下沒被標記的邊就是滿足題目要求的邊。

code:

#include<bits/stdc++.h>
using namespace std;
struct P{
    bool is;
    int a,b,c;
    P():is(0),a(0),b(0),c(0){}
    inline const bool operator<(const P&B)const{
        return c<B.c;
    }
}s[50005];
int n,m;
vector<int >G[505];
int pa[505],dep[505];
int st[505],mp[505][505];
int ans,add;
void dfs(int x){
    for(vector<int >::iterator i=G[x].begin();i!=G[x].end();++i){
        if(*i==pa[x])continue;
        pa[*i]=x;
        dep[*i]=dep[x]+1;
        dfs(*i);
    }
}
int find(int x){
    return st[x]==x?x:st[x]=find(st[x]);
}
inline void uion(int a,int b){
    st[find(a)]=find(b);
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)st[i]=i;
    for(int i=0;i<m;++i){
        scanf("%d%d%d",&s[i].a,&s[i].b,&s[i].c);
    }
    sort(s,s+m);
    for(int i=0;i<m;++i){
        if(find(s[i].a)==find(s[i].b)){
            s[i].is=1;
        }else{
            uion(s[i].a,s[i].b);
            ++add;
            ans+=s[i].c;
            mp[s[i].a][s[i].b]=s[i].c;
            mp[s[i].b][s[i].a]=s[i].c;
            G[s[i].a].push_back(s[i].b);
            G[s[i].b].push_back(s[i].a);
        }
    }
    dfs(1);
    for(int i=0;i<m;++i){
        if(s[i].is){
            int a=s[i].a,b=s[i].b;
            if(dep[a]<dep[b])swap(a,b);
            while(dep[a]>dep[b]){
                if(mp[a][pa[a]]==s[i].c){
                    --add;
                    ans-=s[i].c;
                    mp[a][pa[a]]=mp[pa[a]][a]=0;
                }
                a=pa[a];
            }
            while(a!=b){
                if(mp[a][pa[a]]==s[i].c){
                    --add;
                    ans-=s[i].c;
                    mp[a][pa[a]]=mp[pa[a]][a]=0;
                }
                a=pa[a];
                if(mp[b][pa[b]]==s[i].c){
                    --add;
                    ans-=s[i].c;
                    mp[b][pa[b]]=mp[pa[b]][b]=0;
                }
                b=pa[b];
            }
        }
    }
    printf("%d %d\n",add,ans);
    return 0;
}

2015年11月14日星期六

[ codeforces ] 2015 German Collegiate Programming Contest (GCPC 15) + POI 10-T3 Problem M. Sums

題目:
http://codeforces.com/gym/100753

解法:
這是POI的題目，困難度很高，主要想法是使用最短路徑
設a[i]=集合中第i個元素
則d[x]=最小的K滿足 (K-x)整除於a[0]，0<=x<a[0]
可以用dijkstra得到d陣列
用SPFA則會有TLE的風險
最後詢問Q是否d[Q%a[0]]<=Q，如果滿足條件表示Q可以由集合內的數字組成

code:

#include <bits/stdc++.h>
using namespace std;
int INF=2000000000,s[5005],d[50005];
set<pair<int,int > > st;
int t,n,a;
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;++i)scanf("%d",&s[i]);
    for(int i=0;i<s[0];++i)d[i]=INF;
    d[0]=0;
    st.insert(make_pair(d[0],0));
    while(!st.empty()){
        pair<int,int> top=*st.begin();
        st.erase(top);
        int v=top.second;
        int x=top.first;
        for(int i=1;i<n;++i){
            int x2=x+s[i];
            int v2=(v+s[i])%s[0];
            if(x2<d[v2]){
                if(d[v2]<INF)st.erase(make_pair(d[v2],v2));
                d[v2]=x2;
                st.insert(make_pair(d[v2],v2));
            }
        }
    }
    scanf("%d",&m);
    while(m--){
        scanf("%d",&a);
        if(d[a%s[0]]<=a)printf("TAK\n");
        else printf("NIE\n");
    }
    return 0;
}

latex預處理

2015年11月25日 星期三