首页 > 代码库 > 线性规划与网络流9 方格取数
线性规划与网络流9 方格取数
算法实现题 8-9 方格取数问题（习题 8-20）
?问题描述：
在一个有 m*n 个方格的棋盘中，每个方格中有一个正整数。现要从方格中取数，使任
意 2 个数所在方格没有公共边，且取出的数的总和最大。试设计一个满足要求的取数算法。
?编程任务：
对于给定的方格棋盘，按照取数要求编程找出总和最大的数。
?数据输入：
由文件 input.txt 提供输入数据。文件第 1 行有 2 个正整数 m和 n，分别表示棋盘的行数
和列数。接下来的 m行，每行有 n 个正整数，表示棋盘方格中的数。
?结果输出:
程序运行结束时，将取数的最大总和输出到文件 output.txt 中。
输入文件示例
输出文件示例
input.txt
output.txt
3 3
1 2 3
3 2 3
2 3 1
11
题解：
最大点权独立集=总点权-最小点权覆盖集=总点权-最小割 over……
代码：
1 const inf=maxlongint; 2 type node=record 3 from,go,next,v:longint; 4 end; 5 var tot,i,j,n,m,maxflow,l,r,s,t,x,y,sum:longint; 6 h,head,q,cur:array[0..1000] of longint; 7 e:array[0..50000] of node; 8 num:array[0..50,0..50] of longint; 9 function min(x,y:longint):longint; 10 begin 11 if x<y then exit(x) else exit(y); 12 end; 13 procedure ins(x,y,z:longint); 14 begin 15 inc(tot); 16 e[tot].from:=x;e[tot].go:=y;e[tot].v:=z;e[tot].next:=head[x];head[x]:=tot; 17 end; 18 procedure insert(x,y,z:longint); 19 begin 20 if y>100000 then exit; 21 ins(x,y,z);ins(y,x,0); 22 end; 23 function bfs:boolean; 24 var i,x,y:longint; 25 begin 26 fillchar(h,sizeof(h),0); 27 l:=0;r:=1;q[1]:=s;h[s]:=1; 28 while l<r do 29 begin 30 inc(l); 31 x:=q[l]; 32 i:=head[x]; 33 while i<>0 do 34 begin 35 y:=e[i].go; 36 if (e[i].v<>0) and (h[y]=0) then 37 begin 38 h[y]:=h[x]+1; 39 inc(r);q[r]:=y; 40 end; 41 i:=e[i].next; 42 end; 43 end; 44 exit (h[t]<>0); 45 end; 46 function dfs(x,f:longint):longint; 47 var i,y,used,tmp:longint; 48 begin 49 if x=t then exit(f); 50 used:=0; 51 i:=cur[x]; 52 while i<>0 do 53 begin 54 y:=e[i].go; 55 if (h[y]=h[x]+1) and (e[i].v<>0) then 56 begin 57 tmp:=dfs(y,min(e[i].v,f-used)); 58 dec(e[i].v,tmp);if e[i].v<>0 then cur[x]:=i; 59 inc(e[i xor 1].v,tmp); 60 inc(used,tmp); 61 if used=f then exit(f); 62 end; 63 i:=e[i].next; 64 end; 65 if used=0 then h[x]:=-1; 66 exit(used); 67 end; 68 procedure dinic; 69 begin 70 while bfs do 71 begin 72 for i:=s to t do cur[i]:=head[i]; 73 inc(maxflow,dfs(s,inf)); 74 end; 75 end; 76 procedure init; 77 begin 78 tot:=1; 79 readln(n,m);sum:=0;s:=0;t:=n*m+1; 80 fillchar(num,sizeof(num),60); 81 for i:=1 to n do for j:=1 to m do num[i,j]:=(i-1)*m+j; 82 for i:=1 to n do 83 begin 84 for j:=1 to m do 85 begin 86 read(x);inc(sum,x); 87 if odd(i+j) then insert(s,num[i,j],x) else insert(num[i,j],t,x); 88 end; 89 readln; 90 end; 91 end; 92 procedure main; 93 begin 94 for i:=1 to n do 95 for j:=1 to m do 96 if odd(i+j) then 97 begin 98 insert(num[i,j],num[i,j+1],inf); 99 insert(num[i,j],num[i,j-1],inf);100 insert(num[i,j],num[i-1,j],inf);101 insert(num[i,j],num[i+1,j],inf);102 end;103 maxflow:=0;104 dinic;105 writeln(sum-maxflow);106 end;107 begin108 assign(input,‘grid.in‘);assign(output,‘grid.out‘);109 reset(input);rewrite(output);110 init;111 main;112 close(input);close(output);113 end.
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。