首页 > 代码库 > 【codevs1907】方格取数3(最大流最小割定理)
【codevs1907】方格取数3(最大流最小割定理)
网址:http://codevs.cn/problem/1907/
题意:在一个矩阵里选不相邻的若干个数,使这些数的和最大。
我们可以把它看成一个最小割,答案就是矩阵中的所有数-最小割。先把矩阵按国际象棋棋盘黑白染色(即把相邻的点分别染成白色和黑色),然后黑点连源点,白点连汇点。割掉一个点到源/汇的边就是不选择这个点,最后的目的就是使源到汇不连通(不引发题目不能选择位置相邻的数的矛盾)。
然而最小割怎么求呢?
于是我们就要引入一个定理:最大流最小割定理。它的意思就是说,在一个图中,a点到b点的最小割=a到b的最大流。
然而我并不会证……这里口胡一个想法:最大流就是沿着剩余网络不断地流,每流一次相当于删掉剩余网络的一条边,流到不能流为止。而最小割也是不断地割直到不连通。于是最小割=最大流。
答案就这样变成了求最大流。
具体怎么建图,就是把黑/白点到源/汇的边的流量定为这个位置的上数,而黑白点之间的边,因为不能把它割掉,所以把它的流量设为一个极大数。
于是就过了。
代码:
var a:array[0..1010,0..1010]of longint; s:array[0..50,0..50]of longint; l,q:array[0..1010]of longint; n,m,nn,i,j,k,h,t:longint; ans,sum:int64; function num(x,y:longint):longint; begin exit((x-1)*m+y); end; function dfs(now,ll:longint):longint; var p,i:longint; begin if now=nn then exit(ll); for i:=1 to nn do if(a[now,i]>0)and(l[i]=l[now]+1)then begin if a[now,i]<ll then p:=dfs(i,a[now,i]) else p:=dfs(i,ll); a[now,i]:=a[now,i]-p; a[i,now]:=a[i,now]+p; if p>0 then exit(p); end; exit(0); end; begin read(n,m); sum:=0; for i:=1 to n do for j:=1 to m do begin read(s[i,j]); sum:=sum+s[i,j]; end; fillchar(a,sizeof(a),0); for i:=1 to n do for j:=1 to m do if (i+j)and 1=0 then a[num(i,j),n*m+1]:=s[i,j] else begin if i>1 then a[num(i,j),num(i-1,j)]:=1<<25; if i<n then a[num(i,j),num(i+1,j)]:=1<<25; if j>1 then a[num(i,j),num(i,j-1)]:=1<<25; if j<m then a[num(i,j),num(i,j+1)]:=1<<25; a[0,num(i,j)]:=s[i,j]; end; nn:=n*m+1; ans:=0; while true do begin fillchar(l,sizeof(l),0); h:=1; t:=1; q[1]:=0; l[0]:=1; repeat for i:=1 to nn do if(a[q[h],i]>0)and(l[i]=0)then begin inc(t); q[t]:=i; l[i]:=l[q[h]]+1; end; inc(h); until h>t; if l[nn]=0 then break; repeat k:=dfs(0,1<<25); ans:=ans+k; until k=0; end; writeln(sum-ans); end.
【codevs1907】方格取数3(最大流最小割定理)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。