/ Vijos / 题库 / 旅行 /

题解

57 条题解

  • 1
    @ 2018-11-01 19:45:21
    //一道二进制枚举的题目,二进制的每一位表示一个团队选或者不选,用前缀和维护每一站的人数,所有站人数均不超则该方案可行
    //总复杂度O(n*2^m)
    #include<iostream>
    using namespace std;
    int a[20],b[20],t[20],sum[20],dp[1<<18];
    int main()
    {
        int n,m,v,i,j;
        long long mo,ans=0;
        cin>>n>>m>>v;
        for(i=0;i<m;i++)
         cin>>a[i]>>b[i]>>t[i];
         
        for(i=0;i<(1<<m);i++)
         {
            mo=0;
            for(j=0;j<m;j++)
             if(i&(1<<j))
              {
                sum[a[j]]+=t[j];
                sum[b[j]]-=t[j];
                mo+=(b[j]-a[j])*t[j];
              }
             for(j=1;j<=n;j++)
              {
                sum[j]+=sum[j-1];
                if(sum[j]>v)
                 break;
              }
            if(j>n)
             ans=max(ans,mo);
            for(j=1;j<=n;j++)
             sum[j]=0;
        }
        
        cout<<ans;
        return 0;
    }
    
  • 0
    @ 2018-09-17 10:14:27

    直接枚举+模拟就行

    //O(n*2^m) 
    #include<iostream>
    #include<cstring>
    #include<algorithm>
    using namespace std; 
    int n,s[20],v,m,a[20];
    struct st{
        int a,b,t;
    }e[20];
    int main(){
        cin>>n>>m>>v;
        int i,k,cn,p,ans=0,t;
        for(i=1;i<=m;i++){
            cin>>e[i].a>>e[i].b>>e[i].t;
        }
        cn=1<<m; 
        for(k=0;k<cn;k++){
            //二进制数表示枚举状态,用t保存当前答案,s做前缀和检查是否符合要求 
            memset(a,0,sizeof(a));
            p=k;
            t=0;
            for(i=1;i<=m;i++){
                if(p&1){
                    a[e[i].a]+=e[i].t;
                    a[e[i].b]-=e[i].t;
                    t+=e[i].t*(e[i].b-e[i].a);
                }
                p>>=1;
            }
            s[0]=0;
            for(i=1;i<=n;i++) {
                s[i]=s[i-1]+a[i];
                if(s[i]>v){
                    t=0;
                    break;
                }
            }
            ans=max(ans,t);
        }
        cout<<ans;
        return 0;
    }
    
  • 0
    @ 2017-01-31 10:28:57

    明明是DFS,硬说是模拟。。。
    编译成功

    foo.cpp:6:0: warning: ignoring #pragma warning [-Wunknown-pragmas]
    #pragma warning (disable:4996)

    测试数据 #0: Accepted, time = 0 ms, mem = 728 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 732 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 728 KiB, score = 10
    测试数据 #3: Accepted, time = 0 ms, mem = 728 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 732 KiB, score = 10
    测试数据 #5: Accepted, time = 0 ms, mem = 728 KiB, score = 10
    测试数据 #6: Accepted, time = 0 ms, mem = 728 KiB, score = 10
    测试数据 #7: Accepted, time = 0 ms, mem = 728 KiB, score = 10
    测试数据 #8: Accepted, time = 0 ms, mem = 732 KiB, score = 10
    测试数据 #9: Accepted, time = 0 ms, mem = 728 KiB, score = 10
    Accepted, time = 0 ms, mem = 732 KiB, score = 100
    c++
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #define MAXN 18
    #pragma warning (disable:4996)
    using namespace std;
    int nN, nM, nV, nMax;
    struct tNode
    {
    int nFrom, nTo, nP;
    }tPass[MAXN];
    bool bMyCmp(const tNode &tA, const tNode &tB);
    void vDfs(int nAi, int nCost,int nVis[]);
    bool bCheck(int nVis[], tNode tA);
    void vAdd(int nVis[], tNode tA);
    int main()
    {
    int i, nVis[MAXN];
    while (~scanf("%d%d%d", &nN, &nM, &nV))
    {
    for (i = 0; i < nM; i++)
    scanf("%d%d%d", &tPass[i].nFrom, &tPass[i].nTo, &tPass[i].nP);
    sort(&tPass[0], &tPass[nM], bMyCmp);
    memset(nVis, 0, sizeof(nVis));
    nMax = 0;
    vDfs(0, 0, nVis);
    printf("%d\n", nMax);
    }
    return 0;
    }
    bool bMyCmp(const tNode &tA, const tNode &tB)
    {
    if (tA.nFrom == tB.nFrom)
    return tA.nTo < tB.nTo;
    return tA.nTo < tB.nTo;
    }
    void vDfs(int nAi, int nCost, int nVis[])
    {
    int i, nT[MAXN], j;
    if (nCost > nMax)
    nMax = nCost;
    for (i = nAi; i < nM; i++)
    {
    if (bCheck(nVis, tPass[i]))
    {
    for (j = 0; j < nN; j++)
    nT[j] = nVis[j];
    vAdd(nT, tPass[i]);
    vDfs(i + 1, nCost + (tPass[i].nTo - tPass[i].nFrom)*tPass[i].nP, nT);
    }
    }
    }
    bool bCheck(int nVis[], tNode tA)
    {
    int i;
    for (i = tA.nFrom; i < tA.nTo; i++)
    {
    if (i > nN)
    return false;
    if (nVis[i] + tA.nP>nV)
    return false;
    }
    return true;
    }
    void vAdd(int nVis[], tNode tA)
    {
    int i;
    for (i = tA.nFrom; i < tA.nTo; i++)
    nVis[i] += tA.nP;
    }

  • 0
    @ 2015-03-28 10:37:41

    请高人指点,我为什么错了。。
    var
    i,j,n,k,x,v,m,sum,p:longint;
    a,b,c:array [1..100] of longint;
    f:array [1..100] of boolean;
    procedure s(t:longint);
    var
    i,j:longint;
    begin
    if p>v then exit;
    if k>sum then sum:=k;
    if t=n+1 then exit
    else
    begin
    for i:= 1 to m do
    if b[i]<t then begin k:=k-(b[i]-a[i])*c[i]; p:=p-c[i]; f[i]:=true; end;
    for i:= 1 to m do
    if (b[i]>=t) and (f[i]) then
    begin
    f[i]:=false;
    k:=k+(b[i]-a[i])*c[i];
    p:=p+c[i];
    s(t+1);
    f[i]:=true;
    p:=p-c[i];
    k:=k-(b[i]-a[i])*c[i];
    end;

    end;
    end;

    begin
    readln(n,m,v);
    for i:= 1 to m do readln(a[i],b[i],c[i]);
    fillchar(f,sizeof(f),true);
    s(1);
    writeln(sum);
    end.

  • 0
    @ 2009-11-09 16:23:16

    注意上车时刻,和下车时刻。

    到站时马上就下车了= =||害我wa了三次

  • 0
    @ 2009-11-05 10:12:15

    (写个自己)

    我也裸搜的

    本来是拿车站作为搜索变量的

    怎么也不对

    这道题通过率都被我刷下来了

    后来看了题解才猛然发觉

    应该拿上车的申请做变量

    原来的方法在同一个车站只能让一个请求通过

    这很明显是不对的

    然后就是退化了

    刚开始递归的时候算费用还搞错了

    当成动归那样算 f[b[i]]:=f[a[i]]+...

    其实用一变量就好了……

  • 0
    @ 2009-10-29 19:22:43

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

    完了完了……这等水题都wa了一次,没药救了……

    千万注意增加的不包括a站点的人数……

    下一个目标:生命之泉(虽然我还不会网络流 T^T )

  • 0
    @ 2009-10-18 21:02:14

    program p1341;

    type re=record

    n,s,e:longint;

    end;

    var a,w,down:array[1..18]of re;

    c:array[1..100]of boolean;

    n,m,limit,ans:longint;

    procedure init;

    var i,j:longint;

    begin

    readln(n,m,limit);

    for i:=1 to m do

    readln(a[i].s,a[i].e,a[i].n);

    end;

    procedure sort;

    var i,j:longint; t:re;

    begin

    for i:=1 to m do

    for j:=i+1 to m do

    if a[j].sn) then

    begin

    if sum>ans then ans:=sum;

    exit;

    end;

    if pre0 then

    for i:=1 to pre do

    if (a[i].e>a[pre].s)and(a[i].e

  • 0
    @ 2009-10-04 11:28:37

    真恶心

    for i := inf[now,1] to inf[now,2] do

    begin

    ...

    end;

    就错



    for i := inf[now,1]+1 to inf[now,2] do

    begin

    ...

    end;

    才对

    理解题意理解错了~

  • 0
    @ 2009-09-03 17:54:31

    dfs

    注意在终点位置的人数是不算的

  • 0
    @ 2009-08-10 18:11:54

    不行了,状态上十个没ac,直接copy了

  • 0
    @ 2009-08-07 12:55:12

    咋看咋像费用流啊,和生命之泉几乎一摸一样,就是数据范围小多了。。。。。。

  • 0
    @ 2009-08-03 10:05:45

    水题都要提交三次才过....~~~~(>__ans then ans:=sum;

    exit;

    end;;

    t:=true;

    for i:=a[k] to b[k]-1 do begin

    lin[i]:=lin[i]-p[k];

    if lin[i]

  • 0
    @ 2009-07-25 08:52:10

    var

    n,m,v,i,j,tt,ans:longint;

    a,b,t,zz:array[1..18] of longint;

    procedure dfs(x,y:longint);

    var

    i,j,k:longint;

    begin

    if x>m then

    begin

    if y>ans then ans:=y;

    exit;

    end;

    if (t[x]a[j] then

    begin

    tt:=a[i]; a[i]:=a[j]; a[j]:=tt;

    tt:=b[i]; b[i]:=b[j]; b[j]:=tt;

    tt:=t[i]; t[i]:=t[j]; t[j]:=tt;

    end;

    dfs(1,0);

    writeln(ans);

    end.

    先按起点站大小排序,再搜索。

  • 0
    @ 2009-07-16 17:27:28

    #include

    long doit(long x)

    {long i,j;

    if(x>m)

    else

    for(i=1;i

  • 0
    @ 2009-05-11 19:12:56

    本菜的题解....

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    var

    i,j,v,n,m,max,p:longint;

    a,b,t,mm:array[1..18]of longint;

    procedure writt;

    var i,j,nv:longint;

    f:boolean;

    begin

    nv:=0;f:=true;p:=0;

    for i:=1 to n do

    begin

    for j:=1 to m do begin if (mm[j]=1)and(a[j]=i)then nv:=nv+t[j];if (mm[j]=1)and(b[j]=i)then nv:=nv-t[j];end;

    if nv>v then f:=false;

    end;

    if f then for i:=1 to m do if mm[i]=1 then p:=p+(b[i]-a[i])*t[i];

    if p>max then max:=p;

    end;

    procedure doit(x:longint);

    var i,j:longint;

    begin

    if x>m then writt

    else

    for i:=1 to 2 do

    if i=1 then begin mm[x]:=1;doit(x+1);end else begin mm[x]:=0;doit(x+1);end;

    end;

    begin

    readln(n,m,v);

    for i:=1 to m do

    readln(a[i],b[i],t[i]);

    max:=0;fillchar(mm,sizeof(mm),0);

    doit(1);

    writeln(max);

    end.

  • 0
    @ 2009-04-23 16:49:01

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

    本来想用DP,可题目里没有给出v的范围,而且,数据这么小,为何不用搜索呢!

  • 0
    @ 2009-04-20 13:01:54

    动归不行吗?

    我怎么错乐。。。

  • 0
    @ 2009-03-12 19:44:22

    ......我竟然搜出了后效性....

  • 0
    @ 2009-02-20 21:13:44

    var ar:array[1..18,1..3] of longint;

    aa:array[1..10] of longint;

    m,n,k:integer;

    v,mm:longint;

    procedure hs(c:integer);

    var a,b,i,j,k1:integer; t,mm1:longint; p:boolean;

    begin

    p:=true;mm1:=0;

    for i:=c to m do begin

    for j:=ar to ar-1 do

    if aa[j]+ar>v then p:=false;

    if p then begin

    for j:=ar to ar-1 do aa[j]:=aa[j]+ar;

    hs(c+1);

    p:=true; for j:=ar to ar-1 do aa[j]:=aa[j]-ar;

    end; end;

    for k1:=1 to n do mm1:=mm1+aa[k1];

    if mm1>mm then mm:=mm1;

    end;

    begin

    readln(n,m,v);

    for k:=1 to m do

    readln(ar[k,1],ar[k,2],ar[k,3]);

    for k :=1 to 9 do aa[k]:=0;

    mm:=0;

    hs(1);

    writeln(mm);

    end.

    {编译通过...

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

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

    ├ 测试数据 03:答案错误... ├ 标准行输出

     ├ 错误行输出

    ├ 测试数据 04:答案错误... ├ 标准行输出

     ├ 错误行输出

    ├ 测试数据 05:答案错误... ├ 标准行输出

     ├ 错误行输出

    ├ 测试数据 06:运行超时...

    ├ 测试数据 07:运行超时...

    ├ 测试数据 08:运行超时...

    ├ 测试数据 09:运行超时...

    ├ 测试数据 10:运行超时...

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

    Unaccepted 有效得分:20 有效耗时:0ms

    }

    我为什么超时????~~~~~~~~~~~~回溯怎么不行?

信息

ID
1341
难度
6
分类
模拟 点击显示
标签
(无)
递交数
656
已通过
191
通过率
29%
上传者