HDU 1565 方格取数(1)

给你一个n*n的格子的棋盘，每个格子里面有一个非负数。
从中取出若干个数，使得任意的两个数所在的格子没有公共边，就是说所取的数所在的2个格子不能相邻，并且取出的数的和最大。

包括多个测试实例，每个测试实例包括一个整数n 和n*n个非负数(n<=20)

对于每个测试实例，输出可能取得的最大的和

3

75 15 21

75 15 28

34 70 5 

188
直接用这个程序拿双倍经验吧~

 #include <iostream>

 #include <cstring>

 #include <cstdio>

 #include <queue>

 using namespace std;

 const int INF=;

 const int maxn=,maxm=;

 int cnt,fir[maxn],nxt[maxm],cap[maxm],to[maxm],dis[maxn],gap[maxn],path[maxn];

 int map[][];

 void addedge(int a,int b,int c)

 {

     nxt[++cnt]=fir[a];

     to[cnt]=b;

     cap[cnt]=c;

     fir[a]=cnt;

 }

 bool BFS(int S,int T)

 {

     memset(dis,,sizeof(dis));

     dis[T]=;

     queue<int>q;q.push(T);

     while(!q.empty())

     {

         int node=q.front();q.pop();

         for(int i=fir[node];i;i=nxt[i])

         {

             if(dis[to[i]])continue;

             dis[to[i]]=dis[node]+;

             q.push(to[i]);

         }

     }

     return dis[S];

 }

 int fron[maxn];

 int ISAP(int S,int T)

 {

     if(!BFS(S,T))

         return ;

     for(int i=;i<=T;i++)++gap[dis[i]];

     int p=S,ret=;

     memcpy(fron,fir,sizeof(fir));

     while(dis[S]<=T)

     {

         if(p==T){

             int f=INF;

             while(p!=S){

                 f=min(f,cap[path[p]]);

                 p=to[path[p]^];

             }

             p=T;ret+=f;

             while(p!=S){

                 cap[path[p]]-=f;

                 cap[path[p]^]+=f;

                 p=to[path[p]^];

             }

         }

         int &ii=fron[p];

         for(;ii;ii=nxt[ii]){

             if(!cap[ii]||dis[to[ii]]+!=dis[p])

                 continue;

             else

                 break;

         }

         if(ii){

             p=to[ii];

             path[p]=ii;

         }

         else{

             if(--gap[dis[p]]==)break;

             int minn=T+;

             for(int i=fir[p];i;i=nxt[i])

                 if(cap[i])

                     minn=min(minn,dis[to[i]]);

             gap[dis[p]=minn+]++;

             fron[p]=fir[p];

             if(p!=S)

                 p=to[path[p]^];

         }

     }

     return ret;

 }

 void Init()

 {

     memset(fir,,sizeof(fir));

     memset(gap,,sizeof(gap));

     cnt=;

 }

 int n,m;

 int dot(int x,int y){

     return (x-)*m+y;

 }

 int main()

 {

     int sum;

     while(~scanf("%d%d",&n,&m))

     {

         Init();sum=;

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

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

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

             sum+=map[i][j];

         } 

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

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

                 if((i+j)%==){

                     addedge(,(i-)*m+j,map[i][j]);

                     addedge((i-)*m+j,,);

                 }     

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

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

                 if((i+j)%==){

                     addedge((i-)*m+j,n*m+,map[i][j]);

                     addedge(n*m+,(i-)*m+j,);

                 } 

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

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

                 if((i+j)%==){

                     if(i+<=n){

                         addedge(dot(i,j),dot(i+,j),INF);

                         addedge(dot(i+,j),dot(i,j),);

                     }

                     if(i->=){

                         addedge(dot(i,j),dot(i-,j),INF);

                         addedge(dot(i-,j),dot(i,j),);

                     }if(j->=){

                         addedge(dot(i,j),dot(i,j-),INF);

                         addedge(dot(i,j-),dot(i,j),);

                     }

                     if(j+<=m){

                         addedge(dot(i,j),dot(i,j+),INF);

                         addedge(dot(i,j+),dot(i,j),);

                     }

                 }

         printf("%d\n",sum-ISAP(,n*m+));

     }

     return ;

 }