题解

30 条题解

  • 1
    @ 2017-07-13 15:26:23
    #include <cmath>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <iomanip>
    #include <iostream>
    #include <algorithm>
    #include <vector>
    #include <deque>
    #include <set>
    #include <limits>
    #include <string>
    #include <sstream>
    #include <thread>
    using namespace std;
    
    namespace dts
    {
        typedef long long ll;
        
        double oo_min=(numeric_limits<double>::min)(),oo_max=(numeric_limits<double>::max)();
        
        struct network_flows
        {
            vector<ll> e;
            vector<ll> pre;
            vector<ll> vis;
            vector<vector<ll> > cw;
            vector<vector<ll> > ce;
            vector<double> f;
            vector<double> u;
            vector<vector<double> > c;
            vector<vector<double> > p;
            deque<ll> q;
            
            void clear_flow()
            {
                e.clear();
                pre.clear();
                vis.clear();
                f.clear();
                u.clear();
            }
            
            void clear_edge()
            {
                clear_flow();
                cw.clear();
                ce.clear();
                c.clear();
                p.clear();
            }
            
            ll size()
            {
                return cw.size();
            }
            
            void set_size(ll size_v)
            {
                clear_edge();
                cw.resize(size_v);
                ce.resize(size());
                c.resize(size());
                p.resize(size());
            }
            
            void add_edge(ll x,ll y,double c_v,double p_v)
            {
                cw[x].push_back(y);
                c[x].push_back(c_v);
                p[x].push_back(p_v);
                ce[y].push_back(cw[x].size()-1);
                cw[y].push_back(x);
                c[y].push_back(0);
                p[y].push_back(-p_v);
                ce[x].push_back(cw[y].size()-1);
            }
            
            void prepare(ll s,ll t)
            {
                clear_flow();
                f.resize(size(),0);
                f[s]=oo_max;
                e.resize(size(),-1);
                u.resize(size(),oo_max);
                u[s]=0;
                pre.resize(size(),-1);
                pre[s]=s;
                vis.resize(size(),0);
            }
            
            ll bfs(ll s,ll t,double &flow,double &cost)
            {
                prepare(s,t);
                for (q.clear(),vis[s]=1,q.push_back(s);!q.empty();vis[q.front()]=0,q.pop_front())
                {
                    ll now=q.front();
                    for (ll i=0;i<cw[now].size();i++)
                        if (c[now][i]>0&&u[now]+p[now][i]<u[cw[now][i]])
                        {
                            f[cw[now][i]]=min(c[now][i],f[now]);
                            e[cw[now][i]]=i;
                            u[cw[now][i]]=u[now]+p[now][i];
                            pre[cw[now][i]]=now;
                            if (vis[cw[now][i]]==0)
                                vis[cw[now][i]]=1,q.push_back(cw[now][i]);
                        }
                }
                flow=f[t];
                cost=u[t];
                return (pre[t]!=-1);
            }
            
            void min_cost_max_flow(ll s,ll t,ll typ,double &flow,double &cost)
            {
                double temp_flow,temp_cost;
                while (bfs(s,t,temp_flow,temp_cost))
                {
                    for (ll i=t;i!=s;i=pre[i])
                        c[pre[i]][e[i]]-=temp_flow,c[i][ce[pre[i]][e[i]]]+=temp_flow;
                    flow+=temp_flow;
                    if (typ==0)
                        cost+=temp_cost;
                    else if (typ==1)
                        cost+=(temp_flow*temp_cost);
                }
            }
        }net;
        
        ll n,m,t;
        vector<double> a;
        
        void main()
        {
            while (~scanf("%lld%lld%lld",&n,&m,&t))
            {
                a.clear();
                a.resize(n+1,0);
                for (int i=1;i<=n;i++)
                    scanf("%lf",&a[i]);
                net.set_size(n-m+4);
                net.add_edge(0,1,t,0);
                net.add_edge(net.size()-2,net.size()-1,t,0);
                net.add_edge(1,net.size()-2,1,0);
                for (int i=1;i<=m;i++)
                    net.add_edge(1,i+1,1,-a[i]);
                for (int i=n-m+1;i<=n;i++)
                    net.add_edge(i-m+1,net.size()-2,1,-a[i]);
                for (int i=m+1;i<=n-m;i++)
                    net.add_edge(i-m+1,i+1,1,-a[i]);
                for (int i=1;i<=n-m+1;i++)
                    net.add_edge(i,i+1,oo_max,0);
                double ans_flow=0,ans_cost=0;
                net.min_cost_max_flow(0,net.size()-1,0,ans_flow,ans_cost);
                printf("%.0lf\n",-ans_cost);
            }
        }
    };
    
    int main()
    {
        dts::main();
    }
    
  • 1
    @ 2014-10-20 17:03:25

    研究了一天终于懂了 参考的是楼下boyzkk大神

    下面以N=5,M=2为例
    c[1]+c[2]<=k
    c[2]+c[3]<=k
    c[3]+c[4]<=k
    c[4]+c[5]<=k
    变换得
    c[1]+c[2]+y[1]-k=0
    c[2]+c[3]+y[2]-k=0
    c[3]+c[4]+y[3]-k=0
    c[4]+c[5]+y[4]-k=0

    添加0式为空,5式为空
    前-后得
    c[1]-c[2]+y[1]-k=0
    c[3]-c[1]+y[2]-y[1]=0
    c[4]-c[2]+y[3]-y[2]=0
    c[5]-c[3]+y[4]-y[3]=0
    -c[4]-c[5]-y[4]+k=0

    对于任意变量,在所有式子中均只出现两次,且一正一负,就像【流量平衡】
    于是把正数看做入流,负数看做出流,把每个式子抽象成一个点,连边
    比如①中有正C[1],②中有-C[1],那么由①向②连一条流量为1,费用为a[1]的边
    对于常数K,移向等号右边,那么由S向①式连一条流量为K,费用为0的边
    由⑤向T连一条流量为K,费用为0的边
    这是我的建图
    S=0; tot=n-m+2; T=tot+1;
    add(S,1,K,0); add(tot,T,K,0);
    add(1,tot,1,0);
    for (int i=1;i<=m;++i) add(1,i+1,1,a[i]);
    for (int i=n-m+1;i<=n;++i) add(i-m+1,tot,1,a[i]);
    for (int i=m+1;i<=n-m;++i) add(i-m+1,i+1,1,a[i]);
    for (int i=1;i<=n-m+1;++i) add(i,i+1,inf,0);

    • @ 2017-07-13 14:32:29

      添加0式为空,5式为空
      后-前
      c[1]+c[2]+y[1]-k=0
      c[3]-c[1]+y[2]-y[1]=0
      c[4]-c[2]+y[3]-y[2]=0
      c[5]-c[3]+y[4]-y[3]=0
      -c[4]-c[5]-y[4]+k=0

  • 1
    @ 2009-08-12 13:57:14

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    1次AC, 唯一缺憾的是第13次提交...

    说一下解法:

    c[i]表示第i件物品选与不选, 取值在[0,1].

    那么会有原始不等式:

    c[1]+c[2]+...+c[m]

  • 0
    @ 2014-05-30 19:38:32

    如果写过Employee的话,只要知道把每个物品当作选或者不选(0或1)来看待就好了
    x1+x2+...+xm-y1=k ..然后小心各种样例数据坑人,最好能自己手写一组去试试建边
    可以试试 n=13,m=3 k和下面那些数字无所谓,只是为了搞明白怎么建边

  • 0
    @ 2010-07-16 23:35:02

    70行的 朴素 单纯型…………

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

    Unaccepted 有效得分:60 有效耗时:2089ms

    话说我自己机子极限 随机数据是能过的…………

    如果不是vag 6k,说不定不优化就能过了……

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    加了一行贪心优化之后,依然是vag 6k………

  • 0
    @ 2010-04-12 20:54:10

    弱弱地问一句……什么叫线性规划(DP吗),我只知道这个题是费用流……

    • @ 2013-08-23 19:07:50

      线性规划跟动态规划不一样,是一种数序方法,高中数学有学的。。
      可以费用流解

  • 0
    @ 2010-04-05 09:34:07

    求数据……

    有的好心人发我邮箱吧:NWintre@163.com

    thx

  • 0
    @ 2010-04-04 13:49:33

    线性规划,重在构图。

  • 0
    @ 2010-03-15 21:27:47

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    我是傻X,让这题通过率狂掉………………

    模型类似于employee,但建图真的很讨厌…………交了8次,每次建图都不一样……………… - -!

    后来发现都是些傻瓜错误,囧。

    我就好心的发一下建图方法吧:

    add(st,1,K,0);

    add(n-m+2,en,K,0);

    for(i=1;i=n-m+2) add(1,n-m+2,1,a[i]);

    else add(1,i+1,1,a[i]);

    for(i=2;i=n-m+2) add(i,n-m+2,1,a);

    else add(i,i+m,1,a);

    for(i=1;i

  • 0
    @ 2010-03-11 18:52:20

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    囧RZ

  • 0
    @ 2009-09-18 22:47:37

    弱弱的我感慨:这题很强大,orz...

  • 0
    @ 2009-09-13 13:52:38

    编译通过...

  • 0
    @ 2009-09-07 16:47:35

    我是一个菜鸟。。。。。

    我用搜索与回溯做超时了。

    该怎么优化

  • 0
    @ 2009-09-07 11:32:13

    先开始队列尾循环,头忘循环循环,10分。

    后来改成循环,Accept。

  • 0
    @ 2009-08-30 16:23:20

    要用链表或者前向星存边,不习惯,不想写了

  • 0
    @ 2009-08-26 18:37:23

    我太沙茶了,边容量是1,搞成maxlongint了

  • 0
    @ 2009-08-14 11:51:50

    谁来罩我把,为什么这题像1525那样构图只有60分.

  • 0
    @ 2009-08-16 16:49:10

    vijos不能添加新题了,voyagec2就覆盖了老题,不好意思啊。

    注意题目是绝对值小于1000,如果用zkw费用流必须要先做一次SPFA,否则处理负权边会出问题。

  • 0
    @ 2009-08-11 13:32:38

    谁偷了我的号!!!!!

    这个题目不是我加的!!

  • 0
    @ 2009-08-10 21:07:45

    此题建图方法不同会导致时间相差极大。

    ufo172849z沙茶建图用spfa不能秒杀。oimaster的神new建图用spfa秒杀。

信息

ID
1499
难度
5
分类
图结构 | 网络流 点击显示
标签
(无)
递交数
272
已通过
84
通过率
31%
被复制
2
上传者