文档章节

【LOJ6045】「雅礼集训 2017 Day8」价(网络流)

o
 osc_fmg49rzg
发布于 2019/03/20 08:15
字数 2022
阅读 14
收藏 0

钉钉、微博极速扩容黑科技,点击观看阿里云弹性计算年度发布会!>>>

点此看题面

大致题意: 有$n$种药,每种药有一个权值,且使用了若干种药材。让你选择若干种药,使得药的数量与所使用的药材并集大小相等,求最小权值总和。

网络流

$hl666$:这种数据范围,一眼网络流!

然后我们两个画了半天硬是想不出一种合适的建图方式。。。

于是就默默打开了题解。。。

可惜题解里讲得都不是很详细,~~蒟蒻我表示难以理解,~~最后想了很久才搞明白为什么要这样做,且这样做为什么对。

因此,我会讲得较为详细一些,把所有让我思考了很久的地方都解释清楚。

建图

考虑从源点向每种药分别连一条容量为$INF$减去其权值的边,然后从每种药向对应的药材,从每种药材向汇点,分别连一条流量为$INF$的边。

然后,我们求出最小割(即跑一遍最大流),并用其减去从源点向外连出的边的容量总和即为答案。

看完是不是一脸懵逼?为什么边权都要设成$INF$级别?为什么这样求出最小割就能求出答案?

让我们先来借助样例,来大致感受一下按照这样建图有什么神奇效果:

此时,原图中的最小割为割去$s->1,s->2,3'->t$,共为$3*INF-10$。

而从源点向外连出的边的容量总和为$3*INF-7$,因此相减得到$-3$,即答案。

是不是感到很神奇?

关于建图的具体解释

接下来,我们来具体解释一下这样建图的好处及作用,也就是这样建图的一些性质。

连接药与药材的边绝不会被选作最小割中的边

考虑到你一个药会向不少于$1$种药材连边,所以连接药与药材的边数显然是大于或等于药材数的。

则你设想如果一条连接药与药材的边被选作了最小割中的边,则显然,割去它没有割去它所连接的药材与汇点的连边更优

原因是这条边只不过是连向该药材的一条边,你割去了这条边,其他边可能依然能流通。而你割去了该药材与汇点的连边,则所有连向该药材的边都断流了。

退一步说,即使没有其他连向该药材的边,考虑到这条边与该药材连向汇点的边流量相同,因此割去这两条边就是等价的,因此依然可以看作是割去了该药材与汇点的连边。

该性质得证。

则我们可由此推知,被选作最小割中的边一定是从源点向某种药的连边从某种药材向汇点的连边

割去一条边的实际意义

接下来,我们来考虑一下割去一条边的实际意义。

由于前面已经证过不会割药与药材的连边,因此这种边略过不提。

对于割掉一条从源点向药的连边,我们考虑到最后要将最小割减去从源点向外连出的边的容量总和,而在这一过程中,这条边的容量就抵消掉了。

因此,割掉一条从源点向药的连边,就相当于不选择这种药

而对于割掉一条从药材连向汇点的连边则恰好相反,表示选择这种药材。

选择的药的数量与药材的数量必定相等

考虑从源点向药连出了$n$条边,从药材向汇点连入了$n$条边,则显然至少需要割$n$条边,且割$n$条边一定可行。

而割去$n$条边的代价必然可以表示成$n*INF+x$,其中$x$为某个未知值。

由于割小于$n$条边不可行,而割大于$n$条边时代价可以表示为$n'*INF+y$,其中$n'>n$,$y$为某个未知值。

将两式相减得到:

$$(n*INF+x)-(n'*INF+y)=(n-n')*INF+x-y$$

由于$INF$是个很大的数,所以上述式子必然小于$0$,因此若要求最小割,割去的边数不可能大于$n$。(这也是我们要把每条边的权值设成$INF$级别的原因)

综上所述,割去的边数必然为$n$。

又由于前面证过的连接药与药材的边绝不会被选作最小割中的边,所以这$n$条边必然由$t$条从源点向药的连边和$n-t$条从药材向汇点的连边组成。

再考虑割去一条边的实际意义,也就是说不选择的药的数量选择的药材的数量相加为$n$。

显然不选择的药的数量选择的药的数量相加也为$n$。

也就是说选择的药的数量与选择的药材的数量必定相等,性质得证。

以此方法能够得到合法答案

考虑前面已经证明过割去的边为$t$条从源点向药的连边和$n-t$条从药材向汇点的连边。

则代价可以表示为$n*INF$减去若干种药的权值。

而从源点向外连出的边的容量总和为$n*INF$减去所有药的权值和。

用代价减去容量总和,$n*INF$抵消,而代价中减去的那些药的权值与容量总和中这部分权值抵消(前面提到过割去一条从源点向药的连边表示不选这种药),剩下的权值负负得正成为其原本的权值。

然后求和即为答案。

以此方法选出的答案必为最优解

这是一个比较显然的性质。

我们求的是最小割,而最后答案是最小割减去容量总和。

既然是最小割,求的肯定是最小解,而答案就是最优解了。

代码

