1612方格取数问题
- 格式：doc
- 大小：35.00 KB
- 文档页数：5
方格取数问题
Time Limit:10000MS Memory Limit:128000K
Total Submit:11 Accepted:5
Description
方格取数问题(grid.cpp/c/pas)
【问题描述】
在一个有m*n 个方格的棋盘中，每个方格中有一个正整数。
现要从方格中取数，使任意2 个数所在方格没有公共边，且取出的数的总和最大。
试设计一个满足要求的取数算法。
【编程任务】
对于给定的方格棋盘，按照取数要求编程找出总和最大的数。
Input
由文件grid.in提供输入数据。
文件第1 行有2 个正整数m和n，分别表示棋盘的行数和列数。
接下来的m行，每行有n个正整数，表示棋盘方格中的数。
Output
程序运行结束时，将取数的最大总和输出到文件grid.out中。
Sample Input
3 3
1 2 3
3 2 3
2 3 1
Sample Output
11
Source
线性规划与网络流24题
解法：
先构图，后用最大流算法。
【问题分析】
二分图点权最大独立集，转化为最小割模型，从而用最大流解决。
【建模方法】
首先把棋盘黑白染色，使相邻格子颜色不同，所有黑色格子看做二分图X集合中顶点，白色格子看做Y集合顶点，建立附加源S汇T。
1、从S向X集合中每个顶点连接一条容量为格子中数值的有向边。
2、从Y集合中每个顶点向T连接一条容量为格子中数值的有向边。
3、相邻黑白格子Xi,Yj之间从Xi向Yj连接一条容量为无穷大的有向边。
求出网络最大流，要求的结果就是所有格子中数值之和减去最大流量。
{下面可看可不看}【建模分析】
这是一个二分图最大点权独立集问题，就是找出图中一些点，使得这些点之间没有边相连，这些点的权值之和最大。
独立集与覆盖集是互补的，求最大点权独立集可以转化为求最小点权覆盖集（最小点权支配集）。
最小点权覆盖集问题可以转化为最小割问题解决。
结论:最大点权独立集= 所有点权- 最小点权覆盖集= 所有点权- 最小割集= 所有点权- 网络最大流。
对于一个网络，除去冗余点（不存在一条ST路径经过的点），每个顶点都在一个从S到T 的路径上。
割的性质就是不存在从S到T的路径，简单割可以认为割边关联的非ST节点为割点，而在二分图网络流模型中每个点必关联到一个割点（否则一定还有增广路，当前割不成立），所以一个割集对应了一个覆盖集（支配集）。
最小点权覆盖集就是最小简单割，求最小简单割的建模方法就是把XY集合之间的变容量设为无穷大，此时的最小割就是最小简单割了。
有关二分图最大点权独立集问题，更多讨论见《最小割模型在信息学竞赛中的应用》作者胡伯涛。
var
n,m,del,s,t,sum:longint;
a,b,c:array[0..600,0..600] of longint;
ll:array[1..600] of longint;
lr:array[1..600] of boolean;
success:boolean;
procedure init;
var i,j,x,y:longint;
begin
readln(n,m);
fillchar(a,sizeof(a),0);
fillchar(b,sizeof(b),0);
s:=1; t:=n*m+2; sum:=0; {第一点，构图不是按黑白棋盘来记录} for i:=1 to n do for j:=1 to m do c[i,j]:=m*(i-1)+j+1;
for i:=1 to n do begin
y:=0;
if i mod 2=1 then y:=1;
for j:=1 to m do begin
read(x); sum:=sum+x;
if (y+j) mod 2=0 then begin
a[1,c[i,j]]:=x;
a[c[i,j],c[i-1,j]]:=999999;
a[c[i,j],c[i+1,j]]:=999999;
a[c[i,j],c[i,j-1]]:=999999;
a[c[i,j],c[i,j+1]]:=999999;
end
else a[c[i,j],t]:=x;
end;
end;
end;
function find:longint;
var i:longint;
begin
find:=0;
for i:=1 to t do
if (ll[i]<>0) and lr[i] and (i<=t) then
exit(i);
end;
function ford(var del:longint):boolean;
var i,j,w,min,x:longint;
fillchar(ll,sizeof(ll),0);
fillchar(lr,sizeof(lr),1);
ll[s]:=1; ford:=true;
repeat
i:=find;
if i=0 then exit;
for j:=1 to t do
if (ll[j]=0) and ((a[i,j]>0) or (a[j,i]>0)) then begin
if b[i,j]<a[i,j] then ll[j]:=i;
if b[j,i]>0 then ll[j]:=-i; {第二点这里的b写成a}
end;
lr[i]:=false;
until ll[t]<>0;
w:=t; min:=999999;
repeat
j:=w; w:=abs(ll[j]);
if ll[j]>0 then x:=a[w,j]-b[w,j];
if ll[j]<0 then x:=b[j,w]; {第三点，这里的b写成a}
if x<min then min:=x;
until w=s;
del:=min; ford:=false;
end;
procedure print;
var ans,i,j:longint;
begin
ans:=0;
for i:=1 to t do ans:=ans+b[1,i];
writeln(sum-ans);
end;
procedure change(del:longint);
var w,j:longint;
begin
w:=t;
repeat
j:=w; w:=abs(ll[j]);
if ll[j]>0 then b[w,j]:=b[w,j]+del;
if ll[j]<0 then b[j,w]:=b[j,w]-del; {第四点，这里的j和w对换了} until w=s;
end;
begin
repeat
success:=ford(del);
if success then print
else change(del);
until success;
end.。
