When I solve the problem I have collided with WA on test 11. I saw this test. In this test Q == 4. But it must be equal 2. I think when Marat Bakirov made this test hi take not into consideration what "Q denotes amount of branches that should be preserved" but not "removed"! Please correct this test. Incorrect test was deleted. Don't delete it. Correct this test. Because without this test problem mey be solve by wrong solution. I can offer you another one good test... If you want. Ok, I corrected this test. But it doesn't contain zeroes anymore. Here is my test: 7 3 1 2 1 1 3 39 2 4 40 2 5 40 3 6 39 3 7 39 It have another configuration than test 11. IS THE ANSWER 117? My program says 81 and i think it's correct but I got wa on test 11 :)) Edited by author 03.10.2004 03:35 Edited by author 03.10.2004 03:35 Edited by author 03.10.2004 03:35 U stupid ! The correct answer is 117 = 39+39+39 If n=q, you must output the amount of all the apples. Edited by author 06.04.2004 21:00 But I think everyone can notice this. Thank you very much!!!!!I just changed the edge '1' into '0' then I got ACCEPTED!!!!YOU ARE MY SECOND PARENTS! Oh,the great god!! What is the answer for this test? 4 1 1 2 1 2 3 0 2 4 0 Can i remove 0-branches from tree or not? Another test: 5 1 1 2 1 1 5 0 2 3 0 2 4 0 So can i remove 0-branches? Edited by author 27.10.2004 17:03 The idea of not-removing 0-branches arised because the test where incorrect. Thank you for explanation :) I don't solved 1018 yet. But i think that this problem can be solved with DP. Mine is crash(stack overflow),can you help me. Why my program is wrong,who can help me. This is my program: var a:array [0..100,0..100] of longint; s,b:array [0..100] of longint; used:array [1..100] of boolean; i,j,m,n,q,l,k,ans:longint; procedure cal(k:longint); var i,j:longint; begin used[k]:=true; for i:=1 to n do if (a[k,i]<>-1) and (not used[i]) then begin cal(i); b[k]:=b[k]+b[i]+1; s[k]:=s[k]+s[i]+a[k,i]; end; end; function del(k,m:longint):longint; var i,j,min,k1,k2,mink,ss,t:longint; begin if m=0 then begin del:=0; exit; end; used[k]:=true; if m=b[k] then del:=s[k] else begin k1:=0; k2:=0; for i:=1 to n do if (a[k,i]<>-1) and (not used[i]) then if k1=0 then k1:=i else k2:=i; min:=maxlongint; if m>b[k1] then min:=s[k1]+a[k,k1]+del(k2,m-b[k1]-1); if m>b[k2] then begin ss:=s[k2]+a[k,k2]+del(k1,m-b[k2]-1); if min>ss then min:=ss; end; for i:=m-b[k2] to b[k1] do begin ss:=del(k1,i); ss:=del(k2,m-i)+ss; if ss<min then min:=ss; end; del:=min; end; used[k]:=false; end; begin readln(n,q); for i:=0 to 100 do for j:=0 to 100 do a[i,j]:=-1; for k:=1 to n-1 do begin readln(i,j,l); a[i,j]:=l; a[j,i]:=l; end; fillchar(used,sizeof(used),false); cal(1); s[0]:=0; b[0]:=0; fillchar(used,sizeof(used),false); ans:=s[1]-del(1,n-q-1); writeln(ans); end. This is my program, can anybody tell me what is wrong? I did lot of tests and it seems to work, but I get WA. pleeeeaaaasssssseeeeeee, help!!!!! #include <iostream.h> #include <fstream.h> #ifndef ONLINE_JUDGE ifstream in("in.txt"); ofstream out("out.txt"); #else #define in cin #define out cout #endif int max(int a,int b) { return a>b?a:b; } class PreNode { public: PreNode():_size(0){} Add(int n) { _branch[_size++] = n; } int _size; int _branch[3]; }; class Node { public: Node() { _child[0] = NULL; _child[1] = NULL; } int _apples; int _maxBranches; int _maxApples[101]; Node *_child[2]; void GetVect(); void AddOneChild(Node *child) { _maxBranches = child->_maxBranches+1; for(int i = 0;i<=child->_maxBranches;i++) _maxApples[i+1] = child->_maxApples[i]+_apples; } }; PreNode preTree[101]; int apples[101][101]; Node tree[101]; int N,Q; void Make(int n,int p) { int hijo = 0; tree[n]._apples = apples[p][n]; for(int i = 0;i<preTree[n]._size;i++) { if(preTree[n]._branch[i] != p) { tree[n]._child[hijo++] = &tree[preTree[n]._branch[i]]; Make(preTree[n]._branch[i],n); } } } void Node::GetVect() { for(int h = 0;h<2;h++) { if(_child[h] != NULL) _child[h]->GetVect(); } _maxApples[0] = _apples; if(_child[0] == NULL && _child[1] == NULL) _maxBranches = 0; else { if(_child[0] != NULL && _child[1] == NULL) AddOneChild(_child[0]); else { if(_child[1] != NULL && _child[0] == NULL) AddOneChild(_child[1]); else { _maxBranches = 2+_child[0]->_maxBranches+_child[1]->_maxBranches; for(int i = 1 ; i<= _maxBranches;i++) { int maxi = 0;
if(_child[0]->_maxBranches >= i-1) maxi = max(maxi,_child[0]->_maxApples[i-1]+_apples);
if(_child[1]->_maxBranches >= i-1) maxi = max(maxi,_child[1]->_maxApples[i-1]+_apples); for(int j = 0;j<=i-2;j++) {
if(_child[0]->_maxBranches >= j && _child[0]->_maxBranches >= (i-2-j)) { maxi = max(maxi,_child[0]->_maxApples[j]+_child[1]->_maxApples[i-2- j]+_apples);
} } _maxApples[i] = maxi; } } } } } int main() { int i; in >> N; in >> Q; for(i=0;i<N-1;i++) { int f,t,m; in >> f >> t >> m; apples[f][t] = m; apples[t][f] = m; preTree[f].Add(t); preTree[t].Add(f); } tree[1]._apples = 0; Make(1,-1); tree[1].GetVect(); out << tree[1]._maxApples[Q]; return 0; } View problem statistics, and you'll see how many authors solved this problem. Don't you think that's enough to be sure the judge is ok. By the way, it is often very useful to view Discussions about the problem if you can't solve it. Good luck! Mail to dinhhongminh@yahoo.com No, you are right; the thing is that branches with 0 apples cannot be removed (and this is not written anywhere in the statement!!!) For example look at this test: 7 4 1 2 10 1 3 20 2 4 30 2 5 0 3 6 0 3 7 40 I am sure your output is 100, but the output should be 60 (due to the afore mentioned suggestion) Good luck. > No, you are right; the thing is that branches with 0 apples > cannot be removed (and this is not written anywhere in the > statement!!!) > > For example look at this test: > > 7 4 > 1 2 10 > 1 3 20 > 2 4 30 > 2 5 0 > 3 6 0 > 3 7 40 > > I am sure your output is 100, but the output should be 60 60=10+20+30+0 Branch(3,6) is removed, but it has 0 apples. How to explain? > (due to the afore mentioned suggestion) > > Good luck. > For example look at this test: >7 4 >1 2 10 >1 3 20 >2 4 30 >2 5 0 >3 6 0 >3 7 40 > >I am sure your output is 100, but the output should be 60 >(due to the afore mentioned suggestion) MY AC program output 100 how q can equal to n??? :( Though I know to Dp,but I really don't know the detail to record.Can anyone send me a Tree Dp program? Email:liuzhizhi@hotmail.com Thanks a lot. my email: yuwei110@yahoo.com.cn Please somebody explain me too, how to solve this problem. Thank's!!! my e-mail: r86acm@ukr.net Edited by author 11.08.2005 14:49 We can imagine that there's also a branch (or a trunk ^_^) below the root node, on which of course there are no apples at all. We denote by dp[x,y] the number of apples we can keep if we can keep y edges on the subtree with root x and the branch right below x. If y=0, then dp[x,0]=0. If y=1, then the branch right below x must be kept, so dp[x,1]=the number apples on the branch right below x. If y>1, then you can use enumeration to determine how many apples to keep on the two subtrees of x. Let a and b be the two children of x, then dp[x,y]=max{dp[x,1]+dp[a,i]+dp[b,y-1-i]}. The complexity is obviously O(n^3). Good luck! P.S. To Roman: I wonder why I can't send you e-mail from my Chinese mailbox. In the future you could send questions into this Japanese mailbox: akisame1988@yahoo.co.jp. At last I solved that problem! Edited by author 28.08.2005 02:42 830799 20:21:00 22 Apr 2005 nicushor 1018 C++ Accepted 0.001 190 KB :)) 5 2 1 2 1 1 3 0 3 4 0 3 5 1 Is '1' (I think) or '2' ??? I believe it's zero. There are two branches there with weight zero (ie/ they must be preserved), and you are asked to preserve two branches. Thus, anything with nonzero weight is hosed. I THINK THE ANSWER IS "1",BECAUSE WE SHOULD PRESERVE THEN BRANCHES 1 2 AND 1 3 7 1 1 2 1 1 3 1 2 6 0 2 7 0 3 4 0 3 5 0 What should be the answer 1 or 2? Thanks! So I should cut off zero-trees or only in case of when Q<number of zero-trees? Edited by author 18.04.2005 02:30 In this board people have been discussing about not removing 0-apple branches. Now it's completely RUMOUR! Just do everything as usual. If you get WA #11, it's because your algo is wrong. Greedy won't work. Use DP! Please,please,I am crazy I can give it to you, but I don't want put it here. Give your email or something etc. There's nothing really tricky about this problem, just do everything carefully. I got WA in the 11th data, and I've readen the discussion in the webboard, but them made me even more puzzled. What should I do with the branch which is 0 on earth? And what about when n=q? Would you please help me? And this is my program, I will be very thankful if you can tell me what's wrong with my program too. First, I use e and cost to record the nodes and numbers of apples. Then I build up a tree, delete the branch which is on the top and with the fewest apples. When k=n-1-m, the answer comes out. As follow: type aas=record bef:shortint; val:integer; nex:array[1..2]of byte; end; var i,j,k,t,n,m,a,b,c:integer; ans:longint; tree:array[1..100]of aas; e:array[1..100,1..3]of shortint; cost:array[1..100,1..3]of integer; num:array[1..100]of shortint; mark:array[1..100]of shortint; procedure find(aa:integer); var i2:integer; begin for i2:=1 to num[aa] do if mark[e[aa,i2]]=0 then begin inc(mark[aa]); tree[aa].nex[mark[aa]]:=e[aa,i2]; tree[e[aa,i2]].bef:=aa; tree[e[aa,i2]].val:=cost[aa,i2]; end; for i2:=1 to mark[aa] do find(tree[aa].nex[i2]); end; begin readln(n,m); fillchar(e,sizeof(e),0); fillchar(num,sizeof(num),0); fillchar(cost,sizeof(cost),0); ans:=0; for i:=1 to n-1 do begin read(a,b); readln(c); if c>0 then begin inc(num[a]); inc(num[b]); e[a,num[a]]:=b; e[b,num[b]]:=a; cost[a,num[a]]:=c; cost[b,num[b]]:=c; ans:=ans+c; end; end; fillchar(tree,sizeof(tree),0); fillchar(mark,sizeof(mark),0); find(1); k:=0; while k<n-1-m do begin c:=-1; for i:=1 to n do if (mark[i]=0)and((c=-1)or(c>tree[i].val)) then begin c:=tree[i].val; t:=i; end; inc(k); mark[t]:=-1; ans:=ans-c; dec(mark[tree[t].bef]); end; writeln(ans); end. 1) There are some branches which have 0 apples. Every such branch does NOT contain any non-zero branch - this test is impossible: 5 2 1 2 1 1 3 0 3 4 0 3 5 1, because branch 3 (with 0 apples) contains branch 5 (with 1 apple). 2) If there are some branches with 0 apples, we should IGNORE them and left from other branches (q - number of zero branches) ones. See also 1). For example, 7 5 1 2 1 1 3 0 3 4 0 3 5 0. 2 6 0 2 7 1 There are 4 zero branches. Ignore them - you'll get 2 branches. 1 2 1 2 7 1 From these branches you should left 5(q) - 4(number of zero branches) = 1 branch. Remove 2 7 1 and you'll get answer: 1. 3) All tests are correct now, but for this problem sometimes I had Wrong Answer, but it should be Runtime Error. Why is the answer to 2) 1? Why mustn't I remove the zero-apple branches? I THINK THE ANSWER TO TEST 1 IS "1",AND THE SECOND IS "2" Hi Can you Answer These Test Cases? I know these are too much but please help me :(( I can`t understand what programme should do with 0-apple branches :( Can you tell me What Should we do with branches contain 0 apple? Also If we should preserve or Cut them at first, then it might we get forced by q... For example if we have 4 0-apple and 1 non-0-apple branche then what should we do for q=2 or q=3 ? Best Regards Aidin_n7@hotmail.com Test #1: 6 2 1 2 10 1 4 30 2 3 0 4 5 0 4 6 100 Test #2: 6 2 1 2 10 1 4 30 2 3 0 4 5 0 4 6 0 Test #3: 7 4 1 2 10 2 4 10 2 5 0 1 3 0 3 6 10 3 7 10 Test #4: 5 3 1 2 10 2 3 0 2 4 0 1 5 0 Test #5: 5 2 1 2 10 2 3 0 2 4 0 1 5 0 Test #6: 7 1 1 2 0 1 5 0 2 3 10 2 4 10 5 6 10 5 7 10 Test #7: 7 2 1 2 0 1 5 0 2 3 10 2 4 10 5 6 10 5 7 10 Test #8: 7 3 1 2 0 1 5 0 2 3 10 2 4 10 5 6 10 5 7 10 With The Best Wishes Aidin_n7 PLEASE NOTICE "any biparous branch splits up to exactly two new branches. ",SO THEN N MUST BE ODD |
|