标签:网络流

【题解】 火星探险问题 (网络流24题) 网络流 (LOJ6225) -boshi

火星探险问题

题意:

​ 火星的部分地形可以用一个P*Q的网格表示。登陆舱位于方格(1,1),目标点位于方格(P,Q)。现有k辆探测车从登陆舱出发前往目标点。探测车的坐标不能减小(即x,y均不[......]

[继续阅读= ̄ω ̄=]

Read MoreView 1 Comment

【题解】 「网络流 24 题」方格取数 最大独立集问题 LOJ – 6007

1. 题目

传送门= ̄ω ̄=

2. 题解

这个题是一个很经典的问题:最大点权问题

二分图最大点权独立集问题,就是找出图中一些点,使得这些点之间没有边相连,这些点的权值之和最大。[......]

[继续阅读= ̄ω ̄=]

Read MoreComment

【题解】 「网络流 24 题」试题库 LOJ – 6006

1. 题目

传送门= ̄ω ̄=

2. 题解

感觉没啥好说的,比较水。

  • 从源点到每个类型连一条边,容量为该类型需要的题目数。
  • 从每个类型到该类型对应的每个题目连一条边,容量为1。

  • 从每个题目到汇[......]

[继续阅读= ̄ω ̄=]

Read MoreComment

【算法】 网络流算法之Binic算法 (其实就是Bfs版增广路)

//其实应该是因为常数小所以跑得比较快吧

//但是其实比优化后的Dinic还是慢的,所以dalao可以不用看这篇文章了

//其实写这篇文章主要是因为蒟蒻XZY被骗了所以“作文以记之”

0. 引[......]

[继续阅读= ̄ω ̄=]

Read MoreComment

【题解】 「网络流 24 题」最长递增子序列 Dinic LOJ – 6005

1. 题目

传送门= ̄ω ̄=

2. 题解

建模真奇妙。

(同时这是我打的第一个真·Dinic,以前被骗了一直在打BFS版的增广路算法。。。)

第一问用dp解决就行了。

第二问就得网络流。[......]

[继续阅读= ̄ω ̄=]

Read MoreView 1 Comment

【题解】 「网络流 24 题」圆桌聚餐 网络流 LOJ – 6004

1. 题目

传送门= ̄ω ̄=

2. 题解

前面发了这题的贪心解法,但是毕竟题目没给出总人数限制,所以不严谨。

这里再给出网络流解法吧。

建图的话就是从源点连一条容量为$r_i$的边到第$i$[......]

[继续阅读= ̄ω ̄=]

Read MoreComment

【题解】 「网络流 24 题」太空飞行计划 LOJ – 6001

1. 题目

传送门= ̄ω ̄=

2. 题解

坑了我好久啊。

这题读入太恶心了。

建图方法

  1. 从源点连一条流量为$p_i$的边到第$i$个实验上($p_i$表示第$i$个实验的收益)
  2. 从每个器[......]

[继续阅读= ̄ω ̄=]

Read MoreComment

【题解】 修车 网络流 BZOJ – 1070

1. 题目

传送门= ̄ω ̄=

大意:有$N$个车主,每个车主有1辆车,他们在同一时刻要修车。有$M$个修车的。给出“第i个车给第j个修车的要修多久”。求车主的平均等待时间。等待时间指的是一个车主从[......]

[继续阅读= ̄ω ̄=]

Read MoreComment

【题解】 工作分配问题 最小费用最大流 CODEVS 4893

1. 题目

传送门= ̄ω ̄=
注意!CODEVS数据有误!测试点#4正确答案应该为0!而数据答案是6!需要打表过!

2. 题解

直接上最小费用最大流。

代码:

[crayon-5a61d64[......]

[继续阅读= ̄ω ̄=]

Read MoreComment

【题解】 Going Home 最小费用最大流 HDU – 1533

1. 题目

传送门= ̄ω ̄=

2. 题解

abs大佬太强啦!这题打了170行。。。蒟蒻的3倍啊Orz
此题最小费用最大流模板题,也许能用二分图的最大权匹配做。
abs的题解:http://k-x[......]

[继续阅读= ̄ω ̄=]

Read MoreView 2 Comments