bzoj 1497 最小割模型
2024-10-21 07:48:49
我们可以对于消费和盈利的点建立二分图，开始答案为所有的盈利和，
那么源向消费的点连边，流量为消费值，盈利向汇连边，流量为盈利值
中间盈利对应的消费连边，流量为INF，那么我们求这张图的最小割，用
开始的答案减去最小割就是答案，因为最小割的存在不是左面就是右面，
割左面，代表建这条路，需要对应的消费，那么割右面代表不要这项盈利，
那本来加进去的盈利应该减掉，所以可以这样更新答案。
/**************************************************************
Problem:
User: BLADEVIL
Language: Pascal
Result: Accepted
Time: ms
Memory: kb
****************************************************************/
//By BLADEVIL
var
n, m :longint;
pre, other, len :array[..] of longint;
last :array[..] of longint;
l :longint;
source, sink :longint;
ans :longint;
que, 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];
last[x]:=l;
other[l]:=y;
len[l]:=z;
end;
procedure init;
var
i :longint;
x, y, z :longint;
begin
read(n,m); source:=n+m+; sink:=source+;
l:=;
for i:= to n do
begin
read(x);
connect(source,i,x);
connect(i,source,);
end;
for i:=n+ to n+m do
begin
read(x,y,z);
connect(x,i,maxlongint div );
connect(i,x,);
connect(y,i,maxlongint div );
connect(i,y,);
connect(i,sink,z);
connect(sink,i,);
ans:=ans+z;
end;
end;
function bfs:boolean;
var
q, p, cur :longint;
h, t :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 (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
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 (len[q]>) and (d[p]=d[x]+) and (rest>) then
begin
tmp:=dinic(p,min(len[q],rest));
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(ans);
end;
begin
init;
main;
end.
最新文章
- 特邀美国EMC实战专家Mark来华授课
- UVALive 7143 Room Assignment（组合数学+DP）（2014 Asia Shanghai Regional Contest）
- 想一想social VR might just work
- ASP.NET MVC 快速开发框架之 SqlSugar+SyntacticSugar+JQWidgetsSugar+jqwidgets
- APN 推送
- SqlSever基础 dateadd month 增加五个月
- 自动抓取java堆栈
- opencv for python 之 突出点检测
- javascript获取url参数的方法
- [Editor(typeof(ImageUrlEditor), typeof(UITypeEditor))]无效的可能原因
- Dubbo使用详解及环境搭建
- 如何使用apktool反编译，查看androidmanifest的内容
- eclipse导包导不进来
- Dynamics 365新特性介绍：在视图中显示图片和提示
- wget 使用
- VUE实现登录然后跳转到原来的页面
- CentOS 7 nginx 1.8.1安装
- BZOJ3926 [Zjoi2015]诸神眷顾的幻想乡 字符串 SAM
- BZOJ3324 : [Scoi2013]火柴棍数字
- 使用boost线程定时器作为后台线程来切换主循环程序状态方法2