added working NWERC11C
[the-user-spoj:the-user-spoj.git] / DRAGON.cpp
1 #include <iostream>
2 #include <vector>
3  
4 using namespace std;
5  
6 int n, m, k;
7  
8 struct node
9 {
10     vector<node*> children;
11     vector<int> ill;
12     vector<int> grB, grN; /* biggest and non-biggest */
13     int size;
14 };
15  
16 node *root;
17  
18 vector<vector<pair<int,int> > > adj;
19 vector<bool> visited;
20  
21 node *buildTree(int x)
22 {
23     if(visited[x])
24         return 0;
25     node *ret = new node;
26     visited[x] = true;
27     ret->size = 1;
28     for(int i = 0; i != adj[x].size(); ++i)
29     {
30         if(!visited[adj[x][i].first])
31         {
32             ret->children.push_back(buildTree(adj[x][i].first));
33             ret->ill.push_back(adj[x][i].second);
34             ++ret->size;
35         }
36     }
37     return ret;
38 }
39  
40 void checkPart(node *d, bool b, int sum, int rem, vector<int>& p)
41 {
42     if(rem < 0)
43         return;
44     if(p.size() == d->children.size())
45     {
46         if(rem == 0)
47         {
48             if(b)
49             {
50                 int val = 0;
51                 for(int i = 0; i != d->children.size(); ++i)
52                     val += min(d->children[i]->grB[p[i]] + d->ill[i], d->children[i]->grN[p[i]]);
53                 if(val < d->grB[sum+1])
54                     d->grB[sum+1] = val;
55             }
56             else
57             {
58                 int val = 0;
59                 for(int i = 0; i != d->children.size(); ++i)
60                     val += min(d->children[i]->grB[p[i]], d->children[i]->grN[p[i]] + d->ill[i]);
61                 if(val < d->grN[sum])
62                     d->grN[sum] = val;
63             }
64         }
65     }
66     else
67     {
68         p.push_back(0);
69         for(; p.back() <= rem; ++p.back())
70             checkPart(d, b, sum, rem - p.back(), p);
71         p.pop_back();
72     }
73 }
74  
75 void build2opts(node *d)
76 {
77     if(d->size == 1)
78     {
79         d->grB.resize(2);
80         d->grN.resize(2);
81         d->grB[0] = d->grN[1] = 1000000000;
82         d->grB[1] = d->grN[0] = 0;
83     }
84     else
85     {
86         d->grN.resize(d->size+1, 1000000000);
87         d->grB.resize(d->size+1, 1000000000);
88         for(int i = 0; i != d->children.size(); ++i)
89         {
90             build2opts(d->children[i]);
91         }
92         vector<int> p;
93         for(int i = 0; i != d->size; ++i)
94         {
95             checkPart(d, false, i, i, p);
96             checkPart(d, true, i, i, p);
97         }
98     }
99 }
100  
101 void check3Part(node *d, bool b, int sum, int rem, vector<int>& p)
102 {
103     if(rem < 0)
104     return;
105     if(p.size() == d->children.size())
106     {
107         if(rem == 0)
108         {
109             if(b)
110             {
111                 int val = 0;
112                 for(int i = 0; i != d->children.size(); ++i)
113                     val += min(d->children[i]->grB[p[i]] + d->ill[i], d->children[i]->grN[p[i]]);
114                 if(val < d->grB[sum+1])
115                     d->grB[sum+1] = val;
116             }
117             else
118             {
119                 int val = 0;
120                 for(int i = 0; i != d->children.size(); ++i)
121                     val += min(d->children[i]->grB[p[i]], d->children[i]->grN[p[i]]);
122                 if(val < d->grN[sum])
123                     d->grN[sum] = val;
124             }
125         }
126     }
127     else
128     {
129         p.push_back(0);
130         for(; p.back() <= rem; ++p.back())
131             check3Part(d, b, sum, rem - p.back(), p);
132         p.pop_back();
133     }
134 }
135  
136 void build3opts(node *d)
137 {
138     if(d->size == 1)
139     {
140         d->grB.resize(2);
141         d->grN.resize(2);
142         d->grB[0] = d->grN[1] = 1000000000;
143         d->grB[1] = d->grN[0] = 0;
144     }
145     else
146     {
147         d->grN.resize(d->size+1, 1000000000);
148         d->grB.resize(d->size+1, 1000000000);
149         for(int i = 0; i != d->children.size(); ++i)
150         {
151             build3opts(d->children[i]);
152         }
153         vector<int> p;
154         for(int i = 0; i != d->size; ++i)
155         {
156             check3Part(d, false, i, i, p);
157             check3Part(d, true, i, i, p);
158         }
159     }
160 }
161  
162 int main()
163 {
164     for(int _i_ = 0; _i_ != 10; ++_i_)
165     {
166     cin >> n >> m >> k;
167     if(n < m + k - 1)
168     {
169         cout << "-1" << endl;
170         for(int i = 1; i != n; ++i)
171         {
172             int x, y, ill;
173             cin >> x >> y >> ill;
174         }
175     }
176     else if(m == 1)
177     {
178         // Sum up illnesses
179         int sum = 0;
180         for(int i = 1; i != n; ++i)
181         {
182             int x, y, ill;
183             cin >> x >> y >> ill;
184             sum += ill;
185         }
186         cout << sum << endl;
187     }
188     else
189     {
190         adj.clear();
191         adj.resize(n);
192         root = 0;
193         visited.clear();
194         visited.resize(n, false);
195         for(int i = 1; i != n; ++i)
196         {
197             int x, y, ill;
198             cin >> x >> y >> ill;
199             --x;
200             --y;
201             adj[x].push_back(make_pair(y, ill));
202             adj[y].push_back(make_pair(x, ill));
203         }
204         root = buildTree(0);
205         if(m == 2)
206         {
207             build2opts(root);
208             cout << root->grB[k] << endl;
209         }
210         else
211         {
212             build3opts(root);
213             cout << root->grB[k] << endl;
214         }
215     }
216     }
217