做电信宽带合适做网站吗,建设银行官方网首页,巴州移动网站建设,最专业的做音乐网站问题描述#xff1a;在一个有m*n 个方格的棋盘中#xff0c;每个方格中有一个正整数。现要从方格中取数#xff0c;使任意2 个数所在方格没有公共边#xff0c;且取出的数的总和最大。试设计一个满足要求的取数算法。编程任务#xff1a;对于给定的方格棋盘#xff0c;按…«问题描述在一个有m*n 个方格的棋盘中每个方格中有一个正整数。现要从方格中取数使任意2 个数所在方格没有公共边且取出的数的总和最大。试设计一个满足要求的取数算法。«编程任务对于给定的方格棋盘按照取数要求编程找出总和最大的数。«数据输入由文件grid.in提供输入数据。文件第1 行有2 个正整数m和n分别表示棋盘的行数和列数。接下来的m行每行有n个正整数表示棋盘方格中的数。«结果输出:程序运行结束时将取数的最大总和输出到文件grid.out中。输入文件示例 输出文件示例grid.in3 3 1 2 3 3 2 3 2 3 1 grid.out 11 (1N,M30) 对于棋盘黑白染色构出一张二分图二分图最大独立集。 1 #includeiostream2 #includecstdio3 #includealgorithm4 #includevector5 #includecstdlib6 #includecmath7 #includecstring8 using namespace std;9 #define maxn 91010 #define inf 0x7fffffff11 #define llg int 12 #define yyj(a) freopen(a.in,r,stdin),freopen(a.out,w,stdout);13 llg n,m,e[maxn],N,p[10][5],g[50][50],k,tot,se[50][50];14 15 struct DINIC16 {17 vectorllga[maxn],ba[maxn],val[maxn];18 llg dl[maxn],deep[maxn],bj[maxn];19 20 void insert(llg x,llg y,llg z)21 {22 a[x].push_back(y),val[x].push_back(z);23 a[y].push_back(x),val[y].push_back(0);24 ba[x].push_back(a[y].size()-1); ba[y].push_back(a[x].size()-1);25 }26 27 llg dfs(llg x,llg low)28 {29 llg va0,inc0;30 if (xN) return low;31 llg wa[x].size();32 for (llg i0;iw;i)33 if (deep[x]1deep[a[x][i]] val[x][i]0 (vadfs(a[x][i],min(low,val[x][i]))))34 {35 val[x][i]-va; val[a[x][i]][ba[x][i]]va; incva;36 return va;37 }38 if (!inc) deep[x]-1;39 return 0;40 }41 42 void fencen()43 {44 llg x,w,v; deep[0]0;45 memset(bj,0,sizeof(bj));46 llg head0,tail1; dl[1]0; bj[0]1;47 do48 {49 xdl[head]; wa[x].size();50 for (llg i0;iw;i)51 {52 va[x][i];53 if (bj[v] || val[x][i]0) continue;54 dl[tail]v;55 deep[v]deep[x]1; bj[v]1;56 }57 }while (head!tail);58 }59 60 llg dinic()61 {62 llg ans0;63 while (1)64 {65 fencen();66 if (!bj[N]) break;67 ansdfs(0,inf);68 }69 return ans;70 }71 72 void oupt()73 {74 for (llg i1;ik;i)75 {76 printf(%d: ,i);77 llg wa[i].size();78 for (llg e0;ew;e)79 {80 llg va[i][e];81 if (vk vN val[i][e]0) printf(%d ,v-k); 82 }83 printf(\n);84 }85 }86 }G;87 88 llg ma(llg x,llg y) {return x*m-my;}89 90 void init()91 {92 p[1][1]1,p[2][1]-1,p[3][2]1,p[4][2]-1;93 cinnm;94 Nn*m1;95 for (llg i1;in;i)96 for (llg j1;jm;j)97 scanf(%d,g[i][j]),totg[i][j];98 for (llg i1;in;i)99 for (llg j1;jm;j)
100 {
101 for (llg k1;k4;k)
102 {
103 llg xip[k][1],yjp[k][2];
104 if (xn || x1 || ym || y1) continue;
105 se[x][y](se[i][j]1)%2;
106 }
107 }
108 for (llg i1;in;i)
109 for (llg j1;jm;j)
110 if (se[i][j])
111 {
112 for (llg k1;k4;k)
113 {
114 llg xip[k][1],yjp[k][2];
115 if (xn || x1 || ym || y1) continue;
116 G.insert(ma(i,j),ma(x,y),inf);
117 }
118 G.insert(0,ma(i,j),g[i][j]);
119 }
120 for (llg i1;in;i)
121 for (llg j1;jm;j)
122 if (!se[i][j])
123 G.insert(ma(i,j),N,g[i][j]);
124 }
125
126 int main()
127 {
128 yyj(grid);
129 init();
130 couttot-G.dinic();
131 return 0;
132 } 转载于:https://www.cnblogs.com/Dragon-Light/p/6357781.html
