//这两道题有什么区别。。。= =

 #include<iostream>

 #include<cstdio>

 #include<cmath>

 #include<algorithm>

 #include<queue>

 #include<cstring>

 using namespace std;

 const int maxn=+,maxm=+,inf=-1u>>;

 struct ISAP{

     struct tedge{int x,y,w,next;}adj[maxm];int ms,fch[maxn];

     int d[maxn],s[maxn],cur[maxn],gap[maxn],n,top;

     void init(int n){

         this->n=n;ms=;top=;

         memset(d,-,sizeof(d));

         memset(fch,-,sizeof(fch));

         return;

     }

     void addedge(int u,int v,int w){

         adj[ms]=(tedge){u,v,w,fch[u]};fch[u]=ms++;

         adj[ms]=(tedge){v,u,,fch[v]};fch[v]=ms++;

         return;

     }

     void bfs(){

         queue<int>Q;Q.push(n);d[n]=;

         while(!Q.empty()){

             int u=Q.front();Q.pop();

             for(int i=fch[u];i!=-;i=adj[i].next){

                 int v=adj[i].y;

                 if(d[v]==-) d[v]=d[u]+,Q.push(v);

             }

         } return;

     }

     int maxflow(int S,int T){

         n=T;bfs();int k=S,i,flow=;

         for(i=;i<=n;i++) cur[i]=fch[i],gap[d[i]]++;

         while(d[S]<n){

             if(k==n){

                 int mi=inf,pos;

                 for(i=;i<top;i++) if(adj[s[i]].w<mi) mi=adj[s[i]].w,pos=i;

                 for(i=;i<top;i++) adj[s[i]].w-=mi,adj[s[i]^].w+=mi;

                 flow+=mi;top=pos;k=adj[s[top]].x;

             }

             for(i=cur[k];i!=-;i=adj[i].next){

                 int v=adj[i].y;

                 if(adj[i].w&&d[k]==d[v]+){cur[k]=i;k=v;s[top++]=i;break;}

             }

             if(i==-){

                 int lim=n;

                 for(i=fch[k];i!=-;i=adj[i].next){

                     int v=adj[i].y;

                     if(adj[i].w&&d[v]<lim) lim=d[v],cur[k]=i;

                 } if(--gap[d[k]]==) break;

                 d[k]=lim+;gap[d[k]]++;

                 if(k!=S) k=adj[s[--top]].x;

             }

         } return flow;

     }

 }sol;

 inline int read(){

     int x=,sig=;char ch=getchar();

     while(!isdigit(ch)){if(ch=='-') sig=-;ch=getchar();}

     while(isdigit(ch)) x=*x+ch-'',ch=getchar();

     return x*=sig;

 }

 inline void write(int x){

     if(x==){putchar('');return;}if(x<) putchar('-'),x=-x;

     int len=,buf[];while(x) buf[len++]=x%,x/=;

     for(int i=len-;i>=;i--) putchar(buf[i]+'');return;

 }

 int A[][],mx[]={,-,,},my[]={,,-,};

 void init(){

     int n=read();long long ans=;

     sol.init(n*n+);int S=n*n+,T=n*n+;

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

        for(int j=;j<=n;j++){

                A[i][j]=read();

             if((i+j)&){

                sol.addedge(S,i*n+j-n,A[i][j]);

                for(int d=;d<;d++){

                    int nx=i+mx[d],ny=j+my[d];

                    if(nx>=&&nx<=n&&ny>=&&ny<=n) sol.addedge(i*n+j-n,nx*n+ny-n,inf);

                }

            }

            else sol.addedge(i*n+j-n,T,A[i][j]);

            ans+=A[i][j];

        }

     write(ans-sol.maxflow(S,T));

     return;

 }

 void work(){

     return;

 }

 void print(){

     return;

 }

 int main(){

     init();work();print();return ;

 }

 #include <iostream>

 #include <queue>

 using namespace std;

 const int maxn =  + ;

 const int maxm =  + ;

 struct Edge

 {

     int from, to, cap, flow;

 };

 struct Dinic

 {

     int n, m, s, t;

     int first[maxn], next[maxm];

     Edge edges[maxm];

     void init(int n)

     {

         this -> n = n;

         m = ;

         memset(first, -, sizeof(first));

         return ;

     }

     void AddEdge(int from, int to, int cap)

     {

         edges[m] = (Edge){from, to, cap, };

         next[m] = first[from];

         first[from] = m++;

         edges[m] = (Edge){to, from, , };

         next[m] = first[to];

         first[to] = m++;

         return ;

     }

     int d[maxn], cur[maxn];

     bool vis[maxn];

     int BFS()

     {

         memset(vis, , sizeof(vis));

         queue<int> Q;

         Q.push(s);

         vis[s] = true;

         d[s] = ;

         while(!Q.empty())

         {

             int x = Q.front(); Q.pop();

             for(int i = first[x]; i != -; i = next[i])

             {

                 Edge& e = edges[i];

                 if(!vis[e.to] && e.cap > e.flow)

                 {

                     vis[e.to] = true;

                     d[e.to] = d[x] + ;

                     Q.push(e.to);

                 }

             }

         }

         return vis[t];

     }

     int DFS(int x, int a)

     {

         if(x == t || !a) return a;

         int f, flow = ;

         for(int& i = cur[x]; i != -; i = next[i])

         {

             Edge& e = edges[i];

             if(d[e.to] == d[x] +  && (f = DFS(e.to, min(a, e.cap - e.flow))) > )

             {

                 flow += f;

                 a -= f;

                 e.flow += f;

                 edges[i ^ ].flow -= f;

                 if(!a) break;

             }

         }

         return flow;

     }

     int MaxFlow(int s, int t)

     {

         this -> s = s;

         this -> t = t;

         int flow = ;

         while(BFS())

         {

             for(int i = ; i < n; i++) cur[i] = first[i];

             flow += DFS(s, );

         }

         return flow;   //你大爷！！！！！！！！！！！！！！！！

     }

 }sol;

 int a[][];

 int nx[] = {, , -, };

 int ny[] = {-, , , };

 int main()

 {

     int n, m;

     scanf("%d", &n);

     m = n;

     sol.init(n * m + );

     long long double tot = ;

     int s = n * m;

     int t = n * m + ;

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

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

       {

           scanf("%d", &a[i][j]);

           tot += a[i][j];

           if((i + j) & )

           {

               sol.AddEdge(s, i * m + j, a[i][j]);

               for(int d = ; d < ; d++)

               {

                   int mx = nx[d] + i;

                   int my = ny[d] + j;

                   if(mx >=  && mx < n && my >=  && my < m)

                   {

                       sol.AddEdge(i * m + j, mx * m + my, );

                   }

               }

           }

           else sol.AddEdge(i * m + j, t, a[i][j]);

       }

     printf("%d\n", tot - sol.MaxFlow(s, t));

     //system("pause");

     return ;

 }

搜索

复制