これは自力ではTLEが回避できず。
http://utpc2013.contest.atcoder.jp/tasks/utpc2013_06
問題
N点・M辺の無向グラフが与えられる。
初期状態で、各点は個別のグループとなっている。
ここでQ個のクエリが与えられる。
各クエリでは、p番の点を含むグループとq番の点を含むグループを併合する。
この時、併合後のグループに含まれる点を連結する最小木の長さを答えよ。
解法
1度併合後の最小木構築で使われなかった辺は以後使われない。
よって、各クエリにおいて以下の辺で最小木を構築すればよい。
- p番のグループを構成する最小木に含まれる辺
- q番のグループを構成する最小木に含まれる辺
- p番のグループとq番のグループを結ぶ辺
点が2000個あるので、3番に含まれる辺は最大min(1000^2,M)本程度ある。
しかしいったん最小木を作れば3つのうち(N-1)辺以下しか残らないので、毎回のクエリでそんなたくさんの辺を処理する必要はない。
class UF { public: static const int ufmax=2002; int ufpar[ufmax],ufrank[ufmax]; UF() { init();} void init(){int i; FOR(i,ufmax) { ufpar[i]=i; ufrank[i]=0; } } int find(int x) { return (ufpar[x]==x)?(x):(ufpar[x] = find(ufpar[x]));} int operator[](int x) {return find(x);} void unite(int x,int y) { x = find(x); y = find(y); if(x==y) return; if(ufrank[x]<ufrank[y]) ufpar[x]=y; else {ufpar[y]=x; if(ufrank[x]==ufrank[y]) ufrank[x]++;} } }; int N,M,Q,num[2002]; int mat[2002][2002]; vector<pair<int,pair<int,int> > > E[2001]; vector<pair<int,pair<int,int> > > TE; UF uf; void solve() { int f,i,j,k,l,x,y,z; cin>>N>>M; FOR(i,N) num[i]=1; FOR(i,M) { cin>>x>>y>>l; mat[x][y]=mat[y][x]=l; } TE.reserve(200000); cin>>Q; while(Q--) { cin>>x>>y; UF uf2; int x2=uf[x],y2=uf[y]; TE.clear(); ITR(it,E[x2]) TE.push_back(*it); ITR(it,E[y2]) TE.push_back(*it); E[x2].clear(); E[y2].clear(); vector<int> g1,g2; FOR(i,N) if(uf[i]==x2) g1.push_back(i); FOR(i,N) if(uf[i]==y2) g2.push_back(i); ITR(it,g1) ITR(it2,g2) if(mat[*it][*it2]) TE.push_back(make_pair(mat[*it][*it2],make_pair(*it,*it2))); sort(TE.begin(),TE.end()); uf.unite(x,y); z=uf.find(x); num[z]=num[x2]+num[y2]; ll tot=0; int nv=num[z]; E[z].clear(); ITR(it,TE) { int fi=it->second.first; int se=it->second.second; if(uf2[fi]==uf2[se]) continue; uf2.unite(fi,se); tot += it->first; nv--; E[z].push_back(*it); } if(nv>1) tot=-1; if(tot==-1) cout << "IMPOSSIBLE" << endl; else cout << tot << endl; } }
まとめ
うまく不使用な辺を落とせなかったけど、落とすのではなく毎回グループ間を結ぶ辺だけ足していけばよかったのね。