bzoj 2879: [Noi2012]美食节

.

题意：自己看
题解：费用流
和修车差不多，但要动态加边。
代码：

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

int n,m,p[5000],fst[90000],num=1,s,t,a[5000][10010],dis[90000],flo[90000],pre[90000],nn[10010],ans=0,kk,r[90000];
struct edge
{
    int x,y,c,d,n;
}e[400000];
bool v[90000];

void ins(int x,int y,int c,int d)
{
    e[++num]={x,y,c,d,fst[x]};
    fst[x]=num;
}
int spfa()
{
    static queue<int>q;
    memset(dis,63,sizeof(dis));
    memset(flo,0,sizeof(flo));
    memset(pre,0,sizeof(pre));
    memset(v,0,sizeof(v));
    q.push(s);
    dis[s]=0;
    flo[s]=1<<30;
    while(!q.empty())
    {
        int x=q.front();
        v[x]=0;
        for(int i=fst[x];i;i=e[i].n)
        {
            int y=e[i].y;
            if(e[i].d&&dis[y]>dis[x]+e[i].c)
            {
                dis[y]=dis[x]+e[i].c;
                pre[y]=i;
                flo[y]=min(flo[x],e[i].d);
                if(!v[y])
                {
                    v[y]=1;
                    q.push(y);
                }
            }
        }
        q.pop();
    }
    return flo[t];
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    scanf("%d",&p[i]);
    s=0,t=n+m+1;
    for(int i=1;i<=n;i++)
    {
        ins(s,i,0,p[i]);
        ins(i,s,0,0);
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&a[i][j]);
            ins(i,j+n,a[i][j],1);
            ins(j+n,i,-a[i][j],0);
        }
    }
    for(int i=1;i<=m;i++)
    {
        ins(i+n,t,0,1);
        ins(t,i+n,0,0);
        nn[i]=1;
        r[i+n]=i;
    }
    kk=t;
    int hh;
    while(hh=spfa())
    {
        int oo,pp;
        for(int i=pre[t];i;i=pre[e[i].x])
        {
            if(r[e[i].y])
            {
                kk++;
                ins(kk,t,0,1);
                ins(t,kk,0,0);
                r[kk]=r[e[i].y];
                r[e[i].y]=0;
                nn[r[kk]]++;
                for(int j=1;j<=n;j++)
                {
                    ins(j,kk,a[j][r[kk]]*nn[r[kk]],1);
                    ins(kk,j,-a[j][r[kk]]*nn[r[kk]],0);
                }
            }
        }
        for(int i=pre[t];i;i=pre[e[i].x])
        {
            e[i].d-=hh;
            e[i^1].d+=hh;
            ans+=e[i].c*hh;
        }/*
        for(int i=2;i<=num;i++)
        printf("%d %d %d %d\n",e[i].x,e[i].y,e[i].c,e[i].d);
        puts("=====");*/
//      printf("%d %d\n",oo,pp);
//      printf("%d\n",ans);
    }
    printf("%d",ans);
}