| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 2787 | Accepted: 1488 |
Description
众所周知，我们可以通过直角坐标系把平面上的任何一个点P用一个有序数对(x, y)来唯一表示，如果x, y都是整数，我们就把点P称为整点，否则点P称为非整点。我们把平面上所有整点构成的集合记为W。 定义1 两个整点P1(x1, y1), P2(x2, y2)，若|x1-x2| + |y1-y2| = 1，则称P1, P2相邻，记作P1~P2，否则称P1, P2不相邻。 定义 2 设点集S是W的一个有限子集，即S = {P1, P2,..., Pn}(n >= 1)，其中Pi(1 <= i <= n)属于W，我们把S称为整点集。 定义 3 设S是一个整点集，若点R, T属于S，且存在一个有限的点序列Q1, Q2, ?, Qk满足: 1. Qi属于S（1 <= i <= k）; 2. Q1 = R, Qk = T; 3. Qi~Qi + 1(1 <= i <= k-1)，即Qi与Qi + 1相邻; 4. 对于任何1 <= i < j <= k有Qi ≠ Qj; 我们则称点R与点T在整点集S上连通，把点序列Q1, Q2,..., Qk称为整点集S中连接点R与点T的一条道路。 定义4 若整点集V满足：对于V中的任何两个整点，V中有且仅有一条连接这两点的道路，则V称为单整点集。 定义5 对于平面上的每一个整点，我们可以赋予它一个整数，作为该点的权，于是我们把一个整点集中所有点的权的总和称为该整点集的权和。 我们希望对于给定的一个单整点集V，求出一个V的最优连通子集B，满足： 1. B是V的子集 2. 对于B中的任何两个整点，在B中连通； 3. B是满足条件(1)和(2)的所有整点集中权和最大的。Input
第1行是一个整数N（2 <= N <= 1000），表示单整点集V中点的个数； 以下N行中，第i行(1 <= i <= N)有三个整数，Xi, Yi, Ci依次表示第i个点的横坐标，纵坐标和权。同一行相邻两数之间用一个空格分隔。-10^6 <= Xi, Yi <= 10^6；-100 <= Ci <= 100。Output
仅一个整数，表示所求最优连通集的权和。Sample Input
50 0 -20 1 11 0 10 -1 1-1 0 1Sample Output
2题意：其实就是一个求无向树的所有子树和的最大值
先附上两个网上讲的比较好的题解：
题解一：
就是每个子树的根节点（包括叶子节点）记录dp[i][0]与dp[i][1]，前一个表示不包含根的最大值，后一个表示包含根的最大值。
那么我们可以得到对于dp[i][0]，必然是所有分支中dp[child][0]与dp[child][1]中大于0的最大值的累加（因为不包含树根，所
以在根节点上的连通性不用保证）,dp[i][1]必然是所有分支中dp[child][1]中大于0的最大值的累加再加上该树根本身的值（因为
要保证连通性）。最后只要比较dp[start][0]与dp[start][1]，输出较大的一个即可。
题解二：
给定的是一颗树，根据题意，我们可以从任意一个节点出发，必能访问到其他所有节点，那么dp的起点可以在任意一个节点，因为是无向树。
我们从该起点出发，对以此点为根的树的每个分支进行搜索，采用树的后续遍历法则，对于每个子树来说，dp值首先加上根节点（因为要保证连
通性，所以返回值中必须包含根节点的值，即使为负数也必须加上）先对每个分支dp，然后看分支dp的返回值是不是正数，如果是正数，
那么我们就把该分支的返回值加入到该树中去。就是每个子树的根节点（包括叶子节点）记录dp[i][0]与dp[i][1]，前一个表示不包含根
的最大值，后一个表示包含根的最大值。那么我们可以得到对于dp[i][0]，必然是所有分支中dp[child][0]与dp[child][1]中大于0的
最大值的累加（因为不包含树根，所以在根节点上的连通性不用保证）,dp[i][1]必然是所有分支中dp[child][1]中大于0的最大值的累
加再加上该树根本身的值（因为要保证连通性）。最后只要比较dp[root][0]与dp[root][1]，输出较大。
总结：自己做树，图，之类的题特别少，对这些也不是很了解，之前做的树的题，几乎都是有向树，找到根节点，然后只能往下找的那种，这个就是我第一次接触的“无向树”，一个节点是一个节点的父亲同时也是一个节点的孩子。从任意一个节点开始，可以访问到任何其他节点。访问每个节点的时候，只需要保证在访问这个点的孩子的时候，不碰到他的父亲即可，再说这个转移方程式，dp[][1]好说，以这个点为根节点的树，在他所有儿子为根节点的子树中，肯定要找权值和>0的加上，要不就把这个点的权值变小了，对节点并没有要求，只需要加上对其有贡献的就行，跟哪个最大字段和有点像，只加正的，如果一个正的也没有，就什么也不加，这样让这个节点总的权值减少的最少（不减少）。并且dp[][1]他的儿子必须选，也就是选得儿子也必须是dp[][1]否则，就不连通了，有根节点没有儿子。。。
再说dp[][0]，这个代表这个节点不选的，他是从dp[][0],dp[][1]中选一个，因为这个节点不选，所以不必考虑连通性，注意下如果选得是dp[][1]，这个节点下面都是dp[][1]，不必害怕有空档，让他不连通。。
不知道数据水还是怎么，去掉dp[0][]也对。。。按理说应该要+上这个，不要这个根的节点。。。
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <vector>#include <cmath>using namespace std;const int maxn = 1e3+5;const int INF = 2e6;int dp[maxn][3];int x[maxn], y[maxn], val[maxn], book[maxn];vector<int> p[maxn];void dfs(int u){ dp[u][0] = 0; dp[u][1] = val[u]; book[u] = 1; for(int i = 0; i < p[u].size(); i++) { int to = p[u][i]; if(book[to]) continue; dfs(to); dp[u][1] += max(dp[to][1],0); //这里是 += 只要对她有贡献的全都+上 dp[u][0] = max(dp[u][0], max(dp[to][1], dp[to][0])); //因为这个点不选，所以只能选一个最大的，作为一个去掉根节点子树，因为这个dp数组初始化是0，所以直接这样就行}int main(){ int n; while(~scanf("%d", &n)) { memset(book, 0, sizeof(book)); memset(dp, 0, sizeof(dp)); for(int i = 1; i <= n; i++) p[i].clear(); for(int i = 1; i <= n; i++) { scanf("%d%d%d", &x[i], &y[i], &val[i]); } for(int i = 1; i <= n; i++) for(int j = i+1; j <= n; j++) { if(abs(x[i]-x[j])+abs(y[i]-y[j]) == 1) { p[i].push_back(j); //无向树，一定要两次 p[j].push_back(i); } } dfs(1); PRintf("%d/n", max(dp[1][0], dp[1][1])); } return 0;}还有一中就是dp是一维的。。只要他儿子>0就+上就行，在dfs过程更新每个节点的最大值#include <iostream> #include <cstdio> #include <cstdlib> #include <vector> #include <cmath> #define INF 1E9 using namespace std; vector<int> near[1001]; int X[1001],Y[1001]; int value[1001]; int n,ans=-INF; int now[1001]; int ok[1001]; int dfs(int v) { ok[v]=1; now[v]=value[v]; for(int i=0;i<near[v].size();i++) { int u=near[v][i]; if(ok[u])continue; dfs(u); now[v]+=(now[u]>0?now[u]:0); ans=max(ans,now[v]); } } int main() { scanf("%d",&n); int i,j; for(i=0;i<n;i++) { scanf("%d%d%d",&X[i],&Y[i],&value[i]); } for(i=0;i<n;i++) { for(j=0;j<n;j++) { if(i==j)continue; if(fabs(X[i]-X[j])+fabs(Y[i]-Y[j])>1)continue; near[i].push_back(j); near[j].push_back(i); } } dfs(0); printf("%d/n",ans); }
新闻热点
疑难解答
