一类最小割bzoj2127，bzoj2132 bzoj3438
思考一下我们接触的最小割问题
最小割的基本问题（可能会和图论的知识相结合，比如bzoj1266，bzoj1797）
最大权闭合图（bzoj1497）
最大点权覆盖集，最大点权独立集（bzoj1324）
最近接触到了一类关于最小割新的问题，我也不知道叫什么好
反正它有这么几个特点
每个点都有两种选择的可能性，设为属于S和属于T，属于S有收益a[i],属于T有收益b[i]
两点之间可能因为同在一个或不在同一个集合内产生额外的收益
使收益最大化（废话）
大概就是这个意思，如果看不懂也没关系，我们先从最简单的问题开始分析
首先在满足1的条件下，我们有m对关系，点i和j若同在一个集合，那么就能产生一个额外收益w[i,j];
最终使收益最大化。
对此，我们对于每个点i，我们连s--->i 流量为a[i], i--->t 流量为b[i];
然后对于每对关系(i,j),连i<---j,j--->i 流量都为w[i,j];
然后怎么做呢？根据割的定义，就是s到t没有路
在这里就是，割完之后每个点要么和s连，要么和t连；
我们假如以两个点的图为例，思考一下最小割可能割掉的边（我比较懒，就不发图了）
就会发现，这里的最小割正能使不在一个集合的两个点之间的边被切断
或者使在一个集合的两个点之间的边不被切断
最终ans=∑a[i]+∑b[i]+∑w[i,j]-mincut
这里割对应一种解决问题的方案
好这是最初步，下面就是bzoj2132的问题，
条件2变成了，不在同一个集合里的两点会产生一个额外的收益
我们先按基本问题的方式建图
有了最开始的经验，我们不难猜测，
假如选择一个点集，使其中的点i，颠倒一下使s-->i的流量为b[i],i-->t的流量为a[i];
这样我们再做最小割，不就又变回了最基本的问题吗？
而我们应该怎么选择点集呢？
显然，这个点集内部的点是不能有关系的，并且，这些点是给出关系中一侧的点；
说的明确一点，就是不管S，T，根据关系建得的图G，必须是一个二分图；
那么这道题满不满足呢？
我们对平面图黑白相间染色，显然黑点与白点才会产生关系，
黑点与黑点，白点与白点之间是没有关系——是二分图！
于是这道题就简单了！
const dx:array[..] of integer=(,,,-);
dy:array[..] of integer=(,-,,);
inf=; type node=record
point,next,flow:longint;
end; var edge:array[..] of node;
p,cur,h,numh,pre:array[..] of longint;
c,num:array[..,..] of longint;
s,x,y,i,j,k,n,m,len,t:longint; procedure add(x,y,f:longint);
begin
inc(len);
edge[len].flow:=f;
edge[len].point:=y;
edge[len].next:=p[x];
p[x]:=len;
end; begin
len:=-;
fillchar(p,sizeof(p),);
readln(n,m);
t:=n*m+;
for i:= to n do
for j:= to m do
begin
inc(k);
num[i,j]:=k;
read(x);
s:=s+x;
if (i+j) mod = then //黑白染色
begin
add(,k,x);
add(k,,x);
end
else begin
add(k,t,x);
add(t,k,);
end;
end; for i:= to n do
for j:= to m do
begin
read(x);
s:=s+x;
if (i+j) mod = then
begin
add(num[i,j],t,x);
add(t,num[i,j],x);
end
else begin
add(,num[i,j],x);
add(num[i,j],,);
end;
end;
for i:= to n do
for j:= to m do
read(c[i,j]);
for i:= to n do
for j:= to m do
for k:= to do
begin
x:=i+dx[k];
y:=j+dy[k];
if num[x,y]> then
begin
s:=s+c[i,j];
add(num[i,j],num[x,y],c[i,j]+c[x,y]); //两地建筑物类型不同，增加的额外收益是相互的，一荣俱荣一损俱损
add(num[x,y],num[i,j],);
end;
end;
writeln(s-sap); //求最大流省略
end.
2132
下面再扩展这个问题
条件2变为若点i，j同属于S，增加额外收益为w[i,j],
若点i,j同属于T，增加额外收益为r[i,j]; (这就是bzoj2127）
我们对于每个点i，我们连s--->i 流量为a[i], i--->t 流量为b[i];
显然，之前根据关系的建图方法已经不适用了，我们要思考怎么解决同属于S，同属于T所带来的收益
这必须得回到割的意义上来，我们知道割表示损失，我们取不到的
那我们就来分析一下损失：
1. 当i和j同时属于S的时候，我们损失了r[i,j]
2. 当i和j同时属于T的时候，我们损失了w[i,j]
3. 当i,j属于不同的集合，我们损失了w[i,j]+r[i,j]
这有什么用呢？我们可以换一种方式表达
当i属于S时，损失了r[i,j]/2，当j属于S时，损失了r[i,j]/2
当i属于T时，损失了w[i,j]/2，当j属于T时，损失了w[i,j]/2
这样我们再看3，我们还要在增加(w[i,j]+r[i,j])/2的损失
不难发现，问题又变回了最基本的问题
对于点i，我们增加s--->i 流量为r[i,j]/2，t--->i 流量为w[i,j]/2
对于每对关系(i,j),连i<---j,j--->i 流量都为(w[i,j]+r[i,j])/2;
ans=所有可能收益和-mincut
为了方便，我们可以一开始把流量全乘2，最后再除以2即可
友情提示：这道题不加当前弧优化的sap会TLE
const inf=;
dx:array[..] of integer=(-,,,);
dy:array[..] of integer=(,,-,); type node=record
point,next,flow:longint;
end; var edge:array[..] of node;
d,p,cur,h,numh,pre:array[..] of longint;
a:array[..,..,..] of longint;
num,b,c:array[..,..] of longint;
n,m,t,s,x,i,j,k,len,y:longint; function min(a,b:longint):longint;
begin
if a>b then exit(b) else exit(a);
end; procedure add(x,y,f:longint);
begin
inc(len);
edge[len].point:=y;
edge[len].flow:=f;
edge[len].next:=p[x];
p[x]:=len;
end; function sap:longint;
var tmp,neck,u,i,j,q:longint;
flag:boolean; begin
numh[]:=t+;
u:=;
sap:=;
cur:=p;
neck:=inf;
while h[]<t do
begin
d[u]:=neck;
flag:=false;
i:=cur[u];
while i<>- do
begin
j:=edge[i].point;
if (edge[i].flow>) and (h[u]=h[j]+) then
begin
flag:=true;
neck:=min(neck,edge[i].flow);
cur[u]:=i;
pre[j]:=u;
u:=j;
if u=t then
begin
sap:=sap+neck;
i:=t;
while i<> do
begin
i:=pre[i];
j:=cur[i];
dec(edge[j].flow,neck);
inc(edge[j xor ].flow,neck);
end;
neck:=inf;
u:=;
end;
break;
end;
i:=edge[i].next;
end;
if not flag then
begin
dec(numh[h[u]]);
if numh[h[u]]= then exit;
tmp:=t;
i:=p[u];
q:=;
while i<>- do
begin
j:=edge[i].point;
if (edge[i].flow>) and (h[j]<tmp) then
begin
q:=i;
tmp:=h[j];
end;
i:=edge[i].next;
end;
cur[u]:=q;
h[u]:=tmp+;
inc(numh[h[u]]);
if u<> then
begin
u:=pre[u];
neck:=d[u];
end;
end;
end;
end; begin
readln(n,m);
len:=-;
fillchar(p,sizeof(p),);
t:=n*m+;
for i:= to n do
begin
for j:= to m do
begin
inc(k);
num[i,j]:=k;
read(x);
s:=s+x;
x:=x shl ;
b[i,j]:=b[i,j]+x;
end;
readln;
end;
for i:= to n do
begin
for j:= to m do
begin
read(x);
s:=s+x;
x:=x shl ;
c[i,j]:=c[i,j]+x;
end;
readln;
end; for i:= to n- do
begin
for j:= to m do
begin
read(x);
s:=s+x;
b[i,j]:=b[i,j]+x;
b[i+,j]:=b[i+,j]+x;
a[i,j,]:=a[i,j,]+x;
a[i+,j,]:=a[i+,j,]+x;
end;
readln;
end; for i:= to n- do
begin
for j:= to m do
begin
read(x);
s:=s+x;
c[i,j]:=c[i,j]+x;
c[i+,j]:=c[i+,j]+x;
a[i,j,]:=a[i,j,]+x;
a[i+,j,]:=a[i+,j,]+x;
end;
readln;
end; for i:= to n do
begin
for j:= to m- do
begin
read(x);
s:=s+x;
b[i,j]:=b[i,j]+x;
b[i,j+]:=b[i,j+]+x;
a[i,j,]:=a[i,j,]+x;
a[i,j+,]:=a[i,j+,]+x;
end;
readln;
end; for i:= to n do
begin
for j:= to m- do
begin
read(x);
s:=s+x;
c[i,j]:=c[i,j]+x;
c[i,j+]:=c[i,j+]+x;
a[i,j,]:=a[i,j,]+x;
a[i,j+,]:=a[i,j+,]+x;
end;
readln;
end;
for i:= to n do
for j:= to m do
begin
for k:= to do
begin
x:=i+dx[k];
y:=j+dy[k];
if num[x,y]> then
begin
add(num[i,j],num[x,y],a[i,j,k]); //注意序号的对应
add(num[x,y],num[i,j],);
end;
end;
add(,num[i,j],b[i,j]);
add(num[i,j],,);
add(num[i,j],t,c[i,j]);
add(t,num[i,j],);
end;
writeln(s-sap div );
end.
2127
这个问题最终阶段是bzoj3438 不再是两点间关系而是多点间关系了
即多个点如果同属A集合会产生一个额外收益c1，同属于B集合会产生一个额外收益c2
这就不能用上述的做法了，具体做法见bzoj3438的解题报告
最新文章
- 【RabbitMQ】CentOS安装RabbitMQ，及简单的Java客户端连接
- 功能更强大的格式化工具类 FormatUtils.java
- Delphi 二次开发 CorelDRAW
- [转]使用Xcode和Instruments调试解决iOS内存泄露
- Python正则表达式一
- 并行任务task
- c++ - How to use wstring and wcout to output Chinese words in Xcode? - Stack Overflow
- Android笔记之网络-基本了解
- POJ 3414 Pots(BFS)
- springMVC的拦截器工作流程
- TableView 多余分割线的处理
- java udp服务器设计源码
- STM32 Cube mx 安装
- Ext Js 6+ 如何引入dashboard模版
- VS 2017常用快捷键
- SQL-28 查找描述信息中包括robot的电影对应的分类名称以及电影数目，而且还需要该分类对应电影数量>=5部
- win10和ubuntu16.04双系统Geom Error
- 04-spark streaming
- poj 2828(线段树 逆向思考) 插队是不好的行为
- Android移动应用界面的模板化设计