UVA10859 Placing Lampposts

题目描述

给定一个n个点m条边的无向无环图，在尽量少的节点上放灯，使得所有边都与灯相邻（被灯照亮）。

在灯的总数最小的前提下，被两盏灯同时照亮的边数应该尽可能大。

输入格式

第一行输入T*,为数据组数。

每组数据第一行输入n,m，分别为该组数据中图的点数和边数。

以下m行，输入各边的两端点 u,v。

输入格式

输出共T行。

对每组数据，一行输出三个数，最小灯数、被两盏灯同时照亮的边数、只被一盏灯照亮的边数。

输入输出样例

输入 #1

1
2
3
4
5
6
7
8
9
10
2
4 3
0 1
1 2
2 3
5 4
0 1
0 2
0 3
0 4

输出 #1

1
2
2 1 2
1 0 4

一般来说，如果有两个需要优化的量 $v_1$ 和 $v_2$ ,首先要求满足 $v_1$最小，在 $v_1$相同的情况下 $v_2$最小，则可以把二者组合成一个量 $M \times v_1+ v_2$,其中 $M$ 是一个比 “ $v_2$的最大理论值和 $v_2$的最小理论值之差” 还要大的数。这样只要两个解的 $v_1$不同， 则不管 $v_2$相差多少，都是 $v_1$起决定性作用。（抄自白书）

本题 $d[i][1/0]$ 表示以$i$ 为根节点的子树，放与不放灯时的最小 $x$ ( $x= M \times v_1+ v_2$)值 ,

如果父节点放灯，才允许子节点不放灯（要放灯最少所以选择不放） ，$d[i][1] = \sum d[k][0]$ $k$ 是 $i$ 的子节点，如果 $i$ 不是根 结果 +1 。

如果父节点不放灯，子节点必须放灯 ，$d[i][0] = \sum d[k][1] + M$ , 此时 如果 $i$ 不是根 结果 +1 。

因为 $i$ 和其父节点只有一盏灯照亮。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
const int MAX=1000+10;
int t,n,m,u,v,vis[MAX][2],ans,d[MAX][2];
vi g[MAX];
int dp(int i,int j,int fa){
	if(vis[i][j]) return d[i][j];
	vis[i][j]=1;
	int &ans = d[i][j];// ans,d[i][j] "绑定"
	ans =2000;
	fi(k,0,g[i].size())	
		if(g[i][k]!=fa)
			ans += dp(g[i][k],1,i);
	if(!j && fa>=0) ans ++;
	if(j||fa<0){
		int sum=0;
		fi(k,0,g[i].size())
			if(g[i][k]!=fa)
				sum+=dp(g[i][k],0,i);
		if(fa>=0) sum++;
		ans = min(ans,sum);
	}
	return ans ;
}
int main(){
	freopen("in","r",stdin);
	sf(t);
	while(t--){
		sf(n);sf(m);
		fi(i,0,n) g[i].clear();
		fi(i,0,m){
			sf(u);sf(v);
			g[u].pb(v);g[v].pb(u);
		}
		mem(vis,0);
		ans =0;
		fi(i,0,n)
			if(!vis[i][0])
				ans += dp(i,0,-1);
		printf("%d %d %d\n",ans/2000,m-ans%2000,ans%2000);
	}
	return 0;
}