BruceJay's Blog

BZOJ2879 美食节

| Comments

To start with

费用流动态加边~~~~~

Problem

Solution

将每个厨师x拆成p个点,第i个点p(x,i)表示厨师x做的倒数第i个菜,其对答案的贡献为i*t(x,y)。
所以S向菜i表示的点连容量pi,费用为0的边。厨师拆成的m*p个点向T连容量1,费用0的边。动态添加点p(x,i),每个菜y向p(x,i)连容量1,费用i*t(x,y)的边。
厨师拆成的m*p个点向T连容量1,费用0的边。这一步看似增大了边集的复杂度,其实是对厨师拆成的m*p个点的限制(流量至多为1)。同J房神犇Robert聪明一世糊涂一时,没注意这点,谜之WA了很久。
最后,其实S连向菜会比连向厨师快一些。

Code

#include <cstdio>
#include <cstring>
#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1010;
const int M = 30100;
const int INF = 0x3f3f3f3f;
struct Edge{int u,v,c,w,nxt;}e[M];
int a[N]; int p[N]; int dis[N];
bool vis[N]; int head[N];
queue<int> q;
int need[N];
int n,m,t,cnt=1;

inline int read()
{
    int t=1,x=0; char ch=getchar();
    while(ch<'0' || ch>'9'){
        if(ch=='-') t=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return t*x;
}

void Addedge(int u,int v,int c,int w)
{
    e[++cnt]=(Edge){u,v,c,w,head[u]}; head[u]=cnt;
    e[++cnt]=(Edge){v,u,0,-w,head[v]}; head[v]=cnt;
}

bool Spfa(int& flow,int& cost)
{
    memset(dis,INF,sizeof(dis));
    q.push(0); dis[0]=0;
    vis[0]=true; a[0]=INF; p[0]=0;
    while(!q.empty()){
        int u=q.front(); q.pop(); vis[u]=false;
        for(int i=head[u];i;i=e[i].nxt)
            if(e[i].c && dis[u]+e[i].w<dis[e[i].v]){
                dis[e[i].v]=dis[u]+e[i].w;
                a[e[i].v]=min(a[u],e[i].c); p[e[i].v]=i;
                if(!vis[e[i].v]) q.push(e[i].v),vis[e[i].v]=true;
            }
    }
    if(dis[t]==INF) return false;
    int u=t;
    flow+=a[t]; cost+=a[t]*dis[t];
    while(u){
        e[p[u]].c-=a[t];
        e[p[u]^1].c+=a[t];
        u=e[p[u]].u;
    }
    return true;
}

int MCMF()
{
    int cost=0,flow=0;
    while(Spfa(flow,cost));
    return cost;
}

int main()
{
    int u,v,w;
    freopen("1061.in","r",stdin);
    freopen("1061.out","w",stdout);
    n=read(); m=read(); t=n+2;
    for(int i=1;i<=n;i++) need[i]=read();
    for(int i=1;i<=n;i++) Addedge(i+1,i,INF,0);
    for(int i=1;i<=n+1;i++){
        int tmp=need[i]-need[i-1];
        if(tmp>0) Addedge(0,i,tmp,0);
        else Addedge(i,t,-tmp,0);
    }
    for(int i=1;i<=m;i++){
        u=read(); v=read(); w=read();
        Addedge(u,v+1,INF,w);
    }
    printf("%d",MCMF());
    return 0;
}

Last but not least

这题有个弱化版,BZOJ1070修车,不需要动态加边。
codevs始终TLE几个点TAT。

Comments

comments powered by Disqus