洛谷 P2050 [NOI2012]美食节

费用流

好题

推荐这篇博客click here

注意此题如果不用动态开点的话10000的数组是不够的的，会RE

因此网络流推荐动态开点更方便（原来都是手算的）

#include<bits/stdc++.h>
using namespace std;

#define go(i,a,b) for(int i=a;i<=b;++i)
#define com(i,a,b) for(int i=a;i>=b;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#define add_edge(u,v,w,co) add(u,v,w,co),add(v,u,0,-co)

const int N=110,s=0,t=10000,inf=0x3f3f3f3f;

int cnt,head[N*N],g[N][N],pre[N*N],incf[N*N],ans=0,cook[N*N],dfn[N*N],tot=0;
int d[N*N],n,m,a[N];
bool inq[N*N];
struct edge{
    int nxt,v,w,co;
}e[2*N*N*N];
queue<int>q;

void add(int u,int v,int w,int co){
    e[cnt]=(edge){head[u],v,w,co};
    head[u]=cnt++;
}

void read(int &x){
    x=0;char c=getchar(),f=1;
    while(!isdigit(c)){ if(c=='-') f=-1; c=getchar(); }
    while(isdigit(c)){ x=x*10+c-'0'; c=getchar(); }
    x*=f;
}

bool spfa(){
    mem(d,0x3f);mem(inq,0);
    q.push(s);d[s]=0;incf[s]=inf;
    while(!q.empty()){
        int u=q.front();q.pop();inq[u]=0;
        for(int i=head[u];i+1;i=e[i].nxt){
            if(!e[i].w) continue;
            int v=e[i].v,co=e[i].co;
            if(d[v]>d[u]+co){
                d[v]=d[u]+co;
                incf[v]=min(incf[u],e[i].w);
                pre[v]=i;
                if(!inq[v]) q.push(v),inq[v]=1;
            }
        }
    }
    return d[t]!=inf;
}

void EK(){
    int x=t;
    while(x!=s){
        int i=pre[x];
        e[i].w-=incf[t];
        e[i^1].w+=incf[t];
        x=e[i^1].v;
    }
    ans+=incf[t]*d[t];
    x=e[pre[t]^1].v;
    cook[++tot]=cook[x],dfn[tot]=dfn[x]+1;
    add_edge(tot,t,1,0);
    go(i,1,n) add_edge(i,tot,1,g[i][cook[tot]]*(dfn[tot]+1));
}

signed main(){
    //freopen("input.txt","r",stdin);
    mem(head,-1);
    read(n),read(m);
    go(i,1,n) read(a[i]);
    go(i,1,n)
        go(j,1,m) read(g[i][j]);
    go(i,1,n) add_edge(s,i,a[i],0);
    tot=n;
    go(i,1,m){
        cook[++tot]=i,dfn[tot]=0;
        add_edge(tot,t,1,0);
        go(j,1,n) add_edge(j,tot,1,g[j][i]);
    }
    while(spfa())
        EK();
    printf("%d",ans);
    return 0;
}