UVA 10859 Placing Lampposts 樹形dp（水

UVA 10859 Placing Lampposts 樹形dp（水

題目鏈接：點擊打開鏈接

題意：

白書P70

思路：

簡單題，每個點分放或不放。

import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Scanner;

public class Main {
	int min(int a,int b){return a>b?b:a;}
	int max(int a,int b){return a>b?a:b;}
	static int N = 1005;
	static int M = 2005;
	ArrayList[] G = new ArrayList[N];
	int n, m;
	boolean[] vis = new boolean[N];
	int[][] dp = new int[N][2];
	int dfs(int u){
		vis[u] = true;
		int ans = 0;
		dp[u][0] = 0; dp[u][1] = M;
		//0表示不放
		for(int i = 0; i < G[u].size(); i++){
			int v = G[u].get(i); if(vis[v])continue;
			dfs(v);
			dp[u][1] += min(dp[v][0]+1, dp[v][1]);
			dp[u][0] += dp[v][1]+1;			
		}
		return min(dp[u][0], dp[u][1]);
	}
	void init(){
		n = cin.nextInt(); m = cin.nextInt();
		for(int i = 0; i < n; i++){
			vis[i] = false;
			G[i].clear();
		}
		for(int i = 1, u, v; i <= m; i++){
			u = cin.nextInt(); v = cin.nextInt();
			G[u].add(v); G[v].add(u);
		}
	}
	void work() {		
		for(int i = 0; i < N; i++)G[i] = new ArrayList();
		int T; T = cin.nextInt();
		while(T-->0){
			init();
			int ans = 0;
			for(int i = 0; i < n; i++)
				if(vis[i] == false)
					ans += dfs(i);
			out.printf("%d %d %d", ans/M, m-ans%M, ans%M); out.println();
		}
	}

	Main() {
		cin = new Scanner(System.in);
		out = new PrintWriter(System.out);
	}

	public static void main(String[] args) {
		Main e = new Main();
		e.work();
		out.close();
	}

	public Scanner cin;
	public static PrintWriter out;
}