洛谷P2774 方格取数问题

题目：https://www.luogu.org/problemnew/show/P2774

题目背景

none!

题目描述

在一个有 m*n 个方格的棋盘中，每个方格中有一个正整数。现要从方格中取数，使任意 2 个数所在方格没有公共边，且取出的数的总和最大。试设计一个满足要求的取数算法。对于给定的方格棋盘，按照取数要求编程找出总和最大的数。

输入输出格式

输入格式：

第 1 行有 2 个正整数 m 和 n，分别表示棋盘的行数和列数。接下来的 m 行，每行有 n 个正整数，表示棋盘方格中的数。

输出格式：

程序运行结束时，将取数的最大总和输出

输入输出样例

输入样例#1：

输出样例#1：

说明

m,n<=100

解析

网络流24题之一orz。

二分图点权最大独立集。

在二分图中找到权值和最大的点集，使得它们之间两两没有边。

答案=总权值-最小点覆盖集。

证明？我也不会啊orz。看这吧。

《最小割模型在信息学竞赛中的应用》

相邻的格子放入不同的集合X，Y。

1、从S向X集合中每个顶点连接一条容量为格子中数值的有向边。

2、从Y集合中每个顶点向T连接一条容量为格子中数值的有向边。（两个只要一个符合就行了）

3、相邻黑白格子Xi,Yj之间从Xi向Yj连接一条容量为无穷大的有向边。

ans=sigma(a(i,j))-maxflow();

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<algorithm>
  4 #include<cstring>
  5 #include<cmath>
  6 #include<vector>
  7 #include<queue>
  8 using namespace std;
  9 #define maxn 1100
 10 #define inf (1<<30)
 11 struct line{
 12     int to;
 13     int cap,flow;
 14 };
 15 vector<line> edge;
 16 vector<int> G[maxn];
 17 int fx[4][2]= {{1,0},{0,1},{-1,0},{0,-1}};  
 18 int m,n,tot,top;
 19 int c[maxn][maxn];
 20 int S,T;
 21 int cur[maxn];
 22 int dis[maxn];
 23 bool vis[maxn];
 24 void addedge(int from,int to,int cap){
 25     edge.push_back((line){to,cap,0});
 26     edge.push_back((line){from,0,0});
 27     int m=edge.size();
 28     G[from].push_back(m-2);
 29     G[to].push_back(m-1);
 30 }
 31 bool bfs(){
 32     memset(vis,false,sizeof(vis));
 33     queue<int> q;
 34     q.push(S);
 35     dis[S]=0;
 36     vis[S]=true;
 37     while (!q.empty()){
 38         int u=q.front();
 39         q.pop();
 40         for (int i=0;i<G[u].size();++i){
 41             line e=edge[G[u][i]];
 42             if (vis[e.to]) continue;
 43             if (e.flow>=e.cap) continue;
 44             q.push(e.to);
 45             vis[e.to]=true;
 46             dis[e.to]=dis[u]+1;
 47         }
 48     }
 49     return vis[T];
 50 } 
 51 int dfs(int x,int a){
 52     if (a==0||x==T) return a;
 53     int flow=0,f;
 54     for (int &i=cur[x];i<G[x].size();++i){
 55         line &e=edge[G[x][i]];
 56         if (dis[e.to]==dis[x]+1&&(f=dfs(e.to,min(a,e.cap-e.flow)))){
 57             flow+=f;
 58             a-=f;
 59             e.flow+=f;
 60             edge[G[x][i]^1].flow-=f;
 61             if (!a) break;
 62         }
 63     }
 64     return flow;
 65 }
 66 int dinic(){
 67     int ans=0;
 68     while (bfs()){
 69         memset(cur,0,sizeof(cur));
 70         ans+=dfs(S,inf);
 71     }
 72     return ans;
 73 }
 74 int main(){
 75     scanf("%d%d",&n,&m);
 76     for (int i=1;i<=n;++i){
 77         for (int j=1;j<=m;++j){
 78             scanf("%d",&c[i][j]);
 79             tot+=c[i][j];
 80         }
 81     }
 82     S=0; T=n*m+1;
 83     for (int i=1;i<=n;++i){
 84         for (int j=1;j<=m;++j){
 85             int pos=(i-1)*m+j;
 86             if ((i+j)%2) addedge(S,pos,c[i][j]);
 87             else addedge(pos,T,c[i][j]);
 88             for(int k=0;k<4;k++){  
 89                 int xx=i+fx[k][0],yy=j+fx[k][1];  
 90                 if(xx>=1&&xx<=n&&yy>=1&&yy<=m){
 91                     int poss=(xx-1)*m+yy;  
 92                     if((i+j)%2)  
 93                         addedge(pos,poss,inf);  
 94                     else  
 95                         addedge(poss,pos,inf);  
 96                 }  
 97             }  
 98         }
 99     }
100     cout<<tot-dinic();
101     return 0;
102 }

View Code