[线性规划与网络流之20]最大费用最大流

【题目大意】和K取方格数差不多，不过源和汇的连边有点改变。

【算法】最大费用最大流

【其它】1A

【CODE】

#include using namespace std;
const int N=600;
const int inf=0x7FFFFFFF/2-10;
struct gtp{int x,y,next,op,c,w;}g[100000];
int s,n,m,sn,en,e,S,T,cost;
int ls[N],d[N],fa[N],list[N],v[N],wz[N][N];

inline void add(int x,int y,int c,int w){
    e++;
    g[e].x=x; g[e].y=y; g[e].c=c; g[e].op=e+1; g[e].w=w;
    g[e].next=ls[x]; ls[x]=e;
    e++;
    g[e].x=y; g[e].y=x; g[e].c=0; g[e].op=e-1; g[e].w=-w;
    g[e].next=ls[y]; ls[y]=e;
}

void init(){
    memset(ls,0,sizeof(ls));
    scanf("%d%d%d%d",&sn,&en,&n,&m);
    int tot=0;
    for (int j=0;j<=n;j++)
      for (int i=0;i<=m;i++) wz[i][j]=++tot;
    S=(n+1)*(m+1)+1;
    T=S+1;
    for (int i=0;i<=n;i++)
      for (int j=1;j<=m;j++){
          int x;
          scanf("%d",&x);
          add(wz[j-1][i],wz[j][i],1,x);
          add(wz[j-1][i],wz[j][i],inf,0);
      }
    for (int j=0;j<=m;j++)
      for (int i=1;i<=n;i++){
          int x;
          scanf("%d",&x);
          add(wz[j][i-1],wz[j][i],1,x);
          add(wz[j][i-1],wz[j][i],inf,0);
      }
    for (int i=1;i<=sn;i++){
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        add(S,wz[z][y],x,0);
    }
    for (int i=1;i<=en;i++){
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        add(wz[z][y],T,x,0);
    }
}

bool spfa(){
    for (int i=0;i<=T;i++) d[i]=-inf;
    memset(v,0,sizeof(v));
    int head=0,tail=1;
    list[1]=S; v[S]=1; d[S]=0;
    while (head!=tail){
        head++; if (head>=N) head=0;
        for (int t=ls[list[head]];t;t=g[t].next)
          if (g[t].c && d[g[t].x]+g[t].w>d[g[t].y]){
              d[g[t].y]=d[g[t].x]+g[t].w;
              fa[g[t].y]=t;
              if (!v[g[t].y]){
                  v[g[t].y]=1;
                  tail++; if (tail>=N) tail=0;
                  list[tail]=g[t].y;
              }
          }
        v[list[head]]=0;
    }
    if (d[T]==-inf) return false;
    return true;
}

void change(){
    int nf=inf,i=T;
    nf=0x7FFFFFFF;
    for (;i!=S;i=g[fa[i]].x)
      if (g[fa[i]].c    for (i=T;i!=S;i=g[fa[i]].x){
        g[fa[i]].c-=nf;
        g[g[fa[i]].op].c+=nf;
    }
    cost+=nf*d[T];
}

void maxflow(){
    cost=0;
    while (spfa())
      change();
}

int main(){
    freopen("robo0.in","r",stdin);
    freopen("robo0.ans","w",stdout);
    init();
    maxflow();
    printf("%dn",cost);
    return 0;
}