bzoj 1565 最大权闭合子图
2024-10-14 22:51:52
因为每个植物都有保护的点(每排相邻的右面的算是保护左面的),所以连他和保护
的点一条边,然后每个点有自己的权值,要找到最大的权值且满足每个点在访问时他
的前驱一定被访问,那么反向建边,转化为后继必须访问,即求一个
最大权闭合子图,然后转化为网络流最小割模型求解。。
然后因为成环的点肯定不会被毁掉,所以直接删了,可以由拓扑排序得出,可以提高速度
然后因为成环的点肯定不会被毁掉,所以直接删了,可以由拓扑排序得出,可以提高速度
然后我还是tle了。。。有个480A的码,明儿看看啥意思吧。。。
/**************************************************************
Problem:
User: BLADEVIL
Language: Pascal
Result: Time_Limit_Exceed
****************************************************************/
//By BLADEVIL
var
n, m :longint;
num :array[..,..] of longint;
key :array[..,..] of longint;
sum :array[..] of longint;
flag :array[..] of boolean;
que :array[..] of longint;
other, len, pre, succ :array[..] of longint;
l :longint;
last :array[..] of longint;
source, sink :longint;
ans :longint;
d :array[..] of longint;
function min(a,b:longint):longint;
begin
if a>b then min:=b else min:=a;
end;
procedure connect(x,y,z:longint);
begin
inc(l);
pre[l]:=last[x];
succ[pre[l]]:=l;
last[x]:=l;
other[l]:=y;
len[l]:=z;
end;
procedure topo_sort;
var
h, t, q, p :longint;
i :longint;
cur :longint;
begin
h:=; t:=;
for i:= to num[n-,m-] do
if sum[i]= then
begin
inc(t);
que[t]:=i;
end;
while h<t do
begin
inc(h);
cur:=que[h];
q:=last[cur];
flag[cur]:=true;
while q<> do
begin
p:=other[q];
if len[q]= then
begin
dec(sum[p]);
if sum[p]= then
begin
inc(t);
que[t]:=p;
end;
end;
q:=pre[q];
end;
end;
end;
procedure init;
var
i, j, k :longint;
x, y, cur :longint;
q, p :longint;
begin
read(n,m);l:=;
for i:= to n- do
for j:= to m- do
num[i,j]:=i*m+j+;
for i:= to n- do
for j:= to m- do
begin
read(key[i,j]);
read(cur);
for k:= to cur do
begin
read(x,y);
connect(num[i,j],num[x,y],);
inc(sum[num[x,y]]);
connect(num[x,y],num[i,j],maxlongint);
end;
end;
for i:= to n- do
for j:= to m- do
begin
connect(num[i,j],num[i,j-],);
inc(sum[num[i,j-]]);
connect(num[i,j-],num[i,j],maxlongint);
end;
topo_sort;
for i:= to num[n-,m-] do
if not flag[i] then
begin
q:=last[i];
while q<> do
begin
p:=q xor ;
if succ[p]<> then pre[succ[p]]:=pre[p];
succ[pre[p]]:=succ[p];
q:=pre[q];
end;
end;
end;
function bfs:boolean;
var
q, p :longint;
h, t :longint;
cur :longint;
begin
fillchar(d,sizeof(d),);
h:=; t:=;
d[source]:=;
que[]:=source;
while h<t do
begin
inc(h);
cur:=que[h];
q:=last[cur];
while q<> do
begin
p:=other[q];
if (flag[p]) and (len[q]>) and (d[p]=) then
begin
inc(t);
que[t]:=p;
d[p]:=d[cur]+;
if p=sink then exit(true);
end;
q:=pre[q];
end;
end;
exit(false);
end;
function dinic(x,flow:longint):longint;
var
q, p :longint;
tmp, rest :longint;
begin
if x=sink then exit(flow);
rest:=flow;
q:=last[x];
while q<> do
begin
p:=other[q];
if (len[q]>) and (flag[p]) and (d[x]+=d[p]) and (rest>) then
begin
tmp:=dinic(p,min(rest,len[q]));
dec(rest,tmp);
dec(len[q],tmp);
inc(len[q xor ],tmp);
end;
q:=pre[q];
end;
exit(flow-rest);
end;
procedure main;
var
i, j :longint;
begin
source:=num[n-,m-]+; sink:=source+;
for i:= to n- do
for j:= to m- do
if flag[num[i,j]] then
if key[i,j]> then
begin
inc(ans,key[i,j]);
connect(source,num[i,j],key[i,j]);
connect(num[i,j],source,);
end else
begin
connect(num[i,j],sink,-key[i,j]);
connect(sink,num[i,j],);
end;
flag[sink]:=true; flag[source]:=true;
while bfs do ans:=ans-dinic(source,maxlongint);
if ans> then writeln(ans) else writeln();
end;
begin
init;
main;
end.
最新文章
- JS案例之7——瀑布流布局(2)
- C函数tolower,与toupper
- Motorola C118修改滤波器组件
- 黑马程序员——JAVA基础之多线程的线程间通讯等
- 慕课网-安卓工程师初养成-4-9 Java循环语句之 for
- PowerDesigner15.1创建模型及生成带注释sql操作手册
- Bluebird-Collections
- MySQL5.0版本的安装图解教程
- service redis does not support chkconfig的解决办法
- Android 当打开“开发人员模式”中的“不保留活动”后,程序应当怎么保持正常执行
- 【bzoj2131】免费的馅饼 dp+树状数组
- python day27--网络编程
- Self-Introduce
- JAVA项目工具包集合
- jQ live用法
- leetcode242
- Typescript declaration: Merge a class and an interface
- 【BZOJ1956】[Ahoi2005]SHUFFLE 洗牌
- 学习记录jQuery的animate函数
- 160519、Oracle中将查询出的多条记录的某个字段拼接成一个字符串的方法