题意：给你一个n个点m条边的无向无环图，在尽量少的节点上放灯，使得所有边都被照亮，每盏灯将照亮以他为一个端点的所有边，在灯的总数最小的前提下，被两盏灯同时照亮的边数应当尽量大。
分析：d(i,j)表示i的父节点放灯的状态为j（1表示放，0不放），以i为根的树的最小x值 x=Ma+c， a表示灯的总数， c表示只有一盏灯照亮此边， 题目转化成求x最小的问题， 把每个节点的x都求出来就好
代码：
View Code
1 #include <stdio.h> 2 #include <iostream> 3 #include <string.h> 4 #include <vector> 5 using namespace std; 6 vector<int>adj[1010]; 7 int vis[1010][2], d[1010][2], n, m; 8 #define DEBUG 9 int dp(int i, int j, int f){ 10 if(vis[i][j]) return d[i][j]; 11 vis[i][j]=1; 12 int& ans=d[i][j]; 13 int k; 14 15 ans=2000; 16 for(k=0; k<adj[i].size(); k++) 17 if(adj[i][k]!=f) ans+=dp(adj[i][k], 1, i); 18 if(f>=0 && !j) ans++; 19 20 if(f<0 || j){ 21 int sum=0; 22 for(k=0; k<adj[i].size(); k++) 23 if(adj[i][k]!=f) sum+=dp(adj[i][k], 0, i); 24 if(f>=0) sum++; 25 if(ans>sum) ans=sum; 26 } 27 return ans; 28 } 29 int main(){ 30 #ifndef DEBUG 31 freopen("in.txt", "r", stdin); 32 #endif 33 int T, a, b; 34 scanf("%d", &T); 35 while(T--){ 36 scanf("%d%d", &n, &m); 37 int i; 38 for(i=0; i<n; i++) adj[i].clear(); 39 for(i=0; i<m; i++){ 40 scanf("%d%d", &a, &b); 41 adj[a].push_back(b); 42 adj[b].push_back(a); 43 } 44 memset(vis, 0, sizeof(vis)); 45 int ans=0; 46 for(i=0; i<n; i++) 47 if(!vis[i][0]) ans+=dp(i, 0, -1); 48 printf("%d %d %d\n", ans/2000, m-ans%2000, ans%2000); 49 } 50 return 0; 51 }
训练指南上的分析表示我是第二遍看才看懂。不过上午交题目发现uva这题是judging error1. ⊙﹏⊙b汗
