| 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); }
新聞熱點
疑難解答
