「BZOJ1369」[Baltic2003] Gem
Description
给出一棵树，要求你为树上的结点标上权值，权值可以是任意的正整数 唯一的限制条件是相临的两个结点不能标上相同的权值，要求一种方案，使得整棵树的总价值最小。
Input
先给出一个数字N,代表树上有N个点,N<=10000 下面N-1行,代表两个点相连
Output
最小的总权值
Sample Input
10
7 5
1 2
1 7
8 9
4 1
9 7
5 6
10 2
9 3
7 5
1 2
1 7
8 9
4 1
9 7
5 6
10 2
9 3
Sample Output
14
题解
WJMZBMR：
这题首先是不能用奇偶层染色的办法来做的，我构造出了至少需要1-3的反例，同时用数学归纳法可以证明对于任意n，都有树不能用1-n达到最优解（提示：使用大量叶子节点逼迫某节点染2。。）。。
但是我的构造法弄出来的反例的大小至少是指数增长的，所以我感觉对于N<=10000，10种颜色足够了。。更精确的测试表明3种就OK了(!!!!!我可以构造出1000个以内的需要4种颜色的反例啊囧。。这个数据好弱啊。。)。。然后就是简单的树形DP。。。比赛的时候很明显直接DP就可以了。。证明不重要(*^__^*) 嘻嘻……
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 |
#include<iostream> #include<cstring> #include<cstdio> #include<cstdlib> #include<cmath> #include<algorithm> #include<vector> #define ll long long #define inf 1000000000 using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,cnt; int last[10005],f[10005][25]; struct edge{ int to,next; }e[20005]; void insert(int u,int v) { e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt; e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt; } void dp(int x,int fa) { for(int j=1;j<=20;j++) f[x][j]=j; for(int i=last[x];i;i=e[i].next) if(e[i].to!=fa) dp(e[i].to,x); for(int j=1;j<=20;j++) { for(int i=last[x];i;i=e[i].next) if(e[i].to!=fa) { int mn=inf; for(int k=1;k<=20;k++) if(j!=k)mn=min(mn,f[e[i].to][k]); f[x][j]+=mn; } } } int main() { n=read(); for(int i=1;i<n;i++) { int u=read(),v=read(); insert(u,v); } dp(1,0); int ans=inf; for(int i=1;i<=20;i++) ans=min(ans,f[1][i]); printf("%d\n",ans); return 0; } |
Subscribe
计数器 9864016
OI 课件=>
OI 课件=>