时间限制: 1Sec 内存限制: 128MB 提交: 5 解决: 2
7 6 1 2 1 3 2 4 2 5 3 6 7 3
3
#include<iostream> #include<cstdio> #include<cstring> #include<vector> #include<algorithm> using namespace std; const int maxn = 501; int n,m,sum=1; bool vis[maxn]; vector<int> box[maxn]; void dfs(int from) { if(box[from].size()==1) return ; int Max = -0x3FFFFFFF,u=-1; for(int i=0;i<box[from].size();i++) { int to = box[from][i]; int size = box[to].size(); if(vis[to]==false && size>Max) { Max = size; u = to; } } vis[u]=true; for(int i=0;i<box[from].size();i++) { int to = box[from][i]; if(!vis[to]) { vis[to]=true; sum++; dfs(to); } } } int main(void) { freopen("D:\\input.txt","r",stdin); cin >> n >> m; for(int i=0;i<m;i++) { int u,v; cin >> u >> v; box[u].push_back(v); box[v].push_back(u); } vis[1]=true; dfs(1); cout << sum; return 0; }
一开始打算使用贪心算法，就是在当前的传染点上，找到所有与她相邻并且没有访问过的点，然后将这些点中含有边最多的那一个点给删除掉。
但是出错了，因为自己也没有验证这样做的结果是最优决策。经过自己检查之后，发现这样不是正确的决策方法，存在一些情况使用这个方法不能正确的得到结果。
于是想到用动态规划的方法，使用num[x]记录当x被传染时候，最少传染人数，但是发现忽略了条件每次只能减去一个边。代码如下：
#include<iostream> #include<cstdio> #include<cstring> #include<vector> #include<algorithm> using namespace std; const int maxn = 501; int n,m,sum=1; vector<int> box[maxn]; int num[maxn]; int dfs(int from) { if(num[from]!=0) return num[from]; //如果这个点已经计算过了，直接返回传染这个人之后，最小人数。 num[from]=1; if(box[from].size()==1) return num[from]; //叶子 int sum = 0; for(int i=0;i<box[from].size();i++) { int to = box[from][i]; if(to!=from) { sum+=dfs(to); } } int Max = -0x3FFFFFFF; for(int i=0;i<box[from].size();i++) { int to = box[from][i]; if(to!=from) { if(num[to]>Max) Max = num[to]; } } num[from]+=sum-Max; return num[from]; } void print() { for(int i=1;i<=n;i++) { printf("num[%d]=%d\n",i,num[i]); } } int main(void) { freopen("D:\\input.txt","r",stdin); cin >> n >> m; for(int i=0;i<m;i++) { int u,v; cin >> u >> v; box[u].push_back(v); box[v].push_back(u); } dfs(1); print(); cout << num[1]; return 0; }
最后发现是使用DFS暴力建树，然后使用DFS暴力搜索加剪枝操作。
#include<iostream> #include<cstdio> #include<cstring> #include<vector> #include<algorithm> using namespace std; const int maxn = 501; int n,m,Min=0x3FFFFFFF; vector<int> box[maxn]; //box[x]保存和x相连的所有的点的编号 int depth[maxn],ill[maxn]; //deptch[x]记录结点x在树中的层次 ，ill[x]记录是否生病，默认为0，表示没有生病 void build_tree(int u,int pre) //求出结点编号为u的结点的深度.pre为u结点的父节点. { depth[u]=depth[pre]+1; for(int i=0;i<box[u].size();i++) { int v = box[u][i]; if(v!=pre) build_tree(v,u); } } void dfs(int dep,int sum) { if(sum > Min) return ; //剪枝 bool bottom = true; //记录已经到了最后一层了. for(int i=1;i<=n;i++) { if(depth[i]==dep && ill[i]) { for(int j=0;j<box[i].size();j++) { int p = box[i][j]; if(depth[p]==dep+1) { bottom = false; //表示dep不是最深的一层. ill[p]=1; sum++; } } } } sum--;//在同一层中，减去一个分支. for(int i=1;i<=n;i++) { if(depth[i]==dep+1 && ill[i]) { //注意回溯 ill[i]=0; dfs(dep+1,sum); ill[i]=1; } } sum++; for(int i=1;i<=n;i++) { if(depth[i]==dep && ill[i]) { for(int j=0;j<box[i].size();j++) { int p = box[i][j]; if(depth[p]==dep+1) { ill[p]=0; sum--; } } } } if(bottom) Min=min(Min,sum); } int main(void) { //freopen("D:\\input.txt","r",stdin); cin >> n >> m; for(int i=0;i<m;i++) { int u,v; cin >> u >> v; box[u].push_back(v); box[v].push_back(u); } build_tree(1,0); ill[1]=1; dfs(1,1); cout << Min ; return 0; }
原文：https://www.cnblogs.com/zuimeiyujianni/p/9394740.html
