poj1947.doc

792K16MSG+1111B#include#include#include#define inf 0x007fffffusing namespace std;int f151151;vectorTree151;int n,p;void DFS(int root) int i,j,k; for(i=0;iTreeroot.size();i+) DFS(Treerooti); froot1=Treeroot.size(); for (i=0;i=1;k-) if (frootkinf) for (j=1;j=p-1;j+) if (fTreerootijinf) frootk+j=min(frootk+fTreerootij-1,frootk+j); return ;int DP() int i,j; for(i=1;i= n; i+) for (j=0;j=n;j+) fij=inf; DFS(1); int res=inf; for(i=2;i=n;i+) res=min(res,fip+1); res=min(res,f1p); return res;int main() scanf(%d%d,&n,&p); int i,a,b; for(i=1;in;i+) scanf(%d%d,&a,&b); Treea.push_back(b); printf(%dn,DP(); return 0;fij代表以i为根(包含i)，共j个节点需要切断的路的数量fij+k=min(fij+k,fi.sontk)(t为i的孩子)*820K47MSG+1252B题意：Farmer John农场里的粮仓之间通过一条双向路径连接，若两个粮仓之间的道路组成一个无向树。现给定粮仓之间道路的连接方式，问至少摧毁几条路，使得剩下的粮仓组成的子树恰好有P个粮仓。思路：树型DP。首先需要有一个感性认识，只有这个P是不大于粮仓数的一个正整数，这个子树是肯定存在的。将某个叶子剪掉，子树的粮仓数目就减少了1，如此将某个非叶子节点的所有叶子剪掉之后，这个节点就变成了叶子节点，如此递归下去可减少子树的节点数。由此可知，这个摧毁的道路数，最大值就是N-P。当然，最小值的做法就是像样例那样，将整个子树与总树的连接边剪掉，这样就能一次过减少几个节点。这里就需要树型DP，通过遍历树，来“分配”这些剪掉的边，将其分至各子树中。通过DP i j 表示以i 为父节点，得出节点数为j 的子树，至少需要在该子树内摧毁几条边。首先，对于叶子节点，自然就是0了。而对于非叶子节点，在dfs遍历其所有节点后，对于每个子节点x，dpij=mindpik+dpxj-k,0=k=j，实质就是枚举j分到x的子树的分法。最后需要注意，有可能这个子树的根不是原来的根，所以对于其他子树，最后是需要+1，表示摧毁该子树根与其父节点的连边。#include #include#define MAX 152#define INF 0x3ffffffusing namespace std;int dpMAXMAX;int sonMAX, blaMAX, root, n, p;bool hfMAX;void dfs(int s) int i, j, k, temp; for(i = 0; i = 0; i-) temp = dpsi+1; for(j = 0; j = i; j+) if(dpki-j + dpsj temp) temp = dpki-j + dpsj; dpsi = temp; k = blak; int slove(int root) dfs(root); int i, ans; ans = dprootp; for(i = 1; i = n; i+) if(dpip n p) memset(son, 0, sizeof(son); for(i = 1; i s t; blat = sons; sons = t; hft = true; for(i = 1; i = n; i+) if(!hfi) root = i; cout slove(root) endl; return 0;*876K0MSG+958B#include#include#include#includeusing namespace std;int num155,flag155,son155155,step155155,big=10000000,n,m,start;void dsf(int v) int i,j,k; if(v!=start) stepv1=numv+1; else stepv1=numv; for(i=0;i=1;j-) if(stepvjbig) for(k=1;k+j=m;k+) stepvk+j=min(stepvk+j,stepvj+stepsonvik-2); int main() while(scanf(%d%d,&n,&m)!=EOF) memset(num,0,sizeof(num); memset(flag,0,sizeof(flag); int i,a,b,j; for(i=1;in;i+) scanf(%d%d,&a,&b); flagb=1; sonanuma+=b; for(i=1;i=150;i+) for(j=1;j=150;j+) stepij=big; for(i=1;i=n;i+) if(flagi=0) start=i; dsf(i); break; int res=big; for(i=1;i=n;i+) if(stepimres) res=stepim; printf(%dn,res); 注：stepij表示得到一棵以i为根j个节点的树要stepij步； numa表示a的子节点的个数；sonij表示i的第j个子节点；*868K0MSG+936B设根节点为root,它的一个子结点为v，则我们可以选择切掉它们之间的边，或不切，这就是子问题的决策。我用frootp表示在以root为根的树，获取p个节点所要切的最少边数。1 如果切，则frootp=frootp+12 如果不切，那我们就可以保留v为根的子树的某些节点（起码保留v，因为不切嘛），这时我们就可以枚举子树保留k个节点，而在整树在找p-k个节点，这些也是子问题。以上所有子问题取最少即为答案。边界条件是非常重要，froot1=0,因为刚才已经说了，如果不切root到它父亲节点间的边，则至少会保留该子树的一个节点（即root自己），所以为0.#include#include#includeusing namespace std;const int maxn=151;const int inf=1e8;int flagmaxn,n,p,root,fmaxnmaxn,gmaxnmaxn,nummaxn;int vismaxn,ans;void init()memset(num,0,sizeof(num);void add(int a,int b)ganuma+=b;void dp(int root)for(int i=0;i=p;i+)frooti=inf;froot1=0;int i,j,k,tmp,son;for(i=0;i0;j-)tmp=inf;for(k=1;kj;k+)tmp=min(tmp,frootk+fsonj-k);frootj=min(frootj+1,tmp);int main()int a,b;while(scanf(%d%d,&n,&p)!=EOF)init();for(int i=0;in-1;i+)scanf(%d%d,&a,&b);add(a,b);flagb=1;dp(1);ans=f1p;for(int i=2;i=n;i+)if(fip+1ans)ans=fip+1;printf(%dn,ans);*820K47MSG+1351B#include #include#define MAX 152#define INF 0x3ffffffusing namespace std;/*dpsi:记录s结点，要得到一棵j个节点的子树去掉的最少边数考虑其儿子k 1）如果不去掉k子树，则dpsi = min(dpsj+dpki-j) 0 = j = i 2）如果去掉k子树，则dpsi = dpsi+1总的为dpsi = min (min(dpsj+dpki-j) , dpsi+1 )*/int dpMAXMAX;int sonMAX, blaMAX, root, n, p;/soni:记录i结点的儿子，blai:记录i结点的兄弟bool hfMAX;/hfi:i结点是否有父亲void dfs(int s) int i, j, k, temp; for(i = 0; i = 0; i-) temp = dpsi+1; for(j = 0; j = i; j+) if(dpki-j + dpsj temp) temp = dpki-j + dpsj; dpsi = temp; k = blak; int slove(int root) dfs(root); int i, ans; ans = dprootp; for(i = 1; i = n; i+) if(dpip n p) memset(son, 0, sizeof(son); for(i = 1; i s t; blat = sons; sons = t; hft = true; for(i = 1; i = n; i+) if(!hfi) root = i; cout slove(root) endl; return 0;*896K32MSG+1782B#include#include#include#include#includeusing namespace std;#define M 160#define INF 130vectorGM;int n,p;int dpMM;/dpij表示以i为根节点保留j个节点需删除的最小边数int fMM;/fij表示前i个子节点void Update(int root)int i,j,k;int s=Groot.size();dproot1=s; /如果保留的节点为1，那只需剩下root节点，需s次把root的儿子全部删去if(s=0) return;/找到叶子节点了for(i=0;is;i+)for(j=1;j=p;j+)fij=INF;f01=1;/对于第0号儿子节点，要保留1个节点，只需把根节点与0号节点之间的边删除，即保留根节点for(i=2;i=p;i+)f0i=dpGroot0i-1; /因为有root节点，所以是i-1，即f0i等于root的0号节点保留i-1个节点最少所需删除的边数for(i=1;is;i+)for(j=1;j=p;j+)for(k=1;k(fi-1k+dpGrootij-k)fij=fi-1k+dpGrootij-k;if(fi-1j!=INF)/不用i号儿子节点。花1次代价将之删除if(fijfi-1j+1)fij=fi-1j+1;for(i=1;i=p;i+)dprooti=fs-1i;/把f数组的值转移给dp/printf(*%d %dn,i,fs-1i);void dfs(int root)int i;for(i=0;iGroot.size();i+)dfs(Grooti);Update(root);return;i