HDU 1054 - Strategic Game

HDU 1054 - Strategic Game

Problem Description

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.

The input file 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_identifier
or
node_identifier:(0)

The node identifiers are integer numbers between 0 and n-1, for n nodes (0 < n <= 1500). Every edge appears only once in the input data.

For example for the tree:



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

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 table:

 

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

http://blog.csdn.net/u014141559/article/details/38125679

题目分析：

用最少的士兵将所有的道路都监控起来

这题是最小顶点覆盖，可以用二分匹配，但是今天学树形DP，走起~~

基础模板：

1、建图，用邻接表

2、dfs，遍历整个图，直到叶子，然后子问题一层一层往上合并成整个问题

状态转移 dp[i][0]  i节点不放士兵所需要的最少方案数,dp[i][1]  i节点放士兵的最少方案数

每个节点都有两个状态，放士兵或者不放士兵

1.如果该节点不放士兵，那么它的所有子节点必须放

2.如果该节点放士兵，那么它的子节点有两种决策，放或不放，去最小的

http://blog.csdn.net/u012841845/article/details/18450551
如果当前节点站士兵，则以它为父亲的子节点（就是它的邻接点）就可以站或者不站，取
两种情况中消耗最小的。 dp[i][1]+=min(dp[v][1],dp[v][0])
如果当前节点不站士兵，则它的邻接点不能被守卫到，故它的邻接点必须要有士兵。
dp[i][0]+=dp[v][1];
v是i的邻接点。
跟那个, poj 2342 Anniversary party(简单树形dp+dfs)真是像极了。。。
我就是根据那个来写的。。。
加边的时候当无向边处理。所以不要忘了add(b,a)!!

1. struct edge  
2. {  
3.     int to;  
4.     int next;  
5. }w[10010];  
6. bool vis[1510];  
7. int dp[1510][2],head[1510],tot;  
8. void add(int x,int y)  
9. {  
10.     w[tot].to=y;  
11.     w[tot].next=head[x];  
12.     head[x]=tot++;  
13. }  
14. void dfs(int r)  
15. {  
16.     vis[r]=true;  
17.     int v,i;  
18.     for(i=head[r];i;i=w[i].next)  
19.     {  
20.         v=w[i].to;  
21.         if(!vis[v])  
22.         {  
23.             dfs(v);  
24.             dp[r][0]+=dp[v][1];  
25.             dp[r][1]+=min(dp[v][1],dp[v][0]);  
26.         }  
27.     }  
28. }  
29. int main()  
30. {  
31.     int n,m,a,b;  
32.     while(scanf("%d",&n)!=EOF)  
33.     {  
34.         memset(vis,0,sizeof(vis));  
35.         memset(head,0,sizeof(head));  
36.         tot=1;  
37.         for(int i=0;i<n;i++)  
38.         {  
39.             dp[i][0]=0;  
40.             dp[i][1]=1;  
41.         }  
42.         for(int i=0;i<n;i++)  
43.         {  
44.             scanf("%d:(%d)",&a,&m);  
45.             for(int i=0;i<m;i++)  
46.             {  
47.                 scanf("%d",&b);  
48.                 add(a,b);  
49.                 add(b,a);  
50.             }  
51.         }  
52.         dfs(0);  
53.         printf("%d\n",min(dp[0][0],dp[0][1]));  
54.     }  
55.     return 0;  
56. }  

只在hdu过的了的vector版本~~~~~= =
vector<int> t[1510];
hdu 1054 Strategic Game （最小顶点覆盖+稀疏图）
最小顶点覆盖，一直超时，后来才意识到图是一个稀疏图，用矩阵存图果断超时。用邻接表轻松AC！

1. int mark[N],n,t;  
2. int link[N],head[N];  
3. struct node  
4. {  
5.     int u,v,next;  
6. }g[N*10];  
7. void add(int u,int v)  
8. {  
9.     g[t].u=u;  
10.     g[t].v=v;  
11.     g[t].next=head[u];  
12.     head[u]=t++;  
13. }  
14. int find(int u)  
15. {  
16.     int i,v;  
17.     for(i=head[u];i!=-1;i=g[i].next)  
18.     {  
19.         v=g[i].v;  
20.         if(!mark[v])  
21.         {  
22.             mark[v]=1;  
23.             if(link[v]==-1||find(link[v]))  
24.             {  
25.                 link[v]=u;  
26.                 return 1;  
27.             }  
28.         }  
29.     }  
30.     return 0;  
31. }  
32. int main()  
33. {  
34.     int i,u,q,v;  
35.     while(scanf("%d",&n)!=-1)  
36.     {  
37.         memset(head,-1,sizeof(head));  
38.         memset(link,-1,sizeof(link));  
39.         t=0;  
40.         for(i=0;i<n;i++)  
41.         {  
42.             scanf("%d:(%d)",&u,&q);  
43.             while(q--)  
44.             {  
45.                 scanf("%d",&v);  
46.                 add(u,v);  
47.                 add(v,u);  //建立的双向边，所以答案最后除以二  
48.             }  
49.         }  
50.         int ans=0;  
51.         for(i=0;i<n;i++)  
52.         {  
53.             memset(mark,0,sizeof(mark));  
54.             ans+=find(i);  
55.         }  
56.         printf("%d\n",ans/2);  
57.     }  
58.     return 0;  
59. }  

Also check code at http://panyanyany.iteye.com/blog/1240748