Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

Input: Standard In Output: Standard Out Next Generation Contest 1  Time Limit: 2 seconds Problem D Placing Lampposts

As a part of the mission �Beautification of Dhaka City�, the government has decided to replace all the old lampposts with new expensive ones. Since the new ones are quite expensive and the budget is not up to the requirement, the government has decided to buy the minimum number of lampposts required to light the whole city.

Dhaka city can be modeled as an undirected graph with no cycles, multi-edges or loops. There are several roads and junctions. A lamppost can only be placed on junctions. These lampposts can emit light in all the directions, and that means a lamppost that is placed in a junction will light all the roads leading away from it.

The �Dhaka City Corporation� has given you the road map of Dhaka city. You are hired to find the minimum number of lampposts that will be required to light the whole city. These lampposts can then be placed on the required junctions to provide the service. There could be many combinations of placing these lampposts that will cover all the roads. In that case, you have to place them in such a way that the number of roads receiving light from two lampposts is maximized.

Input

There will be several cases in the input file. The first line of input will contain an integer T(T<=30) that will determine the number of test cases. Each case will start with two integers N(N<=1000) and M( M<N) that will indicate the number of junctions and roads respectively. The junctions are numbered from 0 to N-1. Each of the next M lines will contain two integers a and b, which implies there is a road from junction a to b,
( 0<= a,b < N ) and a != b. There is a blank line separating two consecutive input sets.

Output

For each line of input, there will be one line of output. Each output line will contain 3 integers, with one space separating two consecutive numbers. The first of these integers will indicate the minimum number of lampposts required to light the whole city. The second integer will be the number of roads that are receiving lights from two lampposts and the third integer will be the number of roads that are receiving light from only one lamppost.

Sample Input

2 4 3 0 1 1 2 2 3 5 4 0 1 0 2 0 3 0 4

Sample Output

2 1 2 1 0 4

---

Problem Setter: Sohel Hafiz.
Special thanks to Per Austrin.

---

題目描述：

這個國家要放置路燈於所有道路的路口處，而這個國家道路呈現樹形結構。
一個路燈放置於路口處時，相鄰的道路都會被照亮，希望能用最少路燈照亮所有道路。

在最少路燈的情況下，希望用兩個路燈照亮的道路越多越好。

分別輸出：最少路燈個數、兩個路燈的個數、剩餘使用一個路燈的個數。

題目解法：

樹狀圖上的最少點集覆蓋，將狀態劃分成 dp[i][2] // 分別表示這一點可選可不選。

dp[i][0] = 所有子節點要選的最少花費 dp[j][1]
dp[i][1] = 所有子節點 min(dp[j][0], dp[j][1])

然而要同時最大化兩個相鄰的放置個數，多記錄一個附加個數即可。

#include <stdio.h>
#include <vector>
using namespace std;
vector<int> g[1005];
int dp[1005][2], used[1005];
int dp2[1005][2];
void dfs(int nd) {
    int i, u;
    used[nd] = 1;
    dp[nd][0] = dp[nd][1] = 0; // dp[node][place_]
    dp2[nd][0] = dp2[nd][1] = 0;
    for(i = 0; i < g[nd].size(); i++) {
        u = g[nd][i];
        if(used[u])        continue;
        dfs(u);
        dp[nd][1] += min(dp[u][0], dp[u][1]);
        if(dp[u][0] != dp[u][1])
            dp2[nd][1] += dp[u][0] < dp[u][1] ? dp2[u][0] : (dp2[u][1]+1);
        else
            dp2[nd][1] += max(dp2[u][0], dp2[u][1]+1);
        dp[nd][0] += dp[u][1];
        dp2[nd][0] += dp2[u][1];
    }
    dp[nd][1]++;
    // printf("[%d] %d %d %d %d\n", nd, dp[nd][0], dp[nd][1], dp2[nd][0], dp2[nd][1]);
}
int main() {
    int testcase;
    int n, m;
    int i, j, k, x, y;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d %d", &n, &m);
        for(i = 0; i < n; i++)
            g[i].clear(), used[i] = 0;
        for(i = 0; i < m; i++) {
            scanf("%d %d", &x, &y);
            g[x].push_back(y);
            g[y].push_back(x);
        }
        int lamppost = 0, two = 0;
        for(i = 0; i < n; i++) {
            if(used[i] == 0) {
                dfs(i);
                lamppost += min(dp[i][0], dp[i][1]);
                if(dp[i][0] != dp[i][1])
                    two += dp[i][0] < dp[i][1] ? dp2[i][0] : dp2[i][1];
                else
                    two += max(dp2[i][0], dp2[i][1]);
            }
        }
        printf("%d %d %d\n", lamppost, two, m - two);
    }
    return 0;
}