這題我提供兩個解法和兩份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]); }
沒有留言:
張貼留言