树形DP Codeforces Round #135 (Div. 2) D. Choosing Capital for Treeland

题目传送门

 /*
题意:求一个点为根节点,使得到其他所有点的距离最短,是有向边,反向的距离+1
树形DP:首先假设1为根节点,自下而上计算dp[1](根节点到其他点的距离),然后再从1开始,自上而下计算dp[v],
此时可以从上个节点的信息递推出来
*/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
using namespace std; const int MAXN = 2e5 + ;
const int INF = 0x3f3f3f3f;
struct Edge {
int v, w;
};
vector<Edge> G[MAXN];
int dp[MAXN];
bool vis[MAXN];
int n, res; void DFS(int u) {
vis[u] = true;
for (int i=; i<G[u].size (); ++i) {
int v = G[u][i].v, w = G[u][i].w;
if (vis[v]) continue;
DFS (v);
res += w;
}
} void DFS2(int u) {
vis[u] = true;
for (int i=; i<G[u].size (); ++i) {
int v = G[u][i].v, w = G[u][i].w;
if (vis[v]) continue;
if (w == ) dp[v] = dp[u] + ;
else dp[v] = dp[u] - ;
DFS2 (v);
}
} void work(void) {
memset (vis, false, sizeof (vis));
memset (dp, , sizeof (dp)); res = ; DFS (); dp[] = res;
memset (vis, false, sizeof (vis));
DFS2 (); int mn = INF, p = ;
for (int i=; i<=n; ++i) {
if (mn >= dp[i]) {
mn = dp[i]; p = i;
}
}
printf ("%d\n", mn);
for (int i=; i<=n; ++i) {
if (i == p) {
printf ("%d\n", i); break;
}
if (dp[i] == mn) printf ("%d ", i);
}
} int main(void) { //Codeforces Round #135 (Div. 2) D. Choosing Capital for Treeland
// freopen ("A.in", "r", stdin); while (scanf ("%d", &n) == ) {
for (int i=; i<=n; ++i) G[i].clear ();
for (int i=; i<=n-; ++i) {
int u, v; scanf ("%d%d", &u, &v);
G[u].push_back ((Edge) {v, });
G[v].push_back ((Edge) {u, });
} work ();
} return ;
}
上一篇:IE的debug工具对程序进行debug跟踪JS代码


下一篇:Linux系统下sendmail发送邮件失败的问题