bzoj 1066 最大流
2024-08-28 18:21:39
将每个石柱拆成两个点，分别是进入的和出去的，两个点之间连石柱的高度
然后每个出去的点连别的石柱的进去的点，
源点连所有蜥蜴所在柱子，每个能跳出去的连汇点，然后最大流就行了
/**************************************************************
Problem:
User: BLADEVIL
Language: Pascal
Result: Accepted
Time: ms
Memory: kb
****************************************************************/
//By BLADEVIL
var
r, c, d :longint;
map, jump :array[..,..] of char;
pre, other, len :array[..] of longint;
last :array[..] of longint;
num :array[..,..] of longint;
source, sink :longint;
l :longint;
que, dis :array[..] of longint;
ans, sum :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];
last[x]:=l;
other[l]:=y;
len[l]:=z;
end;
procedure init;
var
i, j, ii, jj :longint;
k :longint;
begin
readln(r,c,d); l:=;
for i:= to r do
begin
for j:= to c do
read(map[i,j]);
readln;
end;
for i:= to r do
begin
for j:= to c do read(jump[i,j]);
readln;
end;
for i:= to r do
for j:= to c do num[i,j]:=c*(i-)+j;
source:=*r*c+; sink:=source+;
for i:= to r do
for j:= to c do
if jump[i,j]='L' then
begin
connect(source,num[i,j],);
connect(num[i,j],source,);
inc(sum);
end;
for i:= to r do
for j:= to c do
if map[i,j]<>'' then
begin
for ii:= to r do
for jj:= to c do
//if (i<>ii) or (j<>jj) then
begin
if (sqrt((i-ii)*(i-ii)+(j-jj)*(j-jj))<=d) then
begin
connect(num[i,j]+r*c,num[ii,jj],maxlongint div );
connect(num[ii,jj],num[i,j]+r*c,);
end;
end;
end;
for i:= to d do
for j:= to c do
if map[i,j]<>'' then
begin
connect(num[i,j]+r*c,sink,maxlongint div );
connect(sink,num[i,j]+r*c,);
end;
for i:=r-d+ to r do
for j:= to c do
if map[i,j]<>'' then
begin
connect(num[i,j]+r*c,sink,maxlongint div );
connect(sink,num[i,j]+r*c,);
end;
for i:= to r do
for j:= to d do
if map[i,j]<>'' then
begin
connect(num[i,j]+r*c,sink,maxlongint div );
connect(sink,num[i,j]+r*c,);
end;
for i:= to r do
for j:=c-d+ to c do
if map[i,j]<>'' then
begin
connect(num[i,j]+r*c,sink,maxlongint div );
connect(sink,num[i,j]+r*c,);
end;
for i:= to r do
for j:= to c do
if map[i,j]<>'' then
begin
k:=ord(map[i,j])-;
connect(num[i,j],num[i,j]+r*c,k);
connect(num[i,j]+r*c,num[i,j],);
end;
end;
function bfs:boolean;
var
h, t, cur :longint;
q, p :longint;
begin
fillchar(dis,sizeof(dis),);
h:=; t:=;
que[]:=source; dis[source]:=;
while h<t do
begin
inc(h);
cur:=que[h];
q:=last[cur];
while q<> do
begin
p:=other[q];
if (len[q]>) and (dis[p]=) then
begin
inc(t);
que[t]:=p;
dis[p]:=dis[cur]+;
if p=sink then exit(true);
end;
q:=pre[q];
end;
end;
exit(false);
end;
function dinic(x,flow:longint):longint;
var
tmp, rest :longint;
q, p :longint;
begin
if x=sink then exit(flow);
rest:=flow;
q:=last[x];
while q<> do
begin
p:=other[q];
if (dis[x]=dis[p]-) and (len[q]>) 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;
begin
while bfs do
ans:=ans+dinic(source,maxlongint div );
writeln(sum-ans);
end;
begin
init;
main;
end.
最新文章
- （gridcontrol等)通用导出excel z
- TextView属性大全
- android adb应用
- NGUI学习笔记-UISprite
- C#- 将秒数转化成任意时间格式
- Using Notepad++ to Execute Oracle SQL
- （转） 将VB.NET网站转换成C#的全过程
- CentOS下JAVA WEB 环境搭建
- <Video> in HTML5
- [maven] 新建项目一直提示loading archetype list
- MySQL 批量导入 csv 文件
- Natas Wargame Level 12 Writeup（文件上传漏洞）
- VR全景智慧城市：360全景市场需要背景及其优势~
- 2、转载一篇，浅析人脸检测之Haar分类器方法
- gcc创建静态库和共享库
- Redis五大数据类型的常用操作
- Java 学习笔记 两大集合框架Map和Collection
- kafka笔记9（监控）
- ArgumentOutOfRangeException: 指定的参数已超出有效值的范围。 参数名: site
- Struts2学习（五）———— s标签和国际化