CF 733 F - Drivers Dissatisfaction
問題
問題概要
個の町と、それらを双方向に結ぶ道が本ある。それぞれの道に対して、ドライバーの不満度がある。
この不満度を下げるために、その道に対してコストがかかる(つまり、ある道の不満度をだけ低下させるためにはだけかかるわけである)。そして、この不満度は0や負にもなりうる。
さて、この本の道の中から本を選んで、main roads
とすることにした。このmain roads
の選び方として、「どの町から他のどの町にも移動可能」でなければならない。
今、予算がある。この予算を使って(使い切る必要はない)、不満度を下げてからmain roads
として本の道を選ぶことを考える。そのときに選んだ本の道の合計の不満度を最小にしたい。
その最小値と、main road
としてどの道を選んだかと、不満度を下げた後のその道の不満度を答えよ。
アイデア
まず、main roads
の定義からこれによって構成されるものは木であるということなのでMSTを構成したいということが分かる。そして、不満度は負でもかまわないということから、予算の使い方としては本の道が決まってしまえばその中でが最小の道に全ての予算をかけるのが最適なのが分かる。
この考察から、予算をつぎ込む辺を全探索することを考える。そして、それで減らしきった後に毎回MSTを初めから構成しているのではかかってしまうので間に合わない。
そこで、とりあえずを無視し、Kruskal法を使って、を基準にしたMSTを構成しておく。そして、予算をつぎ込む辺を全探索するにあたって、このMSTに新たに辺を1つ追加するような感じになる。すると、MSTに閉路ができるので、その閉路の中で最大のを持つ辺を取り除ければ良いことになる。それは、新たに追加しようとしている辺がとを結ぶならそのLCAまでの間で最大のを持つ辺を見つけられればいいことになる。それはLCAを構成するのと同じ要領で、でその辺を見つけられる。
実装大変すぎる...こどふぉって実装重めの問題が多い気がする。LCAのいい練習になった。
実装(C++)
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i)) #define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr) #define all(x) (x).begin(),(x).end() #define pb push_back #define fi first #define se second typedef pair<int,int> pi; // (w,c),(a,b); typedef pair<pi,pi> edge; struct UF{ int n; //正だったらその頂点の親,負だったら根で連結成分の個数 vector<int> d; UF() {} UF(int N):n(N), d(N,-1){} int root(int v){ if(d[v]<0) return v; return d[v]=root(d[v]); } bool unite(int X,int Y){ X=root(X); Y=root(Y); if(X==Y) return false; if(size(X) < size(Y)) swap(X,Y); d[X]+=d[Y]; d[Y]=X; return true; } int size(int v){ return -d[root(v)]; } bool same(int X,int Y){ return root(X)==root(Y); } }; //ノードの個数 const int MAX_V = 200000; //ダブリングに必要なサイズ(log(MAX_V)) const int MAX_LOG_V = 19; //木の隣接リスト表現 vector<int> G[MAX_V]; //根のノード番号 int root = 0; //親を2^k回辿って到達するノード(根を通り過ぎる場合,-1) int parent[MAX_LOG_V][MAX_V]; //根からの深さ int depth[MAX_V]; //現在vに注目、親はp、深さd void lca_dfs(int v, int p, int d){ parent[0][v]=p; depth[v]=d; rep(i,G[v].size()){ if(G[v][i]!=p){ //親でなければ子 lca_dfs(G[v][i], v, d+1); } } } //初期化 void lca_init(int V){ //parent[0]とdepthの初期化 lca_dfs(root, -1, 0); //parentの初期化 for(int k=0; k+1<MAX_LOG_V; ++k){ for(int v=0; v<V; ++v){ if(parent[k][v] < 0) parent[k+1][v]=-1; else parent[k+1][v] = parent[k][parent[k][v]]; } } } //uとvのLCAを求める int lca(int u, int v){ //uとvの深さが同じになるまで親を辿る if(depth[u] > depth[v]) swap(u,v); for(int k=0; k<MAX_LOG_V; ++k){ if((depth[v]-depth[u])>>k & 1) v = parent[k][v]; } if(u==v) return u; //二分探索でLCAを求める for(int k=MAX_LOG_V-1; k>=0; --k){ if(parent[k][u] != parent[k][v]){ u=parent[k][u]; v=parent[k][v]; } } return parent[0][u]; } map<edge,int> eid_for_answer; map<pi,int> edge_to_id; int max_cost_edge_idx[MAX_LOG_V][MAX_V]; edge e[200000]; int main() { int n,m; scanf(" %d %d", &n, &m); rep(i,m) scanf(" %d", &e[i].fi.fi); rep(i,m) scanf(" %d", &e[i].fi.se); rep(i,m) { int a,b; scanf(" %d %d", &a, &b); --a; --b; e[i].se.fi = a; e[i].se.se = b; eid_for_answer[e[i]] = i; eid_for_answer[e[i]] = i; } int S; scanf(" %d", &S); sort(e,e+m); UF uf(n); ll mst_cost=0; vector<bool> used(m,false); rep(i,m) { int a=e[i].se.fi, b=e[i].se.se; if(!uf.same(a,b)) { uf.unite(a,b); mst_cost += e[i].fi.fi; used[i] = true; G[a].pb(b); G[b].pb(a); edge_to_id[pi(a,b)] = i; edge_to_id[pi(b,a)] = i; } } lca_init(n); // 木の上のpath上で最大のwを持つ辺のidをダブリングして持っておく max_cost_edge_idx[0][0]=-1; for(int i=1; i<n; ++i) max_cost_edge_idx[0][i]=edge_to_id[pi(i,parent[0][i])]; rep(i,MAX_LOG_V-1)rep(j,n) { if(j==0) max_cost_edge_idx[i+1][j]=-1; else { if(parent[i][j]==0) max_cost_edge_idx[i+1][j] = max_cost_edge_idx[i][j]; else { int a = max_cost_edge_idx[i][j]; int b = max_cost_edge_idx[i][parent[i][j]]; max_cost_edge_idx[i+1][j] = (e[a].fi.fi>e[b].fi.fi)?a:b; } } } ll ans = mst_cost; int add = -1, rem = -1; rep(i,m) { if(used[i]) { int sub = S/e[i].fi.se; if(ans > mst_cost-sub) { ans = mst_cost-sub; add = i; rem = -1; } } else { int a = e[i].se.fi, b=e[i].se.se; int L = lca(a,b); int max_idx = -1; for(int j=MAX_LOG_V-1; j>=0; --j) { if(depth[a] - depth[L] >= 1<<j) { int t = max_cost_edge_idx[j][a]; if(max_idx == -1 || e[t].fi.fi>e[max_idx].fi.fi) max_idx = t; a = parent[j][a]; } if(depth[b] - depth[L] >= 1<<j) { int t = max_cost_edge_idx[j][b]; if(max_idx == -1 || e[t].fi.fi>e[max_idx].fi.fi) max_idx = t; b = parent[j][b]; } } if(ans > mst_cost - e[max_idx].fi.fi + e[i].fi.fi - S/e[i].fi.se) { ans = mst_cost - e[max_idx].fi.fi + e[i].fi.fi - S/e[i].fi.se; add = i; rem = max_idx; } } } printf("%lld\n", ans); rep(i,m) { if(i==add || (used[i]&&rem!=i)) { printf("%d ", eid_for_answer[e[i]]+1); if(i==add) printf("%d\n", e[i].fi.fi - S/e[i].fi.se); else printf("%d\n", e[i].fi.fi); } } return 0; }