生活随笔
收集整理的這篇文章主要介紹了
NYOJ 674 善良的国王(树形背包DP)
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
善良的國王 時間限制：
1000 ?ms ?|? 內(nèi)存限制：
65535 ?KB 難度：
4
描述
傳說中有一個善良的國王 Good ，他為了不勞民傷財，每當建造一個城鎮(zhèn)的時候都只用一條路去連接，這樣就可以省很多的人力和物力，也就說如果有 n 個城鎮(zhèn)，那么只需要 n-1 條路就可以把所有的城鎮(zhèn)鏈接起來了（也就是一顆樹了）。但是不幸的事情發(fā)生了：有個一強大的帝國想要占領這個國家，但是由于國王 Good 的兵力不足，只能守護 m 個城鎮(zhèn)，所以經(jīng)過商量，國王 Good 只能從他的所有城鎮(zhèn)中選擇 m 個相鏈接的城市，并且把所有可以鏈接到這 m 個城鎮(zhèn)的道路都毀掉以阻止強大帝國的入侵。由于毀掉道路也需要花費一定的代價，所以為了經(jīng)可能的保存實力，國王 Good 想要毀掉最可能少的道路。現(xiàn)在請聰明的你幫助這位善良的國王 Good 吧。（ m 個城市可以是任意的，只要能連接在一起就可以。 輸入第一行一個t，代表有t組測試數(shù)據(jù)； 輸出每組輸出站一行。輸出格式“case #i: ans”，i代表第i組測試數(shù)據(jù)，ans即為最少要刪除的邊數(shù)。 樣例輸入 1
10 3
1 5
1 6
1 7
7 8
7 9
7 10
6 3
6 4
3 2 樣例輸出 case #1: 2 樹形動態(tài)規(guī)劃！ 同http://poj.org/problem?id=1947 AC碼： #include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
#define M 500
#define INF 9999999
vector<int> adj[M];
int f[M][M],vex[M];
int n,p,ans;
int min(int a,int b)
{return a>b?b:a;
}
int DP(int u)
{vex[u]=1;int i,j,k,v,len=adj[u].size();for(i=0;i<len;i++){v=adj[u][i];vex[u]+=DP(v);}f[u][1]=len;for(i=0;i<len;i++){v=adj[u][i];for(k=vex[u];k>=1;k--){for(j=1;(j<k)&&(j<=vex[v]);j++)f[u][k]=min(f[u][k],f[u][k-j]+f[v][j]-1);}}if(vex[u]>=p)ans=min(ans,f[u][p]+(u!=1));return vex[u];
}
int main()
{int T,i,a,b,count=1;scanf("%d",&T);while(T--){for(i=0;i<M;i++)adj[i].clear();scanf("%d%d",&n,&p);for(i=0;i<n-1;i++){scanf("%d%d",&a,&b);adj[a].push_back(b);}ans=INF;memset(f,INF,sizeof(f));DP(1);printf("case #%d: %d\n",count++,ans);}return 0;
}重建道路 時間限制： ?1000MS? 內(nèi)存限制： ?30000K總提交： ?8780? 接受日期： ?3954
描述
奶牛已在可怕的地震去年五月后重建農(nóng)夫約翰的農(nóng)場，與它的N谷倉（1 <= N <= 150，數(shù)字1 .. N）。牛沒有時間來重建任何額外的道路，所以現(xiàn)在正是從任何給定的谷倉去任何其他谷倉的一種方式。因此，養(yǎng)殖場運輸系統(tǒng)可以表示為一棵樹。?農(nóng)夫約翰想要知道另一地震可能造成的傷害。他想知道道路的最小數(shù)量，其破壞將隔離正好P（1 <= P <= N）從谷倉的其余部分谷倉的一個子樹。 輸入
*第1行：兩個整數(shù)N和P?*第2 .. N：N-1行，每 ??行有兩個整數(shù)I和J節(jié)點i節(jié)點J的父母在道路的樹。?產(chǎn)量
單線包含整數(shù)，表示需要對P個節(jié)點被孤立的子樹被破壞道路的最小數(shù)目。?樣例輸入
11 6
1 2
1 3
1 4
1 5
2 6
2 7
2 8
4 9
4 10
4 11
樣例輸出
2AC碼： #include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
#define M 500
#define INF 9999999
vector<int> adj[M];
int f[M][M],vex[M];
int n,p,ans;
int min(int a,int b)
{return a>b?b:a;
}
int DP(int u)
{vex[u]=1;int i,j,k,v,len=adj[u].size();for(i=0;i<len;i++){v=adj[u][i];vex[u]+=DP(v);}f[u][1]=len;for(i=0;i<len;i++){v=adj[u][i];for(k=vex[u];k>=1;k--){for(j=1;(j<k)&&(j<=vex[v]);j++)f[u][k]=min(f[u][k],f[u][k-j]+f[v][j]-1);}}if(vex[u]>=p)ans=min(ans,f[u][p]+(u!=1));return vex[u];
}
int main()
{int i,a,b;scanf("%d",&T);for(i=0;i<M;i++)adj[i].clear();scanf("%d%d",&n,&p);for(i=0;i<n-1;i++){scanf("%d%d",&a,&b);adj[a].push_back(b);}ans=INF;memset(f,INF,sizeof(f));DP(1);printf("%d\n",ans);return 0;
} 總結(jié)
以上是生活随笔 為你收集整理的NYOJ 674 善良的国王(树形背包DP) 的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔 網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔 推薦給好友。
