なんだこれ…。
https://community.topcoder.com/stat?c=problem_statement&pm=15866
問題
T個の電波塔とN個の町がある。
ラジオ局から各町にクリスマスソングを配信することを考える。
各町xにはパラメータA[x],B[x]があり、ラジオ局が電波塔yからxに曲を届けるコストは(A[x]*y+B[x]) mod (10^9+7)である。
また、すでに曲を受信した町同士で曲を配信することもでき、そのコストも個別に与えられる。
全町に曲を到達させるのにかかる最小コストを求めよ。
解法
A[x]が100以下なので、ラジオ局から町に曲を届ける最適な電波塔の候補は、(A[x]*y+B[x])がyを増やしていくことでn*(10^9+7)をまたぐ高々A[x]通り程度である。
あとは単なる最小全域木問題を解くだけ。
int D[50][50]; ll C[51]; const ll mo=1000000007; template<int um> class UF { public: vector<int> par,rank; UF() {rank=vector<int>(um,0); for(int i=0;i<um;i++) par.push_back(i);} int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));} int operator()(int x,int y) { if((x=operator[](x))==(y=operator[](y))) return x; if(rank[x]>rank[y]) return par[x]=y; rank[x]+=rank[x]==rank[y]; return par[y]=x; } }; class ChristmasSongBroadcast { public: int minimizeCost(int T, vector <int> A, vector <int> B, vector <string> directCost) { UF<51> uf; vector<vector<int>> cand; int N=directCost.size(); int y,x,i; FOR(y,N) FOR(x,y) { cand.push_back({directCost[y][x],y,x}); } FOR(i,N) { ll cur=0; ll S=B[i]; C[i]=B[i]; while(cur<T) { C[i]=min(C[i],S); ll add=min(T-cur,(mo-S+A[i]-1)/A[i]); S+=add*A[i]; S%=mo; cur+=add; } cand.push_back({(int)C[i],i,N}); } sort(ALL(cand)); ll ret=0; FORR(c,cand) { if(uf[c[1]]!=uf[c[2]]) { ret+=c[0]; uf(c[1],c[2]); } } return ret; } }
まとめ
問題のコスト計算の設定が不自然すぎるし、それ以外は単なる最小全域木問題なのであまり楽しめず…。