#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 300
#define INF (int)1e9
#define LL long long
using namespace std;
int n;
class FastIO
{
	private:
		#define FS 100000
		#define tc() (A==B&&(B=(A=FI)+fread(FI,1,FS,stdin),A==B)?EOF:*A++)
		#define tn (x<<3)+(x<<1)
		#define D isdigit(c=tc())
		int f;char c,*A,*B,FI[FS];
	public:
		I FastIO() {A=B=FI;}
		Tp I void read(Ty& x) {x=0,f=1;W(!D) f=c^'-'?1:-1;W(x=tn+(c&15),D);x*=f;}
		Ts I void read(Ty& x,Ar&... y) {read(x),read(y...);}
}F;
class MaxFlow//最大流
{
	private:
		#define Psz (N<<1)+2
		#define Lsz (N*N<<1)+(N<<2)
		#define add(x,y,c) (e[++ee].nxt=lnk[x],e[lnk[x]=ee].to=y,e[ee].Cap=c)
		LL Ctot;int ee,lnk[Psz+5],cur[Psz+5],q[Psz+5],dep[Psz+5];
		struct edge {int to,nxt,Cap;}e[Lsz+5];
		I bool BFS()//BFS找增广路
		{
			RI i,k,H=1,T=1;memset(dep,0,sizeof(dep)),dep[q[1]=s]=1;W(H<=T&&!dep[t])
				for(i=lnk[k=q[H++]];i;i=e[i].nxt) e[i].Cap&&!dep[e[i].to]&&(dep[q[++T]=e[i].to]=dep[k]+1);
			return dep[t]?(memcpy(cur,lnk,sizeof(lnk)),true):false;
		}
		I int DFS(CI x,RI f)//DFS统计流量
		{
			if(!(x^t)||!f) return f;RI i,p,res=0;
			for(i=cur[x];i;i=e[i].nxt)
			{
				if(cur[x]=i,(dep[x]+1)^dep[e[i].to]||!(p=DFS(e[i].to,min(f,e[i].Cap)))) continue;
				if(e[i].Cap-=p,e[((i-1)^1)+1].Cap+=p,res+=p,!(f-=p)) break;
			}return !res&&(dep[x]=-1),res; 
		}
	public:
		int s,t;I MaxFlow() {s=1,t=2;}
		I int P1(CI x) {return x+2;}I int P2(CI x) {return x+n+2;}
		I void Add(CI x,CI y,CI c) {add(x,y,c),add(y,x,0),Ctot+=c;}
		I LL GetAns() {Reg LL t=0;W(BFS()) t+=DFS(s,2*INF);return t;}
}M;
int main()
{
	RI i,x,y;Reg LL sum=0;for(F.read(n),i=1;i<=n;++i) for(F.read(x);x;--x) F.read(y),M.Add(M.P1(i),M.P2(y),INF);//建边
	for(i=1;i<=n;++i) F.read(x),M.Add(M.s,M.P1(i),INF-x),M.Add(M.P2(i),M.t,INF),sum+=INF-x;//建边
	return printf("%lld",M.GetAns()-sum),0;
}
o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
2019年3月训练记录(3.01~3.23)

前言 $ZJOI2019$的赛前停课集训在本周开始了(说起来也只上了一周文化课)。 虽说今年省选只是去打酱油的,但还是要好好准备一下的吧! $Mar 1st$ 今天学了一下$NTT$,做了一道较模板的题目:...

osc_bm1l5rx8
2019/03/01
2
0
LOJ_6045_「雅礼集训 2017 Day8」价 _最小割

LOJ6045「雅礼集训 2017 Day8」价 _最小割 描述: 有$n$种减肥药,$n$种药材,每种减肥药有一些对应的药材和一个收益。 假设选择吃下$K$种减肥药,那么需要这$K$种减肥药包含的药材也等于$K$...

osc_yfquc6et
2018/05/10
4
0
loj6045 「雅礼集训 2017 Day8」价

我们考虑最小割。 我一开始觉得是裸的最小割,就直接S到每个减肥药连up+p[i]的边,减肥药到药材连inf边,药材到T连up,然后得到了40分的好成绩。 之后我发现这是一个假的最小割,最小割割的是...

osc_gatdqtjj
2018/04/12
2
0
2019年四月刷题列表

Preface 一轮完挂之后好久没搞OI了(Luogu的$300+$Day打卡都没了QAQ),经过斟酌还是决定走下去吧 但是文化课的坑也开始变大,要同时兼顾三边的话还是感觉力不从心 所以训练强度会比之前下降...

osc_k6lb5e4x
2019/04/08
4
0
ZJOI2019一轮停课刷题记录

Preface 菜鸡HL终于狗来了他的省选停课,这次的时间很长,暂定停到一试结束,不过有机会二试的话还是可以搞到4月了 这段时间的学习就变得量大而且杂了,一般以刷薄弱的知识点和补一些新的奇怪...

osc_r8q2esik
2019/02/27
4
0

没有更多内容

加载失败,请刷新页面

加载更多

聊聊dubbo-go的AccessLogFilter

序 本文主要研究一下dubbo-go的AccessLogFilter AccessLogFilter dubbo-go-v1.4.2/filter/filter_impl/access_log_filter.go type AccessLogFilter struct {logChan chan AccessLogData}......

go4it
27分钟前
24
0
对服务与工厂感到困惑 - Confused about Service vs Factory

问题: As I understand it, when inside a factory I return an object that gets injected into a controller. 据我了解,当在工厂内部时,我返回一个被注入控制器的对象。 When inside a ...

技术盛宴
44分钟前
9
0
OpenCV开发笔记(六十七):红胖子8分钟带你深入了解特征点暴力匹配(图文并茂+浅显易懂+程序源码)

若该文为原创文章,未经允许不得转载 原博主博客地址:https://blog.csdn.net/qq21497936 原博主博客导航:https://blog.csdn.net/qq21497936/article/details/102478062 本文章博客地址:h...

红模仿_红胖子
今天
24
0
将向量附加到向量[重复] - Appending a vector to a vector [duplicate]

问题: This question already has an answer here: 这个问题已经在这里有了答案: Concatenating two std::vectors 22 answers 连接两个std :: vectors 22个答案 Assuming I have 2 standa......

javail
今天
19
0
获得所有文件夹的大小

有两个工具 https://www.getfoldersize.com/ http://www.uderzo.it/main_products/space_sniffer/index.html...

ethanleellj
今天
18
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部