UVa10895 Placing Lampposts

 1 #include<iostream>
 2 #include<cstring>
 3 #include<vector>
 4 using namespace std;
 5 
 6 const int maxn = 1000+10;
 7 const int INF=1<<30;
 8 const int M=2000;
 9 
10 vector<int> G[maxn];
11 int d[maxn][2];
12 bool vis[maxn][2];
13 int n,m; 
14 
15 inline void init() {
16     for(int i=0;i<n;i++) G[i].clear();
17     memset(vis,false,sizeof(vis));
18     memset(d,0,sizeof(d)); 
19 }
20 
21 int dp(int i,int j,int fa) {
22     if(vis[i][j]) return d[i][j];
23     vis[i][j]=true;
24     int &ans=d[i][j];
25     
26     //无论j都可以在i上放置街灯 
27     ans=M;              //放置一个街灯的价值 
28     for(int k=0;k<G[i].size();k++) {
29         int v=G[i][k];
30         if(v!=fa) {
31             ans += dp(v,1,i);
32         }
33     }
34     if(!j && fa>=0) ans++;  //01
35     
36     if(j || fa<0)  //根也可以不放 
37     {
38         int sum=0;
39         for(int k=0;k<G[i].size();k++) {
40            int v=G[i][k];
41            if(v!=fa) {
42               sum += dp(v,0,i);
43            }
44         }
45         if(fa>=0) sum++;             //10 //根不算 
46         ans=min(ans,sum);  //两种情况取min 
47     }
48     
49     return ans;
50 }
51 
52 int main() {
53     ios::sync_with_stdio(false);
54     int T; cin>>T;
55     while(T--)
56     {
57         cin>>n>>m;
58         init();
59         int u,v;
60         for(int i=0;i<m;i++) {
61             cin>>u>>v;
62             G[u].push_back(v);
63             G[v].push_back(u);
64        }
65        int ans=0;
66        for(int i=0;i<n;i++) if(!vis[i][0]) {
67                ans += dp(i,0,-1);
68        }
69        cout<<ans/M<<" "<<m-ans%M<<" "<<ans%M<<"\n";
70     }
71     return 0;
72 }