2016年3月4日 星期五

[Codeforces Round #286 (Div. 1) pD][Disjoint Set][sqrt method] Mr. Kitayuta's Colorful Graph

原題連結
這題我提供兩個解法和兩份code,都具有相當的啟發性。
解法 1- 1907ms

先說說樸素的解法:
我們將所有邊讀入,每個顏色各建成一張獨立的圖,對於每個詢問我們可以去看每一個顏色的圖中兩點是否有連通,O(M*Q)。
看起來非常糟糕,如果我們在不改變主算法的前提下,想做的更好要怎麼辦呢?

似乎不怎麼樣的優化1: 
  其實根本不用每個顏色的圖都看吧!只要去看和A相鄰的邊顏色的那些圖中,A和B是否連通就好了! (如果和A相鄰的邊比和B相鄰的邊還要多,我們就去戳B)

似乎更不怎麼樣的優化2:
  乾脆開個map來紀錄答案是什麼,重複問的時候就不需要重算了!

你一定想問,這樣做能過嗎?

答案是可以。

而且這就是官方最原本的解答,經過分析時間複雜度是O(m*logm*sqrt(q))。
不妨戳這裡看分析過程。

code:
#include<algorithm>
#include<map>
#include<cstdio>
#include<vector>
using namespace std;
const int maxn=100000+5;
const int maxm=100000+5;
int fa[maxm*2];
int findset(int x) {return x==fa[x]?x:fa[x]=findset(fa[x]);}
struct Edge {int from,to,color;};
vector<Edge> edges;
vector<int> color[maxn];
int pre[maxn];
int getpos(int x,int c)
{
    return pre[x-1]+(lower_bound(color[x].begin(),color[x].end(),c)-color[x].begin());
}
map<pair<int,int>,int> mp;
int main()
{
    int Q,n,m;
    scanf("%d%d",&n,&m);
    for(int i=0,a,b,c;i<m;i++)
    {
        scanf("%d%d%d",&a,&b,&c);
        color[a].push_back(c);
        color[b].push_back(c);
        edges.push_back((Edge){a,b,c});
    }
    for(int i=0;i<=2*m;i++) fa[i]=i;
    pre[0]=0;
    for(int i=1;i<=n;i++)
    {
        sort(color[i].begin(),color[i].end());
        color[i].resize(unique(color[i].begin(),color[i].end())-color[i].begin());
        pre[i]=pre[i-1]+color[i].size();
    }
    for(int i=0;i<m;i++)
    {
        Edge& e=edges[i];
        int a=getpos(e.from,e.color),b=getpos(e.to,e.color);
        fa[findset(a)]=findset(b);
    }
    scanf("%d",&Q);
    for(int i=0,a,b;i<Q;i++)
    {
        scanf("%d%d",&a,&b);
        if(color[a].size()>color[b].size()) swap(a,b);
        if(mp.count(make_pair(a,b))) {printf("%d\n",mp[make_pair(a,b)]);continue;}

        int ans=0;
        for(int j=0;j<color[a].size();j++)
        {
            int c=color[a][j];
            if(binary_search(color[b].begin(),color[b].end(),c) 
                && findset(getpos(a,c))==findset(getpos(b,c))) ans++; 
        }
        mp[make_pair(a,b)]=ans;
        printf("%d\n",ans);
    }
}

如果你跟我一樣,覺得解法1似乎不太靠譜。
那歡迎你使用解法2。

解法2 - 889ms

我們先思考兩種很簡單的作法:

1.求出所有顏色的圖,C(點數,2)去更新所有點對的答案。
--> O(sum(圖中點數*圖中點數))
2.求出所有顏色的圖,掃過所有詢問去更新答案。
--> O(詢問數*顏色數)

第1個方法在圖中點數非常多的時候會很慢,第2個方法在顏色數很多的時候會很慢。
我們設置一個值B,當圖中點數<=B時採取第一個作法,否則採取第二個作法。

那麼複雜度會怎麼樣變化呢?應該是
O(B*B*情況1出現次數 + 詢問數*情況2出現次數)

不難發現,情況1出現次數上限是O(N/B),情況2出現次數上限也是O(N/B) (並沒有那麼直觀,想一想,為什麼)

那麼總複雜度就是
O(B*N+Q*N/B),我們取B=sqrt(N),最後複雜度就是

O(N*sqrt(N) + Q*sqrt(N))

實際表現比解法1快了2倍,相當不錯。

code:

#include<algorithm>
#include<cstdio>
#include<map>
#include<vector>
#include<cmath>
using namespace std;
const int maxn=100000+5;
const int maxm=100000+5;
const int maxQ=100000+5;
int fa[maxn],show[maxn],ans[maxQ];
int findset(int x) {return x==fa[x]?x:fa[x]=findset(fa[x]);}
struct Edge{int from,to;};
struct Query{int a,b;};
vector<Edge> edges[maxm];
vector<Query> qu;
map<pair<int,int>,int> mp;
int main()
{
    int Q,n,m;
    scanf("%d%d",&n,&m);
    for(int i=0,a,b,c;i<m;i++)
    {
        scanf("%d%d%d",&a,&b,&c);
        edges[c].push_back((Edge){a,b});
    }
    scanf("%d",&Q);
    for(int i=0,a,b;i<Q;i++)
    {
        scanf("%d%d",&a,&b);
        if(a>b) swap(a,b);
        qu.push_back((Query){a,b});
    }
    int B=sqrt(n);
    for(int i=1;i<=m;i++)
    {
        if(edges[i].size()==0) continue;
        vector<int> vec;
        for(int j=0;j<edges[i].size();j++)
        {
            vec.push_back(edges[i][j].from);
            vec.push_back(edges[i][j].to);
        }
        sort(vec.begin(),vec.end());
        vec.resize(unique(vec.begin(),vec.end())-vec.begin());

        for(int j=0;j<vec.size();j++) fa[vec[j]]=vec[j],show[vec[j]]=i;
        for(int j=0;j<edges[i].size();j++) fa[findset(edges[i][j].from)]=findset(edges[i][j].to);
        if(vec.size()<=B) // brute
        {
            for(int j=0;j<vec.size();j++)
                for(int k=j+1;k<vec.size();k++) if(findset(vec[j])==findset(vec[k]))
                    mp[make_pair(min(vec[j],vec[k]),max(vec[j],vec[k]))]++;
        }
        else // update every query
        {
            for(int j=0;j<Q;j++)
                if(show[qu[j].a]==i && show[qu[j].b]==i && findset(qu[j].a)==findset(qu[j].b))
                    ans[j]++;
        }
    }
    for(int i=0;i<Q;i++) printf("%d\n",mp[make_pair(qu[i].a,qu[i].b)]+ans[i]);
}

沒有留言:

張貼留言