題目鏈接:點擊打開鏈接
題意:
白書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; }