UVA1104 芯片难题 Chips Challenge 题解

Description

题目链接

有一个 $N \times N$ 的棋盘,可以在上面放棋子。

有些格子不能放棋子,有些格子必须放棋子,剩下的格子随意。

要求放好棋子之后满足如下两条要求:

  1. 第 $i$ 行和第 $i$ 列的棋子数目必须一样多。$(1\leq i \leq N)$
  2. 第 $i$ 行的棋子数目不能超过总的棋子数目的 $\frac{A}{B}$。$(1\leq i \leq N)$

求最多可以另外放多少个棋子(就是除掉必须放的)。如果无解输出 impossible

$1\leq N \leq 40,1\leq A\leq B\leq 1000$

Solution

我们可以考虑补集思想。

考虑如果一开始把所有可以放的格子不管三七二十一都放上棋子。

那么题目就转化为至少从中除掉多少个棋子,使其满足题目条件

但问题来了,我们既不知道棋子的总个数,也不知道每一行的个数。

既然是要求最少,那么我们可以先枚举每一行最多的棋子的个数,然后跑一遍费用流,计删掉一个棋子的花费为 $i$,那么问题就转化为求最小费用最大流。

考虑如何建图,

首先将超级源点 $S$ 连向 $i$ 一条流量为 $sumx[i]$(表示该行的可以放的棋子数量),费用为 $0$ 的边,表示该行一开始就可以有 $sumx[i]$ 个棋子。

再将每一列 $i+n$ 连向超级汇点 $T$ 一条流量为 $sumy[i]$,费用为 $0$ 的边,表示该列最多可以放置 $sumy[i]$。

然后将每一行 $i$ 与对应的列 $i+n$ 连一条流量为 $flow$(表示枚举到的对多流量),费用为 $0$ 的边,表示每一行每一列的放置棋子的个数应该相等。

然后考虑如果第 $i$ 行 $j$ 列是 '.',表示可以放也可以不放,那么我们就可以 $i$ 连一条 $j+n$ 的边,流量为 $1$,费用为 $1$。

Code

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