【BZOJ2879】【NOI2012】美食节

新费用流建图技巧get

显然可以把每个厨师拆成\(\sum p\)个跑费用流

但是~~（你们又不高兴）~~这样跑会很慢，那怎么办？

开始只设\(m\)个厨师表示该厨师最后一次做的菜，增广完将被增广的厨师新建一个点作为他倒数第二次做的菜，代价翻倍，以此类推

脑补一下是对的

// <2879.cpp> - 01/02/17 14:14:08
// This file is created by XuYike's black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don't know what this program is.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
int gi(){
    int res=0,fh=1;char ch=getchar();
    while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
    if(ch=='-')fh=-1,ch=getchar();
    while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
    return fh*res;
}
const int MAXN=2010;
const int MAXM=2000010;
const int N=41;
const int M=110;
const int INF=1e9;
int bt=1,b[MAXN],next[MAXM],to[MAXM],val[MAXM],cost[MAXM];
inline void add(int x,int y,int z,int c){
    next[++bt]=b[x];b[x]=bt;to[bt]=y;val[bt]=z;cost[bt]=c;
    next[++bt]=b[y];b[y]=bt;to[bt]=x;val[bt]=0;cost[bt]=-c;
}
int T,p[N],t[N][M];
queue <int> q;
int dis[MAXN],pre[MAXN];
bool in[MAXN];
bool fc(){
    for(int i=1;i<=T;i++)dis[i]=INF,pre[i]=0;
    q.push(0);
    while(!q.empty()){
        int x=q.front();q.pop();in[x]=0;
        for(int i=b[x];i;i=next[i]){
            if(!val[i]||dis[x]+cost[i]>=dis[to[i]])continue;
            dis[to[i]]=dis[x]+cost[i];
            pre[to[i]]=i;
            if(in[to[i]])continue;
            in[to[i]]=1;
            q.push(to[i]);
        }
    }
    return dis[T]!=INF;
}
int get(){
    int f=INF;
    for(int i=pre[T];i;i=pre[to[i^1]])f=min(f,val[i]);
    for(int i=pre[T];i;i=pre[to[i^1]]){
        val[i]-=f;
        val[i^1]+=f;
    }
    return dis[T]*f;
}
int tot,pos[M],cnt[M];
int main(){
    int n=gi(),m=gi(),sum=0;
    for(int i=1;i<=n;i++)sum+=p[i]=gi();
    T=n+m+sum+1;
    for(int i=1;i<=n;i++){
        add(0,i,p[i],0);
        for(int j=1;j<=m;j++)add(i,n+j,1,t[i][j]=gi());
    }
    for(int i=1;i<=m;i++)add(pos[i]=n+i,T,1,0),cnt[i]=1;
    int ans=0;
    for(int k=1;k<=sum;k++){
        fc();ans+=get();
        int p;
        for(p=1;val[b[pos[p]]];p++);
        cnt[p]++;pos[p]=n+m+k;
        for(int i=1;i<=n;i++)add(i,pos[p],1,t[i][p]*cnt[p]);
        add(pos[p],T,1,0);
    }
    printf("%d",ans);
    return 0;
}

// <2879.cpp> - 01/02/17 14:14:08

// This file is created by XuYike's black technology automatically.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <queue>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

typedef long long lol;

int gi(){

int res=0,fh=1;char ch=getchar();

while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();

if(ch=='-')fh=-1,ch=getchar();

while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();

return fh*res;

}

const int MAXN=2010;

const int MAXM=2000010;

const int N=41;

const int M=110;

const int INF=1e9;

int bt=1,b[MAXN],next[MAXM],to[MAXM],val[MAXM],cost[MAXM];

inline void add(int x,int y,int z,int c){

next[++bt]=b[x];b[x]=bt;to[bt]=y;val[bt]=z;cost[bt]=c;

next[++bt]=b[y];b[y]=bt;to[bt]=x;val[bt]=0;cost[bt]=-c;

}

int T,p[N],t[N][M];

queue <int> q;

int dis[MAXN],pre[MAXN];

bool in[MAXN];

bool fc(){

for(int i=1;i<=T;i++)dis[i]=INF,pre[i]=0;

q.push(0);

while(!q.empty()){

int x=q.front();q.pop();in[x]=0;

for(int i=b[x];i;i=next[i]){

if(!val[i]||dis[x]+cost[i]>=dis[to[i]])continue;

dis[to[i]]=dis[x]+cost[i];

pre[to[i]]=i;

if(in[to[i]])continue;

in[to[i]]=1;

q.push(to[i]);

}

return dis[T]!=INF;

}

int get(){

int f=INF;

for(int i=pre[T];i;i=pre[to[i^1]])f=min(f,val[i]);

for(int i=pre[T];i;i=pre[to[i^1]]){

val[i]-=f;

val[i^1]+=f;

}

return dis[T]*f;

}

int tot,pos[M],cnt[M];

int main(){

int n=gi(),m=gi(),sum=0;

for(int i=1;i<=n;i++)sum+=p[i]=gi();

T=n+m+sum+1;

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

add(0,i,p[i],0);

for(int j=1;j<=m;j++)add(i,n+j,1,t[i][j]=gi());

}

for(int i=1;i<=m;i++)add(pos[i]=n+i,T,1,0),cnt[i]=1;

int ans=0;

for(int k=1;k<=sum;k++){

fc();ans+=get();

int p;

for(p=1;val[b[pos[p]]];p++);

cnt[p]++;pos[p]=n+m+k;

for(int i=1;i<=n;i++)add(i,pos[p],1,t[i][p]*cnt[p]);

add(pos[p],T,1,0);

}

printf("%d",ans);

return 0;

}

说点什么