SRM627 Medium
Class:getMinimumInversions
問題概要:n(<=1000)頂点の無向木に辺を一本足したもの(多重辺,self loopなし)が与えられる.それぞれの頂点には整数V[i](1<=V[i]<=1000)が定まっている.K個の異なる点からなる木上の経路Cをうまく選んで、V[C_1],V[C_2],...V[C_K]の転倒数の最小を求めよ.Cが取れない場合は-1を返せ.
解答:
dfs適当にやって良い,InversionはBITでできる(Vの値の方で持つ)のだが、dfsの引数にvectorint bitとかを持って中でbit2を宣言してコピーして再帰とかするとコピーコストが大量にかかって死にます(死にました)
呼び出し時にvisited[i]=true,return時にvisited[i]=falseとすれば再帰がうまくいくことを知っているなら、同様にbitに足した分を減らして返せば良い(Marathonとかだと当たり前の工夫)
コード:
#include <iostream> #include <vector> #define rep(i,n) for(int i=0;i<n;i++) #define rep1(i,n) for(int i=1;i<=n;i++) #define all(c) c.begin(),c.end() #define pb push_back #define fs first #define sc second using namespace std; vector<int> G[1000],V,bit(1001); bool visited[1000]; class GraphInversions{ public: int mn=1e8; void add(int i,int x){ while(i<=1000){ bit[i]+=x; i+=(i&-i); } } int sum(int i){ int s=0; while(i>0){ s+=bit[i]; i-=(i&-i); } return s; } void dfs(int x,int cnt,int ret){ visited[x]=true; ret-=sum(V[x]); add(V[x],1); // cout << x << " " << cnt << " " << ret << endl; // rep(i,5) cout << visited[i] << " "; // cout << endl; if(cnt==1){ // cout << ret << endl; mn=min(mn,ret); visited[x]=false; add(V[x],-1); return; } rep(i,G[x].size()){ if(visited[G[x][i]]) continue; dfs(G[x][i],cnt-1,ret); } visited[x]=false; add(V[x],-1); } int getMinimumInversions(vector <int> A, vector <int> B, vector <int> Vc, int K){ V=Vc; int n=A.size(); rep(i,n){ G[A[i]].pb(B[i]); G[B[i]].pb(A[i]); } rep(i,n) dfs(i,K,K*(K-1)/2); if(mn==1e8) mn=-1; return mn; } };