bzoj3438

很容易想到是最小割模型
首先对于一个点i,从s到i连一条容量为ai的边,再从i连一条容量为bi的边到t
然后就是处理附加权的问题了
一开始受到之前的思维定势的影响,一直在思考怎么在作物之间连边
由于每种额外收益对应多种作物,而不再是原来bzoj2132的二元关系最小割,这是不行的
所以我们考虑可以把一种组合作物方式看成一个两点u,v,表示同时种在一个A、B田里的两种情况
对于u,我们连边s-->u 容量为c1,再从u向对应每种作物连一条容量inf的边
对于v,我们连边v-->t 容量为c2,再从对应每个作物向v连一条容量inf的边(组合方式是固定的,这些边当然不能割去)
不难发现,做最小割后s-->u,v-->t的容量不能同时保存,
且同时假设保留s-->u 那么对应作物与t的连边一定被割去,相当于对应作物都种在A地中
保留v-->t同理,所以这样建图做最小割是正确的
最终ans=所有收益-mincut

还有种想法我觉得更好的是做最大权闭合子图
首先我们把所有作物都种在A田地里,然后再通过调整选一些作物种在B里取得最优答案
我们把每个额外收益看作一个点,点权为c2-c1,每个作物的点权为bi-ai;
要选取某个作物组合改成种在B里,那么必然所对应的作物也都要种在B里
这就相当于选择一个点集,其中每个点的指向的点也在点集中,使这样一个点权和最大
很容易想到是一个最大权闭合子图问题,最大权闭合子图的做法具体见bzoj1497,这里就不多说
这种调整思路和判断混合图欧拉回路颇有异曲同工之妙

这里采用的是第一种方法

 const inf=;
type node=record
next,flow,point:longint;
end; var edge:array[..] of node;
p,numh,h,d,cur,pre:array[..] of longint;
t,x,y,k,i,j,n,m,len,a,s: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 i,j,q,tmp,u,neck:longint;
begin
sap:=;
fillchar(h,sizeof(h),);
numh[]:=t+;
for i:= to t do
cur[i]:=p[i];
u:=;
sap:=;
neck:=inf;
while h[]<t+ do
begin
d[u]:=neck;
i:=cur[u];
while i<>- do
begin
j:=edge[i].point;
if (edge[i].flow>) and (h[u]=h[j]+) then
begin
pre[j]:=u;
cur[u]:=i;
neck:=min(neck,edge[i].flow);
u:=j;
if u=t then
begin
sap:=sap+neck;
while u<> do
begin
u:=pre[u];
j:=cur[u];
dec(edge[j].flow,neck);
inc(edge[j xor ].flow,neck);
end;
neck:=inf;
end;
break;
end;
i:=edge[i].next;
end;
if i=- then
begin
dec(numh[h[u]]);
if numh[h[u]]= then exit;
q:=-;
tmp:=t;
i:=p[u];
while i<>- do
begin
j:=edge[i].point;
if edge[i].flow> then
if h[j]<tmp then
begin
q:=i;
tmp:=h[j];
end;
i:=edge[i].next;
end;
h[u]:=tmp+;
cur[u]:=q;
inc(numh[h[u]]);
if u<> then
begin
u:=pre[u];
neck:=d[u];
end;
end;
end;
end; begin
len:=-;
fillchar(p,sizeof(p),);
readln(n);
for i:= to n do
begin
read(x);
s:=s+x;
add(,i,x);
add(i,,);
end;
readln;
for i:= to n do
begin
read(h[i]);
s:=s+h[i];
end;
readln(m);
t:=m*+n+;
for i:= to n do
begin
add(i,t,h[i]);
add(t,i,);
end;
for i:= to m do
begin
read(k,x,y);
s:=s+x+y;
add(,i+n,x);
add(i+n,,);
add(i+n+m,t,y);
add(t,i+n+m,);
for j:= to k do
begin
read(a);
add(i+n,a,inf);
add(a,i+n,);
add(a,i+n+m,inf);
add(i+n+m,a,);
end;
readln;
end;
writeln(s-sap);
end.
上一篇:python爬虫之採集——360联想词W2版本号


下一篇:iOS-数据解析XML解析的多种平台介绍