bzoj1001最小割

听说最大流过不去？？？

dinic果然神了，1000,000的点都能过（主要是比较稀疏）

 #include <cstdio>

 #define INF 9223372036854775807

 int n,m,x,y,z,p,M=;long long ans=;

 int d[],l[],fir[],nex[],to[],wei[];

 int min(long long a,long long b){if(a<b) return a;else return b;}

 void add(int x,int y,int z){to[++M]=y;wei[M]=z;nex[M]=fir[x];fir[x]=M;

                             to[++M]=x;wei[M]=z;nex[M]=fir[y];fir[y]=M;}

 long long dfs(int now,long long flow)

 {

     if(now==n*m)

         return flow;

     long long used=;

     for(int i=fir[now];i;i=nex[i])

         if(d[to[i]]==d[now]+ && wei[i])

             {

                 int fl=dfs(to[i],min(flow-used,wei[i]));

                 wei[i]-=fl,wei[i^]+=fl;

                 used+=fl;

                 if(used==flow)

                     return flow;

             }

 //    if(!used) d[now]=-1;这句必写，否则T

     return used;

 }

 bool bfs()

 {

     int h=,t=;

     l[]=;d[]=;

     for(int i=;i<=n*m;i++) d[i]=-;

     while(h<t)

         for(int i=fir[l[++h]];i;i=nex[i])

         if(wei[i] && (d[to[i]]==-))

             l[++t]=to[i],d[l[t]]=d[l[h]]+;

     return d[n*m]+;

 }

 int main()

 {

     scanf("%d%d",&n,&m);

     for(int i=;i<=n;i++)

         for(int j=;j<m;j++)

             scanf("%d",&p),add((i-)*m+j,(i-)*m+j+,p);

     for(int i=;i<n;i++)

         for(int j=;j<=m;j++)

             scanf("%d",&p),add((i-)*m+j,i*m+j,p);

     for(int i=;i<n;i++)

         for(int j=;j<m;j++)

             scanf("%d",&p),add((i-)*m+j,i*m+j+,p);

     while(bfs()) ans+=dfs(,INF);

     printf("%lld\n",ans);

     return ;

 }

不要管longlong，现在打网络流就会想起以前忘记longlong调一晚上的痛苦