題干：

Bob enjoys playing computer games, especially strategic games, but sometimes he cannot find the solution fast enough and then he is very sad. Now he has the following problem. He must defend a medieval city, the roads of which form a tree. He has to put the minimum number of soldiers on the nodes so that they can observe all the edges. Can you help him??

Your program should find the minimum number of soldiers that Bob has to put for a given tree.?

For example for the tree:?

the solution is one soldier ( at the node 1).

Input

The input contains several data sets in text format. Each data set represents a tree with the following description:?

• ?
• the number of nodes?
• the description of each node in the following format?
  node_identifier:(number_of_roads) node_identifier1?node_identifier2?... node_identifiernumber_of_roads?
  or?
  node_identifier:(0)?

The node identifiers are integer numbers between 0 and n-1, for n nodes (0 < n <= 1500);the number_of_roads in each line of input will no more than 10. Every edge appears only once in the input data.

Output

The output should be printed on the standard output. For each given input data set, print one integer number in a single line that gives the result (the minimum number of soldiers). An example is given in the following:

Sample Input

4 0:(1) 1 1:(2) 2 3 2:(0) 3:(0) 5 3:(3) 1 4 2 1:(1) 0 2:(0) 0:(0) 4:(0)

Sample Output

1 2

題目大意：

給出一個n個結點的樹,要求選出其中的一些頂點,使得對于樹中的每條邊(u, v),u和v至少有一個被選中. 請給出選中頂點數最少的方案.?

解題報告：

? ? 樹形圖的最小點覆蓋、、、直接跑匈牙利也可以過，大概是數據水了。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair #define fi first #define se second using namespace std; const int MAX = 2e5 + 5; int n; vector<int> vv[1505]; int dp[1505][2]; void dfs(int cur,int root) {int up = vv[cur].size(); // if(up == 1) {dp[cur][1]=1; // }for(int i = 0; i<up; i++) {int v = vv[cur][i];if(v == root) continue;dfs(v,cur);dp[cur][0] += dp[v][1];dp[cur][1] += min(dp[v][0],dp[v][1]);} } int main() {int x,num,y;while(~scanf("%d",&n)) {for(int i = 0; i<=n; i++) vv[i].clear();memset(dp,0,sizeof dp);for(int i = 1; i<=n; i++) {scanf("%d:(%d)",&x,&num);if(num == 0) continue;while(num--) {scanf("%d",&y);vv[x].pb(y);vv[y].pb(x);}}//dfs(vv[0][0],0);dfs(0,0);printf("%d\n",min(dp[0][0],dp[0][1]));}return 0 ;}

總結：

? ?幾個要注意的地方：

? ? ? ?首先別忘了是從0號點開始編號！！所以vv的初始化要從i=0開始！

? ? ? 第二那個if num==0? 可以不加、

? ? ? 第三這題雙向圖單向圖都可以做，一般習慣雙向圖然后dfs中加一個參數root就行了。。。而且main函數調用的時候不需要管root傳什么值（實在不行給個-1，，反正用不到這個），，直接(0,0)或者(1,1)都行。。。（當然最好還是傳(0,0)。因為這題是恰好了沒有單個頂點的情況，萬一有這種特例，那就WA了啊）

?

AC代碼2：（分析一下）

#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #define PI acos(-1.0)using namespace std; typedef long long ll; const int maxn = 1500+7, INF = 0x3f3f3f3f; int n, cur, ans; int f[maxn]; bool vis[maxn]; int next[maxn]; struct edge {int v, bef; } e[maxn*2]; void add(int x, int y) {e[cur].v = y;e[cur].bef = next[x];next[x] = cur++; } void init() {memset(next, -1, sizeof(int)*(n+1));cur = 1;for(int j = 0; j < n; ++j) {int u, v, cnt;scanf("%d:(%d)", &u, &cnt);for(int i = 0; i < cnt; ++i) {scanf("%d", &v);add(u, v);add(v, u);//a[u].push_back(v);//a[v].push_back(u);}}memset(f, -1, sizeof(int)*(n+1)); } bool dfs(int id) {for(int i = next[id]; i != -1; i = e[i].bef) {if(!vis[e[i].v]) {vis[e[i].v] = 1;if(f[e[i].v] == -1 || dfs(f[e[i].v])) {f[id] = e[i].v;f[e[i].v] = id;return true;}}}return false; } int main() {while(scanf("%d", &n) != EOF && n) {init();ans = 0;for(int i = 0; i < n; ++i) {if(f[i] == -1) {memset(vis, false, sizeof(bool)*(n+1));if(dfs(i)) ans++;}}printf("%d\n", ans);}return 0; }

我們來分析一下這份冗長的代碼（網上找的，上面這份是原始代碼）首先他用f數組（也就是nxt）數組同時記錄了兩個的值（與這個題不同【HDU - 1281 】棋盤游戲，那個題的AC代碼2 是 用兩個數組分別記錄左側的值和右側的值的，，而這個題的這種解法是都存在同一個數組f中）所以我們要想直接輸出ans而不是ans/2的話，就需要判斷一步? ：（? ?if(f[i] != -1)則進入循環 ）。如果去掉這個if的話，最后還是要輸出ans/2的，，因為相當于還是每個點都搜了一遍，，原來的匹配會被覆蓋的，，所以加這個if的話，會減少一半的復雜度（其實也沒多少、。、還是那個數量級）（其實我也不太懂，，，不加這個if，，為什么不會wa？？我感覺會WA的啊）其實這題跑匈牙利的話直接建雙向邊上模板就好了。。。就是個拆點

?

下面是個完整的匈牙利代碼：（改天可以自己再寫一遍）

其實之所以可以跑二分匹配，是因為它其實是個二分圖。（所以可以“拆點”(偽拆點)求最大匹配！！！）想想為啥是個二分圖。

#include <stdio.h> #include <string.h> #include <vector> #include <algorithm> #define maxn 210 const int INF=0x3f3f3f3f; using namespace std; int n; vector<int>g[1510]; int used[1510],match[1510]; int dfs(int x) {int i;for(i=0;i<g[x].size();i++){int k=g[x][i];if(!used[k]){used[k]=1;if(match[k]==-1||dfs(match[k])){match[k]=x;return 1;}}}return 0; } int main () {int i,j,a,b,k;while(scanf("%d",&n)!=EOF){int ans=0;memset(g,0,sizeof(g));for(i=1;i<=n;i++){scanf("%d:(%d)",&a,&k);while(k--){scanf("%d",&b);g[a].push_back(b);g[b].push_back(a);}}memset(match,-1,sizeof(match));for(i=0;i<n;i++){memset(used,0,sizeof(used));if(dfs(i))ans++;}printf("%d\n",ans/2);}return 0; }

附：

https://blog.csdn.net/Ema1997/article/details/51870453

不知道這個代碼為什么找第一個flag=0的點進行dfs。、。。感覺隨便找個點dfs就可以啊，所以0號點就好了啊。

?

一個看不懂的代碼：大概是找增廣路的方法。匹配變成不匹配。

總結

以上是生活随笔為你收集整理的【POJ - 1463】Strategic game （树上最小点覆盖，树形dp）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。