12 条题解

  • 2
    @ 2016-10-20 21:13:20
    program vjiosP1553;
    
    type
            point=^node;
            node=record
                    data,w:longint;
                    next:point;
            end;
    var
            n,s:longint;
            head:array[1..500050] of point;
            list:array[1..500050] of longint;
            lists:longint;
            visit,flag:array[1..5000050] of boolean;
            pre,pred,sum,f:array[1..500050] of longint;
            key,max:longint;
            ans:longint;
            queue,qt:array[1..500050] of longint;
            qhead,qtail:longint;
    
    function maxf(a,b:longint):longint;
    begin
            if a>b then
                    exit(a)
            else
                    exit(b);
    end;
    
    function minf(a,b:longint):longint;
    begin
            if a<b then
                    exit(a)
            else
                    exit(b);
    end;
    
    procedure initdfs;
    begin
            fillchar(visit,sizeof(visit),0);
            fillchar(pre,sizeof(pre),0);
            fillchar(pred,sizeof(pred),0);
            max:=0;
    end;
    
    procedure initq;
    begin
            qhead:=1;
            qtail:=1;
    end;
    
    procedure put(data,id:longint);
    var
            tmp:longint;
    begin
            tmp:=qhead;
            while queue[tmp]>data do
                    inc(tmp);
            queue[tmp]:=data;
            qt[tmp]:=id;
            qtail:=tmp;
    end;
    
    function find(l:longint):longint;
    begin
            while qt[qhead]<l do inc(qhead);
            exit(queue[qhead]);
    end;
    
    procedure initp(x:longint);
    begin
            head[x]:=nil;
    end;
    
    procedure insert(u,v,w:longint);
    var
            p:point;
    begin
            new(p);
            p^.data:=v;
            p^.w:=w;
            p^.next:=head[u];
            head[u]:=p;
    end;
    
    procedure inputdata;
    var
            i:longint;
            u,v,w:longint;
    begin
            fillchar(flag,sizeof(flag),false);
            readln(n,s);
            for i:=1 to n do
                    initp(i);
            for i:=1 to n-1 do
            begin
                    readln(u,v,w);
                    insert(u,v,w);
                    insert(v,u,w);
            end;
    end;
    
    procedure dfs(id,dist:longint);
    var
            now:point;
            nowid,nowd:longint;
    begin
            visit[id]:=true;
            now:=head[id];
            while now<>nil do
            begin
                    nowid:=now^.data;
                    nowd:=dist+now^.w;
                    if (not visit[nowid]) and (not flag[nowid]) then
                    begin
                            pre[nowid]:=id;
                            pred[nowid]:=now^.w;
                            if nowd>max then
                            begin
                                    key:=nowid;
                                    max:=nowd;
                            end;
                            dfs(nowid,nowd);
                    end;
                    now:=now^.next;
            end;
    end;
    
    procedure work1;
    var
            now,t:longint;
            i:longint;
    begin
            initdfs;
            pre[1]:=1;
            dfs(1,0);
            initdfs;
            pre[key]:=key;
            pred[key]:=0;
            dfs(key,0);
    
            fillchar(sum,sizeof(sum),0);
            lists:=1;
            list[1]:=key;
            t:=pred[key];
            now:=pre[key];
            while pre[now]<>now do
            begin
                    inc(lists);
                    list[lists]:=now;
                    sum[lists]:=sum[lists-1]+t;
                    t:=pred[now];
                    now:=pre[now];
            end;
            inc(lists);
            list[lists]:=now;
            sum[lists]:=sum[lists-1]+t;
            for i:=1 to lists do
                    flag[list[i]]:=true;
    end;
    
    procedure work2;
    var
            i:longint;
    begin
            for i:=1 to lists do
            begin
                    initdfs;
                    dfs(list[i],0);
                    f[i]:=max;
            end;
    end;
    
    procedure work3;
    var
            tl,tr:longint;
            tot,tmp:longint;
    begin
            ans:=200000000; initq;
            tl:=1;  tr:=1;  put(f[1],1);
            repeat
                    while (sum[tr+1]-sum[tl]<=s) and (tr<lists) do
                    begin
                            inc(tr);
                            put(f[tr],tr);
                    end;
                    tot:=0;
                    tot:=maxf(sum[tl],find(tl));
                    tot:=maxf(tot,sum[lists]-sum[tr]);
                    ans:=minf(ans,tot);
    
                    inc(tl);
                     if tr>=lists then break;
            until tr=lists;
    end;
    
    begin
            inputdata;
            work1;
            work2;
            work3;
            writeln(ans);
    end.
    
  • 0
    @ 2009-07-11 23:55:24

    Accepted 有效得分:100 有效耗时:3200ms

    数据果然弱:

    1.DP的时候原本直接递归,但是这样就栈溢出,于是限制递归层数不超过10000,这样有一些点可能就错了,但是没错...

    2.懒得写RMQ了,直接枚举的...

    1可能为2节约了时间,才卡时通过的.

  • 0
    @ 2009-08-23 16:45:15

    BFS+DFS+单调队列

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 41ms

    ├ 测试数据 05:答案正确... 56ms

    ├ 测试数据 06:答案正确... 9ms

    ├ 测试数据 07:答案正确... 244ms

    ├ 测试数据 08:答案正确... 212ms

    ├ 测试数据 09:答案正确... 666ms

    ├ 测试数据 10:答案正确... 556ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:1784ms

  • 0
    @ 2009-07-01 19:44:50

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 25ms

    ├ 测试数据 04:答案正确... 103ms

    ├ 测试数据 05:答案正确... 103ms

    ├ 测试数据 06:答案正确... 134ms

    ├ 测试数据 07:答案正确... 338ms

    ├ 测试数据 08:答案正确... 338ms

    ├ 测试数据 09:答案正确... 806ms

    ├ 测试数据 10:答案正确... 791ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:2638ms

    O(N)算法,常数巨大。

    多亏了PUPPY。

  • 0
    @ 2009-06-30 22:01:12

    我是神牛!大家来膜拜我!!!!!

    • @ 2013-04-03 23:22:59

      哇!**拽****爆**了,i ac too!

  • 0
    @ 2009-06-30 17:33:22

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 9ms

    ├ 测试数据 06:答案正确... 9ms

    ├ 测试数据 07:答案正确... 103ms

    ├ 测试数据 08:答案正确... 119ms

    ├ 测试数据 09:答案正确... 462ms

    ├ 测试数据 10:答案正确... 416ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:1118ms

    就400000还这样,输入输出常数很大

  • 0
    @ 2009-06-14 14:54:15

    我也是O(n)的,可怎么会这样......

    难道是因为用了class?

    ├ 测试数据 01:答案正确... 25ms

    ├ 测试数据 02:答案正确... 56ms

    ├ 测试数据 03:答案正确... 134ms

    ├ 测试数据 04:答案正确... 244ms

    ├ 测试数据 05:答案正确... 244ms

    ├ 测试数据 06:答案正确... 228ms

    ├ 测试数据 07:答案正确... 431ms

    ├ 测试数据 08:答案正确... 447ms

    ├ 测试数据 09:答案正确... 884ms

    ├ 测试数据 10:答案正确... 931ms

  • 0
    @ 2009-06-13 22:13:52

    O(n)吧

  • 0
    @ 2009-06-27 20:45:28

    写O(n)算法就能AC……

    还有这题可能卡C++的读入……

    还有s

  • -1
    @ 2009-08-15 16:50:40

    哈哈哈哈哈哈哈啊哈哈哈哈啊哈哈

  • -1
    @ 2009-07-22 12:35:07

    汗,第一次交成朴素的了……

  • -1
    @ 2009-07-13 20:26:51

    bfs + 单调队列

  • 1

信息

ID
1553
难度
7
分类
动态规划 | 树形DP 点击显示
标签
(无)
递交数
436
已通过
87
通过率
20%
被复制
2
上传者