怎样做不用备案的网站,专业沈阳网站制作,国外室内设计网站大全网站,全国最好的装修平台问题描述#xff1a;在一个有m*n 个方格的棋盘中#xff0c;每个方格中有一个正整数。现要从方格中取数#xff0c;使任意2 个数所在方格没有公共边#xff0c;且取出的数的总和最大。试设计一个满足要求的取数算法。编程任务#xff1a;对于给定的方格棋盘#xff0c;按…«问题描述在一个有m*n 个方格的棋盘中每个方格中有一个正整数。现要从方格中取数使任意2 个数所在方格没有公共边且取出的数的总和最大。试设计一个满足要求的取数算法。«编程任务对于给定的方格棋盘按照取数要求编程找出总和最大的数。«数据输入由文件grid.in提供输入数据。文件第1 行有2 个正整数m和n分别表示棋盘的行数和列数。接下来的m行每行有n个正整数表示棋盘方格中的数。 【问题分析】 二分图点权最大独立集转化为最小割模型从而用最大流解决。 【建模方法】 首先把棋盘黑白染色使相邻格子颜色不同所有黑色格子看做二分图X集合中顶点白色格子看做Y集合顶点建立附加源S汇T。 1、从S向X集合中每个顶点连接一条容量为格子中数值的有向边。2、从Y集合中每个顶点向T连接一条容量为格子中数值的有向边。3、相邻黑白格子Xi,Yj之间从Xi向Yj连接一条容量为无穷大的有向边。 求出网络最大流要求的结果就是所有格子中数值之和减去最大流量。 【建模分析】 这是一个二分图最大点权独立集问题就是找出图中一些点使得这些点之间没有边相连这些点的权值之和最大。独立集与覆盖集是互补的求最大点权独立集可以转化为求最小点权覆盖集最小点权支配集。最小点权覆盖集问题可以转化为最小割问题解决。结论:最大点权独立集 所有点权 - 最小点权覆盖集 所有点权 - 最小割集 所有点权 - 网络最大流。 对于一个网络除去冗余点不存在一条ST路径经过的点每个顶点都在一个从S到T的路径上。割的性质就是不存在从S到T的路径简单割可以认为割边关联的非ST节点为割点而在二分图网络流模型中每个点必关联到一个割点否则一定还有增广路当前割不成立所以一个割集对应了一个覆盖集支配集。最小点权覆盖集就是最小简单割求最小简单割的建模方法就是把XY集合之间的变容量设为无穷大此时的最小割就是最小简单割了。 /* * Problem: 线性规划与网络流24题 #9 方格取数问题* Author: Guo Jiabao* Time: 2009.6.27 19:06* State: Solved* Memo: 网络最大流 二分图点权最大独立集
*/
#include iostream
#include cstdio
#include cstdlib
#include cmath
#include cstring
using namespace std;
const int MAXL50,MAXN50*50,MAXMMAXN*8,INF~0U1;
const int dx[]{0,0,-1,1},dy[]{-1,1,0,0};
struct edge
{edge *next,*op;int t,c;
}*V[MAXN],*P[MAXN],ES[MAXM],*Stae[MAXN];
int N,M,S,T,C,EC,Ans,Maxflow,Total;
int Lv[MAXN],Stap[MAXN],Map[MAXL][MAXL];
inline void addedge(int a,int b,int c)
{ES[EC].next V[a]; V[a]ESEC; V[a]-tb; V[a]-cc;ES[EC].next V[b]; V[b]ESEC; V[b]-ta; V[b]-c0;V[a]-op V[b]; V[b]-op V[a];
}
void init()
{int i,j,k,c;freopen(grid.in,r,stdin);freopen(grid.out,w,stdout);scanf(%d%d,M,N);S0; TN*M1;for (i1;iM;i){for (j1;jN;j){scanf(%d,c);Total c;Map[i][j] C;if ((ij)%20)addedge(S,C,c);elseaddedge(C,T,c);}}for (i1;iM;i){for (j1;jN;j){if ((ij)%20){for (k0;k4;k){int xidx[k],yjdy[k];if (x1 xM y1 yN)addedge(Map[i][j],Map[x][y],INF);}}}}
}
bool Dinic_Label()
{int head,tail,i,j;Stap[headtail0]S;memset(Lv,-1,sizeof(Lv));Lv[S]0;while (headtail){iStap[head];for (edge *eV[i];e;ee-next){je-t;if (e-c Lv[j]-1){Lv[j] Lv[i]1;if (jT)return true;Stap[tail] j;}}}return false;
}
void Dinic_Augment()
{int i,j,delta,Stop;for (iS;iT;i)P[i] V[i];Stap[Stop1]S;while (Stop){iStap[Stop];if (i!T){for (;P[i];P[i]P[i]-next)if (P[i]-c Lv[i] 1 Lv[jP[i]-t])break;if (P[i]){Stap[Stop] j;Stae[Stop] P[i];}elseStop--,Lv[i]-1;}else{delta INF;for (iStop;i2;i--)if (Stae[i]-c delta)delta Stae[i]-c;Maxflow delta;for (iStop;i2;i--){Stae[i]-c - delta;Stae[i]-op-c delta;if (Stae[i]-c0)Stop i-1;}}}
}
void Dinic()
{while (Dinic_Label())Dinic_Augment();
}
int main()
{init();Dinic();Ans Total - Maxflow;printf(%d\n,Ans);return 0;
} 转载于:https://www.cnblogs.com/Aragaki/p/7554744.html
