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

題目描述

現(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

輸入

4
2 3 4 3
1 2
2 3
3 4

輸出

12

蒟蒻暴力枚舉-_-!

#include <bits/stdc++.h>using namespace std;const int MAXN=1e5+10;int a[MAXN];map<int, int >ma;set<int>se;int x[MAXN],y[MAXN];int main(){int n;scanf("%d",&n);for (int i = 1; i <=n ; ++i) {scanf("%d",&a[i]);se.insert(a[i]);}for (int i = 1; i <n ; ++i) {scanf("%d%d",&x[i],&y[i]);}long long ans=1e14,sum=0;set<int>::iterator it;for (it=se.begin(); it !=se.end() ; ++it) {sum=0;for (int j = 1; j <=n ; ++j) {if((*it)!=a[j]) sum+=((*it)+a[j]);}ans=min(sum,ans);}printf("%lld\n",ans);return 0;}

最后想說這都過了什么鬼，不會(huì)數(shù)據(jù)這么弱吧？？！?我只枚舉了最小的價(jià)值顏色的情況，唉，不管了不管了。

#include<bits/stdc++.h> using namespace std; int a[1000000],n,m,k=1,t,ans=0; int main() {scanf("%d",&n);for(int i=1;i<=n;++i)scanf("%d",&a[i]);sort(a+1,a+n+1);for(int i=2;i<=n;++i)if(a[i]!=a[1])ans+=a[i]+a[1];printf("%d",ans);return 0; }

總結(jié)

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

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