四川省城乡与建设厅网站,中国十大it培训机构排名,wordpress关闭导航,国际网站怎么注册免费的Cell Phone Network
题意:
每个牧场的电塔可以覆盖与该牧场相邻的电塔#xff0c;为了让所有牛都可以打电话#xff0c;求建的电塔的最小数量
题解#xff1a;
树的最小支配集 dp[x][0]#xff1a;选点i#xff0c;并且以点i为根的子树都被覆盖 dp[x][1]#xff1a;不…Cell Phone Network
题意:
每个牧场的电塔可以覆盖与该牧场相邻的电塔为了让所有牛都可以打电话求建的电塔的最小数量
题解
树的最小支配集 dp[x][0]选点i并且以点i为根的子树都被覆盖 dp[x][1]不选ii被其儿子覆盖 dp[x][2]不选点ii被其父亲覆盖此时儿子可选可不选 转移方程 dp[i][0]1∑min(dp[u][0],dp[u][1],dp[u][2])(u是i的儿子) 被儿子被自己被父亲覆盖
dp[i][2]∑(dp[u][1],dp[u][0]) i被父亲覆盖u是i的儿子u 可选可不选但是u肯定不会被i所覆盖
对于dp[i][1]情况i的儿子们中必须有一个取dp[u][0] if(i没有子节点)dp[i][1]INF else dp[i][1]∑mindp[u][0],dp[u][1]inc 对于inc if(∑mindp[u][0],dp[u][1]中包含某个dp[u][0])inc0 else incmin(dp[u][0]-dp[u][1]) 选与不选 若dp[u][0]dp[u][1]即所有子节点都不染色所以我们必须强迫一个子节点染色且保证最优解dp[root][1]min;
代码:
#includebits/stdc.h
#define debug(a,b) printf(%s %d\n,a,b)
typedef long long ll;
using namespace std;inline int read(){int s0,w1;char chgetchar();while(ch0||ch9){if(ch-)w-1;chgetchar();}while(ch0ch9) ss*10ch-0,chgetchar();//s(s3)(s1)(ch^48);return s*w;
}
const int maxn1e49;
const int INF1e99;
vectorintvec[maxn];
/*
dp[u][0]表示节点u建站点最少数目
dp[u][1]表示节点u的子节点有建u不建
dp[u][2]表示节点u能够被父亲节点覆盖u不建
*/
int vis[maxn];
int dp[maxn][5];
void dfs(int u)
{dp[u][0]1;dp[u][1]dp[u][2]0;vis[u]1;int MinINF;bool f1;for(int i0;ivec[u].size();i){int vvec[u][i];if(vis[v])continue;dfs(v);dp[u][0]min(dp[v][0],min(dp[v][1],dp[v][2]));dp[u][2]min(dp[v][0],dp[v][1]);if(dp[v][0]dp[v][1]){f0;dp[u][1]dp[v][0];}else {dp[u][1]dp[v][1];Minmin(dp[v][0]-dp[v][1],Min);}}if(f)dp[u][1]Min;}
int main()
{int n;cinn;for(int i1;in;i){int u,v;cinuv;vec[u].push_back(v);vec[v].push_back(u);}dfs(1);printf(%d\n,min(dp[1][0],dp[1][1]));return 0;
}
