汕头市队赛 SRM16 T2

描述

猫和老鼠，看过吧？猫来了，老鼠要躲进洞里。在一条数轴上，一共有n个洞，位置分别在xi，能容纳vi只老鼠。一共有m只老鼠位置分别在Xi，要躲进洞里，问所有老鼠跑进洞里的距离总和最小是多少。

输入格式

两个用空格隔开的整数m和n。

这一行m个数字分别表示老鼠的位置

接下来n行每行两个数字分别表示洞的位置和容纳量

输出格式

一个整数，表示最小的距离总和。（如果无解，输出-1）

样例输入

样例输出

11
——————————————————————————
 n <= 500, m <= 500 的时候可以写费用流 但是要比较好的建图方式
nm的建图肯定要挂

#include<cstdio>

#include<cstring>

#include<algorithm>

#define LL long long

using namespace std;

const int M=2e3+,inf=0x3f3f3f3f;

const LL mx=1e15;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>'') {if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<='') {ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,m,q[M],vis[M];

int N,S,T;

LL ans,d[M];

struct node{int to,next,flow;LL cost;}e[M*M];

int first[M],cnt=,cur[M];

void ins(int a,int b,int flow,LL cost){e[++cnt]=(node){b,first[a],flow,cost}; first[a]=cnt;}

void insert(int a,int b,int flow,LL cost){ins(a,b,flow,cost); ins(b,a,,-cost);}

bool spfa(){

    for(int i=S;i<=T;i++) d[i]=mx;

    int head=,tail=;

    q[]=T; vis[T]=; d[T]=;

    while(head!=tail){

         int x=q[head++]; if(head>M) head=;

         for(int i=first[x];i;i=e[i].next){

             int now=e[i].to;

            if(e[i^].flow&&d[x]+e[i^].cost<d[now]){

                d[now]=d[x]+e[i^].cost;

                if(!vis[now]){

                    if(d[now]<d[q[head]]){head--; if(head<) head=M; q[head]=now;}

                    else{q[tail++]=now; if(tail>M) tail=;}

                    vis[now]=;

                }

            }

         }

         vis[x]=;

     }

    return d[S]<mx;

}

int dfs(int x,int a){

    if(x==T||a==)return a;

    vis[x]=;

    int flow=,f;

    for(int& i=cur[x];i;i=e[i].next){

        int now=e[i].to;

        if(!vis[now]&&d[x]==e[i].cost+d[now]&&(f=dfs(now,min(a,e[i].flow)))>){

               e[i].flow-=f; e[i^].flow+=f;

            ans+=e[i].cost*f; flow+=f;

              a-=f;if(a==)break;

        }

      }

    vis[x]=;

    return flow;

}

int x[M];

LL sum;

struct pos{int y,k;}qq[M];

bool cmp(pos a,pos b){return a.y<b.y;}

int main()

{

    n=read(); m=read();

    S=; T=n+m+;

    for(int i=;i<=n;i++) x[i]=read(),insert(S,i,,);

    for(int i=;i<=m;i++) qq[i].y=read(),qq[i].k=read(),sum+=qq[i].k;

    if(sum<n){printf("-1\n"); return ;}

    sort(qq+,qq++m,cmp);

    for(int i=;i<=m;i++) insert(i+n,T,qq[i].k,);

    for(int i=;i<=m;i++){

        if(i>) insert(i+n,i+n-,inf,qq[i].y-qq[i-].y);

        if(i<m) insert(i+n,i+n+,inf,qq[i+].y-qq[i].y);

    }

    for(int i=;i<=n;i++){

        int k1=; while(qq[k1+].y<=x[i]&&k1<m) k1++;

        int k2=m; while(qq[k2-].y>=x[i]&&k2>) k2--;

        if(qq[k1].y<=x[i]) insert(i,k1+n,,x[i]-qq[k1].y);

        if(qq[k2].y>=x[i]) insert(i,k2+n,,qq[k2].y-x[i]);

    }

    while(spfa()){for(int i=;i<=T;i++) cur[i]=first[i]; dfs(S,inf);}

    printf("%lld\n",ans);

    return ;

}

n <= 5000, m <= 5000 的时候就需要dp了

先将洞和老鼠按位置从小到大排一波序

因为老鼠选的洞必然是单调递增的我们可以考虑dp

f【i】【j】表示前i个洞选j只老鼠

转移方程 f【i】【j】=f【i-1】【k】+（k+1到j 的距离

然后发现是三方的写法然后就后面可以用单调队列优化dp降一波复杂度

然后就是n方写法了

这里我们每次可以算一下每只老鼠到第i个洞的前缀

队列里扔的就是f【j】+（前缀数组）s【j】就好啦

f【i】=q【l】+s【i】就好辣

#include<cstdio>

#include<cstring>

#include<algorithm>

#define LL long long

using namespace std;

const int M=5e3+;

const LL inf=1e15;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>'') {if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<='') {ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int l,r,n,m,x[M];

struct pos{int y,k;}e[M];

bool cmp(pos a,pos b){return a.y<b.y;}

LL sum,f[M],s[M];

LL pabs(LL x){return x>=?x:-x;}

struct node{LL v; int pos;}q[M];

int main()

{

    n=read(); m=read();

    for(int i=;i<=n;i++) x[i]=read();

    for(int i=;i<=m;i++) e[i].y=read(),e[i].k=read(),sum+=e[i].k;

    if(sum<n){printf("-1\n"); return ;}

    sort(x+,x++n);

    sort(e+,e++m,cmp);

    for(int i=;i<=n;i++) f[i]=inf;

    for(int i=;i<=m;i++){

        l=; r=;

        for(int j=;j<=n;j++) s[j]=s[j-]+pabs(x[j]-e[i].y);

        for(int j=;j<=n;j++){

            while(l<=r&&q[r].v>=f[j]-s[j]) r--;

            while(l<=r&&(j-q[l].pos)>e[i].k) l++;

            q[++r].v=f[j]-s[j]; q[r].pos=j;

            f[j]=q[l].v+s[j];

        }

    }printf("%lld\n",f[n]);

    return ;

}

巴特西

汕头市队赛 SRM16 T2

描述

输入格式

输出格式

样例输入

样例输出

最新文章

热门文章