加载中…
个人资料
Mektpoy
Mektpoy
  • 博客等级:
  • 博客积分:0
  • 博客访问:15,146
  • 关注人气:6
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
访客
加载中…
评论
加载中…
博文
KM算法是什么 可以吃么
费用流又是什么 可以吃么

由于非树边必然增加 树边必然减少
不妨给每条边定义个d[i]
如果这条边是树边则表示最终结果该边+d[i] 否则该边-d[i]

根据kruskal的思想, 对于一条非树边(x, y) 它对应树上的路径上的边k需要满足:
w[k] - d[k] <= w[i] + d[i]
(可以思考一下为什么这里还要加等号)
移项得
d[k] + d[i] >= w[k] - w[i]

这样是不是就完了呢?
注意题目要求d[i]必须为整数,但是事实上一定存在(来源请求?)一个最优解使得所有d都为整数。

于是得到了若干约束条件
目标:min{\sum{d[i]}}
其中,任意i有d[i] >= 0

线性规划对偶之后恰好为线性规划标准型,而且显然有初始解0向量,跑单纯形即可。
值得注意的是这题64M的内存限制并不能让我们直接开二维数组,于是把单纯形的矩阵改成map
当这个元素为0的时候不要开它的内存即可。

阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
(2016-09-02 15:40)
现场要是想出来这题现在就黄名了吧…
怪自己没怎么写过上下界网络流。。
当然这题是费用流 不过做法很像上下界网络流的做法

add_edge的形式为(x, y, cap, cost)

类似上下界带源汇的网络流
新增超级源和超级汇
add_edge(t, s, INF, 0)

首先对于原图中的每条边(x, y, c, f)
若f > c
ans += flow - cap
add_edge(y, x, f - c, 0) 退流(可以思考一下为什么这里cost是0)
add_edge(y, x, c, 1) 退流
add_edge(x, y, INF, 2) 增广

若c >= f
add_edge(y, x, f, 1) 退流
add_edge(x, y, c - f, 1) 增广
add_edge(x, y, INF, 2) 增广

然后对于每个点(包括1和n)统计一下离流量守恒还差多少
若还需要流量 则d[i] > 0 否则有多余的流量 d[i] < 0

对于d[i]>0
add_edge(i, t, d[i], 0)
否则
add_edge(s
阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
这题差点把我搞傻了

我一开始考虑的是 既然只限制走一步 那就搞个分层图吧 每个点拆成两个点 然后随手建个最大流

交上去WA了

想了一下,这样建模的话 并没有限制住不攻击的牛 比如说A牛在原地 B牛走到A牛的位置 杀了对方的A'牛
这样是不合法的

于是改成费用流

交上去又WA了

仔细思考发现分两层并没有限制住每个点只能有一头牛的限制
于是会发生这样的情况 A牛在原地杀了A'牛 B牛走到A牛这个格子杀了B'牛 显然这样也是不合法的

于是分了三层

交上去终于AC

但是看了别人的题解发现是直接最大流解决的
事实上牛卡在原地总有等价的方案使得这头牛不卡在原地…
于是最大流就可以了。。

当然如果做原题要输出方案的话 显然费用流会好做一点= =...
阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
逛了逛网上的题解发现基本都没讲清楚 只是把建模写出来。。
所以相信还是有好多同学并不理解为什么要这样建模。。
以及我到现在为止也没弄懂这个入点和出点的拆分方式是什么意思求指教?
以下是我自己的理解:

题目已经要求了我们把点集分成3类

考虑最小割模型

1.损坏 (一个点在s割 一个点在t割 产生代价1)
2.没损坏到不了1点(强制两个点都在t割)
3.没损坏与1联通(强制两个点都在s割)

最小化1类点产生的代价

对于非N点 (不确定属于哪类点)
add_edge(x, x', 1)
产生代价1

对于N点 (属于2类点)
add_edge(x, x', INF)
add_edge(x', t, INF)
强制成为2类点

对于点1 (属于3类点)
add_edge(s, 1, INF)
add_edge(1, 1'
阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
第一眼差点看成网络流。。mdzz

令dp[i][j]为
在i站之前上车 且在i站之后j站之前下车的人
dp[i][j] = sum(a[k <= i][i < l <= j])

设s[i][j]是二维前缀和 有:
dp[i][j] = s[i][j] - s[i][i]

f[k][i] 检查k次票 最后一次票在i和i+1站之间检票

f[k][i] = max(f[k - 1][j] + dp[i][j])

这样就可以输出最小字典序的方案了。
阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
每次暴力交换两个字符
扔到map里去
将每个map视作一个集合。
相当于要写个数据结构支持集合用一个值更新最大值,并且有插入和删除操作
显然可以用splay维护。
可以参考BZOJ 千山鸟飞绝
时间复杂度O(mlogn)

本来以为O(nm)应该给过的,果然太天真了
阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
首先树上k大可以用一个数据结构,找最大然后删掉,重复k次

于是我们可以对每个树上的节点维护一个数据结构
支持:
删掉指定元素
插入元素
查询最大值

显然可以用配对堆。

于是我们写一个lct找最大值,并借助配对堆维护。

O(qklogn)

不要问我配对堆怎么写… 我写的是pb_ds…
阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
显然随便什么树套树都可以做。。
写了个线段树套treap TLE
线段树改成树状数组 TLE
treap改成暴力BST 过了。。
真是blgl
阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
由于n>m
那么n!是m!的倍数
考虑小于等于m!的数里有多少个数与它互质
答案是phi(m!)=m!(1-1/p1)(1-1/p2)...
由于n!是m!的倍数
而gcd(a,b)=gcd(a%b,b)
所以大于m!的数可以映射到小于等于m!的数
ans = phi(m!)*(n!/m!)
对于n!/m!,我的做法是用一个线段树统计
O(N+TlogN)
阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
想了想可以在splay上面二分整体复杂度O(nlogn)于是用LCT水过了 成功rank垫底 比倒数第二还慢两倍233
正解是这样的
离线所有询问 f[i]表示i的答案,那么我们很容易的使用一个路径压缩的并查集就能处理这个东西。
把标记变成不标记 那么pa[i]指向i在树中的父亲
那么f[i]就是findroot(i)
以上纯属口胡,因为我懒得再写一个交了(应该没问题?)。。
阅读  ┆ 评论  ┆ 转载 ┆ 收藏 
  

新浪BLOG意见反馈留言板 不良信息反馈 电话:4006900000 提示音后按1键(按当地市话标准计费) 欢迎批评指正

新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

新浪公司 版权所有