5 条题解
-
2qiuzanlin LV 9 @ 10 年前
设第i天是否去逛街为a[i],c[i]表示第i天的智商,a[i]=1表示去逛街,a[i]=0表示不去
则可得2n个不等式
a[1]+a[2]+...+a[n]<=k
a[2]+a[3]+...+a[n+1]<=k
...
a[2n+1]+....+a[3n]<=k
求c[1]*a[1]+c[2]*a[2]+...+c[3n]*a[3n]的最大值
添加一个辅助变量
a[1]+a[2]+...+a[n]+y[1]=k
a[2]+a[3]+...+a[n+1]+y[2]=k
...
a[2n+1]+....+a[3n]+y[2n+1]=k
0<=y[i]<=k
将上述不等式相邻两个相减
y[1]+a[1]=a[n+1]+y[2]。。。。。。。。。1
y[2]+a[2]=a[n+2]+y[3]。。。。。。。。。2
......
y[n+1]+a[n+1]=a[2n+1]+y[n+2]。。。。。。。n+1
......
y[2n]+a[2n]=a[3n]+y[2n+1]。。。。。。。。2n
根据网络中每个节点流入量等于流出量的性质
将上述等式编号并抽象成网络中的点,变量a[i]和y[i]抽象为网络中的有向边(弧)
问题等价于求最大费用最大流
以a[n+1]为例 可以看成是节点1部分流出量和节点n+1的部分流入量于是可以建边从n+1到1
故根据这些等式可以建图
设源点为0,汇点为2n+3
i到n+i连一条弧,流量上限为1,费用为c[n+i] 1<=i<=n
i到i+1连一条弧,流量上限为k,费用为0(即为辅助变量y)1<=i<=2n-1
这时发现题目的k还没用上,
于是发现上述等式成立必需满足这两个等式
a[1]+a[2]+...+a[n]+y[1]=k。。。。。2n+1
a[2n+1]+....+a[3n]+y[2n+1]=k。。。。。2n+2
于是建一个节点2n+1
为了满足2n+1式
则由源点向节点2n+1连一条流量上限为k的边,费用为0。
由节点2n+1向i连一条流量上限为1的边,费用为c[i](即为变量a[i])1<=i<=n
由2n+1向1连一条流量上限为k的边,费用为0(即y[1])
同理建一个节点2n+2
为了满足2n+2式则由节点2n+2向汇点连一条流量上限为k的边,费用为0。
由节点i向2n+2连一条流量上限为1的边,费用为ci
建图完毕,剩下就是套算法。 -
16 年前@
我有个不用线性规划的做法,简单费用流。
类似于网络流24题中的最长k可重区间集问题,将每个点拆成
i
和i'
,S
向SS
连容量为k
费用为0
的边,SS
向每个点i
连容量为1
费用为0
的边,每个i
向i'
连容量为1
费用为价值的边,每个i'
向T
连容量为1
费用为0
的边,i'
向[i+n,i+n*3]
中的所有点连容量为1
费用为0
的边,跑最大费用流。代码
-
010 年前@
这一题用线性规划可破。
-
010 年前@
直接网络流
-
010 年前@
我提前发题解了
- 1
信息
- ID
- 1891
- 难度
- 6
- 分类
- (无)
- 标签
- (无)
- 递交数
- 320
- 已通过
- 95
- 通过率
- 30%
- 被复制
- 5
- 上传者