【2018/07/16テストT 2】【SDOJ 2509】乳牛大集会
【テーマ】
タイトルの説明:
Bessieは年に一度の乳牛大集会を計画しており、全国各地からの乳牛が将来参加する.もちろん、彼女は最も便利な場所を選んで今回の集会を開催します.
各乳牛はN(1<=N<=100000)の農場の1つに居住し、これらの農場はN-1の道路で接続され、いずれの農場からも別の農場に到達することができる.道路i接続農場A_iとB_i(1<=A_i<=N;1<=B_i<=N)、長さL_i(1 <= L_i <= 1,000).集会はN農場のいずれかで行うことができる.また、牛舎ごとに居住者C_i(0<=C_i<=1000)乳牛のみ.
集会の場所を選ぶ際、Bessieは便利さを最大化(つまり不便さを最小化)することを望んでいる.例えば、集会場所としてX番目の農場を選択すると、その不便さは他の牛小屋の乳牛が集会に参加するための道のりの和である(例えば、農場iが農場Xに到着する距離は20であり、総道のりはC_i*20である).Bessieが最も便利な場所を見つけて大集会を開くのを助ける.
5つの農場からなる国を考えて、それぞれ長さの異なる道路でつながっています.すべての農場では、3番と4番は乳牛が住んでいません. 1 3 4 5
@--1--@--3--@--3--@[2]
[1] |
2
|
@[1]
2
Bessieは5つの農場のいずれかで集会を開催することができ、以下は各場所で集会を開催する不便な値の統計表である. ----- ------
B1 B2 B3 B4 B5 Total
1 0 3 0 0 14 17
2 3 0 0 0 16 19
3 1 2 0 0 12 15
4 4 5 0 0 6 15
5 7 8 0 0 0 15
Bessieが農場1で集会を開くと、各農場のそれぞれの不便値は 1 0 -- !
2 3 -- 2+1=3 x 1 = 3
3 0 -- !
4 0 -- !
5 14 -- 3+3+1=7 x 2 = 14
したがって,全体的な不便値は17である.
最小の不便値は15で、3日、4日、または5日に農場で集会を開いたときです.
入力形式:
1行目:整数N
2行目からN+1行目:i+1行目に整数C_があるi
N+2行目から2*N行目、i+N+1行目の3つの整数:A_i,B_iとL_i.
出力フォーマット:
1行目:最小の不便な値を表す値.
サンプルデータ:
入力
5 1 1 0 0 2 1 3 1 2 3 2 3 4 3 4 5 3
しゅつりょく
15
コメント:
データ規模と約束:
30%データ:N<=30
100%データ:N<=10000000,0<=Ci,Wi<=1000
【分析】
本題で使用する知識点:ツリーDP+反発原理+ルート変更
f[i]を定義してiをキーとする答えを表す
dis[i]はiから1までの距離を表す
num[i]はiを元とする子数点権の和を表し、totは総点権和である
現在dpからi番ノード,jはiの息子であり,wはこのときの辺権であると仮定する.
では、f[j]=f[i]+(tot-num[j])*w-num[j]*w;
親ノードから子ノードに移行すると、反発しにくくなりますので、図面を描いて理解することをお勧めします.
【コード】 #include
#include
#include
using namespace std;
const int N=100005,M=200005;
int n,t;
int c[N],first[N];
int v[M],w[M],next[M];
long long ans,tot,f[N],num[N],dis[N];
void add(int x,int y,int z)
{
t++;
next[t]=first[x];
first[x]=t;
v[t]=y;
w[t]=z;
}
void dfs(int x,int father)
{
int i,j;
num[x]+=c[x];
for(i=first[x];i;i=next[i])
{
j=v[i];
if(j==father)
continue;
dis[j]=dis[x]+w[i];
dfs(j,x);
num[x]+=num[j];
}
}
void dp(int x,int father)
{
int i,j;
for(i=first[x];i;i=next[i])
{
j=v[i];
if(j==father)
continue;
f[j]=f[x]+(tot-num[j])*w[i]-num[j]*w[i];
ans=min(ans,f[j]);
dp(j,x);
}
}
int main()
{
int x,y,z,i;
scanf("%d",&n);
for(i=1;i<=n;++i)
{
scanf("%d",&c[i]);
tot+=c[i];
}
for(i=1;i
1 3 4 5
@--1--@--3--@--3--@[2]
[1] |
2
|
@[1]
2 ----- ------
B1 B2 B3 B4 B5 Total
1 0 3 0 0 14 17
2 3 0 0 0 16 19
3 1 2 0 0 12 15
4 4 5 0 0 6 15
5 7 8 0 0 0 15 1 0 -- !
2 3 -- 2+1=3 x 1 = 3
3 0 -- !
4 0 -- !
5 14 -- 3+3+1=7 x 2 = 14本題で使用する知識点:ツリーDP+反発原理+ルート変更
f[i]を定義してiをキーとする答えを表す
dis[i]はiから1までの距離を表す
num[i]はiを元とする子数点権の和を表し、totは総点権和である
現在dpからi番ノード,jはiの息子であり,wはこのときの辺権であると仮定する.
では、f[j]=f[i]+(tot-num[j])*w-num[j]*w;
親ノードから子ノードに移行すると、反発しにくくなりますので、図面を描いて理解することをお勧めします.
【コード】 #include
#include
#include
using namespace std;
const int N=100005,M=200005;
int n,t;
int c[N],first[N];
int v[M],w[M],next[M];
long long ans,tot,f[N],num[N],dis[N];
void add(int x,int y,int z)
{
t++;
next[t]=first[x];
first[x]=t;
v[t]=y;
w[t]=z;
}
void dfs(int x,int father)
{
int i,j;
num[x]+=c[x];
for(i=first[x];i;i=next[i])
{
j=v[i];
if(j==father)
continue;
dis[j]=dis[x]+w[i];
dfs(j,x);
num[x]+=num[j];
}
}
void dp(int x,int father)
{
int i,j;
for(i=first[x];i;i=next[i])
{
j=v[i];
if(j==father)
continue;
f[j]=f[x]+(tot-num[j])*w[i]-num[j]*w[i];
ans=min(ans,f[j]);
dp(j,x);
}
}
int main()
{
int x,y,z,i;
scanf("%d",&n);
for(i=1;i<=n;++i)
{
scanf("%d",&c[i]);
tot+=c[i];
}
for(i=1;i
#include
#include
#include
using namespace std;
const int N=100005,M=200005;
int n,t;
int c[N],first[N];
int v[M],w[M],next[M];
long long ans,tot,f[N],num[N],dis[N];
void add(int x,int y,int z)
{
t++;
next[t]=first[x];
first[x]=t;
v[t]=y;
w[t]=z;
}
void dfs(int x,int father)
{
int i,j;
num[x]+=c[x];
for(i=first[x];i;i=next[i])
{
j=v[i];
if(j==father)
continue;
dis[j]=dis[x]+w[i];
dfs(j,x);
num[x]+=num[j];
}
}
void dp(int x,int father)
{
int i,j;
for(i=first[x];i;i=next[i])
{
j=v[i];
if(j==father)
continue;
f[j]=f[x]+(tot-num[j])*w[i]-num[j]*w[i];
ans=min(ans,f[j]);
dp(j,x);
}
}
int main()
{
int x,y,z,i;
scanf("%d",&n);
for(i=1;i<=n;++i)
{
scanf("%d",&c[i]);
tot+=c[i];
}
for(i=1;i