题意：给你一个n个点m条边的无向无环图，在尽量少的节点上放灯，使得所有边都被照亮，每盏灯将照亮以他为一个端点的所有边，在灯的总数最小的前提下，被两盏灯同时照亮的边数应当尽量大。

分析：d(i,j)表示i的父节点放灯的状态为j（1表示放，0不放），以i为根的树的最小x值     x=Ma+c， a表示灯的总数， c表示只有一盏灯照亮此边， 题目转化成求x最小的问题， 把每个节点的x都求出来就好

代码：

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 using namespace std; 6 vector
          
           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
           
            =0 && !j) ans++;19 20 if(f<0 || j){21 int sum=0;22 for(k=0; k
            
             =0) sum++;25 if(ans>sum) ans=sum;26 }27 return ans;28 }29 int main(){30 #ifndef DEBUG31 freopen("in.txt", "r", stdin);32 #endif33 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
            
           
          
         
        
       
      

训练指南上的分析表示我是第二遍看才看懂。不过上午交题目发现uva这题是judging error1.  ⊙﹏⊙b汗