鏈接：https://www.nowcoder.com/acm/contest/133/A
來源：牛客網(wǎng)
?

時(shí)間限制：C/C++ 1秒，其他語言2秒
空間限制：C/C++ 262144K，其他語言524288K
64bit IO Format: %lld

題目描述

現(xiàn)在有一棵被Samsara-Karma染了k種顏色的樹，每種顏色有著不同的價(jià)值

Applese覺得Samsara-Karma染的太難看了，于是打算把整棵樹重新染成同一種顏色

但是，由于一些奧妙重重的原因，每一次染色Applese可以選擇兩個(gè)有邊相連的點(diǎn)，將其中一個(gè)染成另一個(gè)的顏色。而進(jìn)行一次這樣的操作需要付出兩種顏色價(jià)值和的代價(jià)

現(xiàn)在，Applese的錢要用來買書(game)，所以他想要最小化代價(jià)

?

輸入描述:

輸入包括若干行 第一行包括一個(gè)數(shù)n，表示這棵樹有n個(gè)節(jié)點(diǎn) 第二行包括n個(gè)數(shù)，第i個(gè)數(shù)表示第i個(gè)節(jié)點(diǎn)的顏色coli **注意：一個(gè)顏色的標(biāo)號(hào)即價(jià)值

接下來的n - 1行，每行包括兩個(gè)數(shù)u, v，表示u節(jié)點(diǎn)與v節(jié)點(diǎn)之間有一條無向邊

n ≤ 100000, 1 ≤ coli ≤ 1e9，數(shù)據(jù)保證是一棵樹

輸出描述:

輸出包括一行 第一行包括一個(gè)數(shù)，表示最小代價(jià)

示例1

輸入

復(fù)制

4 2 3 4 3 1 2 2 3 3 4

輸出

復(fù)制

12

題意：》》》》

思路：其實(shí)和圖沒有太大的關(guān)系，只要統(tǒng)計(jì)顏色的種類，然后記錄圖染成每一種顏色用的代價(jià)，比較最小值輸出即可；

有兩種復(fù)雜度的代碼：

O(n^2)

#include<bits/stdc++.h> #define ll long long using namespace std; set<ll> l; set<ll>::iterator it; ll a[100005]; int main() {int n,v,c;cin>>n;for(int i=0;i<n;i++){scanf("%lld",&a[i]);l.insert(a[i]);}for(int i=0;i<n-1;i++)scanf("%lld %lld",&c,&v);long long ans=0;long long ams;for( it=l.begin();it!=l.end();it++){ans=0;for(int j=0;j<n;j++){if(*it!=a[j])ans+=a[j]+*it;else continue;}ams=min(ans,ams);}printf("%lld\n",ams);return 0; }

O(n)

#include<bits/stdc++.h> using namespace std; #define LL long longconst int MAXN = 1e5+10; const int INF = 0x3f3f3f3f; int n,u,v; int a[MAXN]; map<int,LL>mp,cost; int main(){while(scanf("%d",&n)!=EOF){LL sum = 0;for(int i=1;i<=n;i++){scanf("%d",&a[i]);mp[a[i]] += a[i];sum += a[i];}for(int i=1;i<n;i++){scanf("%d%d",&u,&v);}LL ans = 1LL<<60;map<int,LL>::iterator it;for(it=mp.begin();it!=mp.end();it++){ans = min(ans,sum - it->second + (n - it->second / it->first) * it->first);}cout<<ans<<endl;}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的Wannfly挑战赛20 A 染色的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。