您现在的位置是:首页 > 正文

【ZJOI2013】bzoj3112 防守战线

2024-02-29 17:27:57阅读 5

首先可以列出形如

j=liriXjdi    (1im)

Minimizei=1nXici

的线性规划式子。但是注意到 Xi 的分布很杂乱,不好处理。考虑转化为对偶问题。
ljirjYjci    (1in)

Maximizei=1mYidi

这样就可以差分建图跑最大费用流了。但是这样是会T的,spfa加了SLF以后在bzoj上卡过了。

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=1020,maxe=200010,maxm=10010,p=1011,s=1005,t=1006,oo=0x3f3f3f3f;
int fir[maxn],ne[maxe],to[maxe],w[maxe],c[maxe],
que[maxn],in[maxn],dis[maxn],mnw[maxn],pre[maxn],
a[maxn],l[maxm],r[maxm],d[maxm],
n,m,num;
int rd()
{
    int x=0;
    char c=getchar();
    while (c<'0'||c>'9') c=getchar();
    while (c>='0'&&c<='9')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    return x;
}
void check()
{
    for (int i=0;i<=t;i++)
        for (int j=fir[i];j;j=ne[j])
            if (w[j])
                printf("%d->%d:%d,%d\n",i,to[j],w[j],c[j]);
}
void add(int u,int v,int x,int y)
{
    num++;
    ne[num*2]=fir[u];
    fir[u]=num*2;
    to[num*2]=v;
    w[num*2]=x;
    c[num*2]=y;
    ne[num*2+1]=fir[v];
    fir[v]=num*2+1;
    to[num*2+1]=u;
    w[num*2+1]=0;
    c[num*2+1]=-y;
}
void inc(int &x)
{
    x=x+1==p?0:x+1;
}
int find(int &ret)
{
    int hd=0,tl=1,u,v;
    que[0]=s;
    for (int i=0;i<=n;i++) dis[i]=-oo;
    dis[t]=-oo;
    dis[s]=0;
    mnw[s]=oo;
    in[s]=1;
    while (hd!=tl)
    {
        u=que[hd];
        inc(hd);
        for (int i=fir[u];i;i=ne[i])
            if (w[i]&&dis[v=to[i]]<dis[u]+c[i])
            {
                dis[v]=dis[u]+c[i];
                pre[v]=i;
                mnw[v]=min(mnw[u],w[i]);
                if (!in[v])
                {
                    in[v]=1;
                    que[tl]=v;
                    if (dis[que[tl]]>dis[que[hd]]) swap(que[tl],que[hd]); 
                    inc(tl);
                }
            }
        in[u]=0;
    }
    if (dis[t]==-oo) return 0;
    for (int i=pre[t];i;i=pre[to[i^1]])
    {
        w[i]-=mnw[t];
        w[i^1]+=mnw[t];
    }
    ret=dis[t]*mnw[t];
    return 1;
}
int main()
{
    int ans=0,x;
    n=rd();
    m=rd();
    for (int i=1;i<=n;i++)
    {
        a[i]=rd();
        if (a[i]>a[i-1]) add(i-1,t,a[i]-a[i-1],0);
        else add(s,i-1,a[i-1]-a[i],0);
        add(i,i-1,oo,0);
    }
    add(s,n,a[n],0);
    for (int i=1;i<=m;i++)
    {
        l[i]=rd();
        r[i]=rd();
        d[i]=rd();
        add(r[i],l[i]-1,oo,d[i]);
    }
    //check();
    while (find(x)) ans+=x;
    printf("%d\n",ans);
}

网站文章

  • 「Torrent文件的奥秘揭示:从字节到资源的计算机网络深度解析!」

    通过深入了解Torrent文件的原理和工作方式,我们能更好地利用它来获取需要的资源,并且注意在合法、安全的前提下进行使用。当用户开始下载一个Torrent文件时,Torrent客户端首先会连接Trac...

    2024-02-29 17:27:29
  • 【C++】:静态转换(static_cast)与动态类型转换(dynamic_cast)

    【C++】:静态转换(static_cast)与动态类型转换(dynamic_cast)

    这篇笔记的内容是:静态类型转换与动态类型转换 在之前我们学过,变量的数据类型可以强制转换为其他数据类型。但由于这种C风格的类型转换可能会出现一些问题,即过于松散的情况,因此C++提出了更加规范、严格的...

    2024-02-29 17:27:22
  • 求质数(Prime Number 素数)的方法——厄拉多塞筛法

    质数又称素数。指在一个大于1的自然数中,除了1和此整数自身外,没法被其他自然数整除的数。换句话说,只有两个正因数(1和自己)的自然数即为素数。比1大但不是素数的数称为合数。1和0既非素数也非合数。合数是由若干个质数相乘而得到的。所以,质数是合数的基础,没有质数就没有合数。【1】一般方法素数是除了1和它本身之外再不能被其他数整除的自然数。由于找不到一个通项公式来表示所有的素数,所以对

    2024-02-29 17:27:16
  • waltz说明文档

    waltz说明文档

    文档链接:https://wepay.github.io/waltz/docs/introduction介绍 waltz是分布式/复制的预写日志。它的目标是成为一个通用的预写日志,以帮助微服务体系结...

    2024-02-29 17:27:07
  • Java 组件化(gradle)

    Java 组件化(gradle)

    组件化什么是组件化,直接看下面两张图。上面是非组件化的项目,下面是组件化的项目。非组件化的问题如果项目本身有多个互相不影响的模块,甚至有多人分开负责各个模块的开发时,非组件化项目的弊端就会暴露出来,主要是有下面几个:1、依赖难以管理,不同的模块依赖不同的库,甚至是同一个库的不同版本。2、各个模块单独打包麻烦。3、增加额外开发成本,开发本身可能只需要开发一个模块,但是由于...

    2024-02-29 17:26:36
  • Python ORM Pony 事务和db_session

    Pony是一个高级的对象关系映射器ORM框架。Pony它能够使用Python生成器表达式和lambdas向数据库编写查询。Pony分析表达式的抽象语法树,并将其转换为SQL查询。支持SQLite, MySQL, PostgreSQL和Oracle等数据库,本文主要介绍Python pony 中事务和db_session。原文地址:Python ORM Pony 事务和db_session

    2024-02-29 17:26:28
  • Bootstrap第二式

    根据Bootstrap第一节我们了解到了一些关于Bootstrap的基本知识,什么是Bootstrap,为什么用,用在哪里,怎么用。在Bootstrap第二式我们近一半了解一些关于Bootstrap的...

    2024-02-29 17:26:22
  • LeetCode90:Subsets II

    LeetCode90:Subsets II

    Given a collection of integers that might contain duplicates, nums, return all possible subsets.Note: Elements in a subset must be in non-descending order. The solution set must not contain duplicate

    2024-02-29 17:25:54
  • Docker安装mysql无法远程客户端访问

    Docker安装mysql无法远程客户端访问

    可以看到箭头部分,该库的root用户只允许当前主机连接,所以要登录到数据库中,修改root的连接方式为‘%’解决办法:1进入到mysql容器内部docker exec -it mysql_slave3...

    2024-02-29 17:25:14
  • C#基础知识(以宝马,车,车轮为例)

    C#基础知识(以宝马,车,车轮为例)

    派生类using System;using System.Collections.Generic;using System.Linq;using System.Text;using System.IO;using ClassLibrary1.util;using ClassLibrary1.util.util2;namespace ClassLibrary1...

    2024-02-29 17:25:05