传纸条noip2008湖南费用流做法！ [复制链接]

首先！这个做法是很有意义的~加入要传2张以上的纸条怎么做ne ?费用流！！网上标准费用流建图~我用的是ZKW费用流~跪求哪里不对~只能对前三个点！神犇们快救我啊~调几天了！附程序：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<time.h>
#include<math.h>
intG[5022][5022],w[5022][5022],S=0,T,n,m,sx[5555],dis[5023],ans=0,h[55][55],num=0;
int ans1=0,wx[99];
void replace()
{
    int i,j,k,min1=200000000;
    for(i=0;i<=T;i++)
    if(sx)
    for(j=0;j<=T;j++)
    if(!sx[j])
    if(G[j]&&(-dis+dis[j]+w[j]<min1))min1=-dis+dis[j]+w[j];
    for(i=0;i<=T;i++)
    if(sx)dis+=min1;
}
int sap(int now,int flow)
{
    
    int i,j,k;
    
    if(now==T){
                ans+=-dis[S];
                return flow;
                }
    sx[now]=1;
    int tmp=flow;
    //for(j=1;j<=8;j++)
    //for(k=-1;k<=1;k++)
    for(i=0;i<=T;i++)
    {
    
    if(!sx&&G[now]&&dis+w[now]==dis[now])
    {
          if(G[now]<flow)flow=G[now];
     int t=sap(i,flow);
     if(t){
           G[now]-=t;
           G[now]+=t;
           return t;
           }
    flow=tmp;
    }
    }
    return 0;
}
int main()
{
   freopen("massage.in","r",stdin);
   freopen("massage.out","w",stdout);
   int i,j,k;
   scanf("%d%d",&n,&m);
   T=n*m*2+1;
   for(i=1;i<=n;i++)
   for(j=1;j<=m;j++)
    {
    scanf("%d",&h[j]);
    num++;
    G[num][num+n*m]=1;
    w[num][num+n*m]=-h[j];
    w[num+n*m][num]=h[j];
    if(j<m)G[num+n*m][num+1]=1;
    if(i<n)G[num+n*m][num+m]=1;
    }
    
    G[0][1]=2;
   G[n*m*2][T]=2;
   G[1][1+n*m]=2;
   G[n*m][n*m*2]=2;

   while(dis[S]<1900000)
    {
    memset(sx,0,sizeof(sx));
    while(sap(0,20000000))
    memset(sx,0,sizeof(sx));
    replace();
    }
   printf("%d\n",ans);
   return 0;
}