POJ1463

概述每条边至少要有一个端点有士兵，求最少需要士兵数。 因此，如果子树的根节点不放士兵，那么其所有的直接儿子节点必须都放上士兵。 状态转移方程： sol[root][0] += sol[G[root][i]][1]; sol[root][1] += min(sol[G[root][i]][0], sol[G[root][i]][1]); /**/#include <cstdio>#include <

每条边至少要有一个端点有士兵，求最少需要士兵数。
因此，如果子树的根节点不放士兵，那么其所有的直接儿子节点必须都放上士兵。
状态转移方程：
sol[root][0] += sol[G[root][i]][1];
sol[root][1] += min(sol[G[root][i]][0],sol[G[root][i]][1]);

/**/#include <cstdio>#include <cstring>#include <cmath>#include <cctype>#include <iostream>#include <algorithm>#include <map>#include <set>#include <vector>#include <string>#include <stack>#include <queue>typedef long long LL;typedef unsigned long long ulL;using namespace std;//bool Sqrt(LL n) { return (LL)sqrt(n) * sqrt(n) == n; }const double PI = acos(-1.0),ESP = 1e-10;const LL INF = 99999999999999;const int inf = 999999999,N = 1500 + 24;int sol[N][2],fa[N],n;vector<int> G[N]; //用邻接表存储树voID dfs(int root) {    for(int i = 0; i < G[root].size(); i++) dfs(G[root][i]);    for(int i = 0; i < G[root].size(); i++) {        sol[root][0] += sol[G[root][i]][1];        sol[root][1] += min(sol[G[root][i]][0],sol[G[root][i]][1]);    }}int main(){    //freopen("in.txt","r",stdin);    //freopen("out.txt","w",stdout);    while(~scanf("%d",&n)) {        for(int i = 0; i < n; i++) {            G[i].clear();            sol[i][1] = 1; sol[i][0] = 0;            fa[i] = -1;        }        for(int i = 0; i < n; i++) {            int root,node,cnt;            scanf("%d:(%d)",&root,&cnt);            for(int i = 0; i < cnt; i++) {                scanf("%d",&node);                G[root].push_back(node);                fa[node] = root;            }        }        int root = 1;        while(fa[root] != -1) root = fa[root]; //这样来找根节点        dfs(root);        printf("%d\n",min(sol[root][0],sol[root][1]));    }    return 0;}/*    input:    output:    modeling:    methods:    complexity:    summary:*/

这道题与POJ2342类似，都是在直接父子关系的节点之间。

总结

以上是内存溢出为你收集整理的POJ1463全部内容，希望文章能够帮你解决POJ1463所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。