Coding MRain , Beta!

网络流算法有许多种,最基本的一种方法是Fold-Fulkerson.不过裸奔的Fold-Fulkerson的效率总是不尽如人意.于是各种优化层出不穷.

比较牛X的一个就是基于分层图思想的MPLA(最短路径增值).在层次图里,从源点开始,不管怎么走,总能走到汇点,而且保证是最短路.这是一个非常优美的性质.复杂度证明...找WC2007王欣上论文吧..

于是便有了以下的裸的MPLA程序(附件1).每次计算出一个层次图.然后进行若干次DFS寻找增广路.

Dinic是基于MPLA上的另外一个改进.引入一个新的名词叫做块流,表示在一张剩余图上所有可增广的流量.Dinic在每次计算出层次图后,仅用一次DFS来找出这张图的块流,避免了许多废的搜索状态和回溯状态.详见程序(附件2).

Read the rest of this entry »

Dinic, 算法, 网络流

昨晚作为第一波下完的(9点左右才下好),赶紧给装上.

采用的是F8的修复计算机安装(我原本用的还是Win7 7000 beta),安装的速度快的惊人啊.

总共只花了十五分钟左右..在我这台07年的本本上.

新装的系统速度快了很多.中文版的..开机的"Starting Windows"变成了"正在启动Windows"

以及..Windows 7 Ultimate变成了Windows 7 旗舰版(这个还是有点儿囧..)

先上截图..

Read the rest of this entry »

Windows 7

- "忘了吧.这样能好受些"

- "你说,忘了那块奶酪,还能再吃到它?"

- "至少你能吃到新的奶酪"

- "我办不到."

- "所以你吃不到奶酪."

以上..看懂沉默.不懂忽略.

我还是办不到.

题目就不多说了..原本是找些线段树的题目来练练手.

结果这题..看起来好水..可以用树状数组切掉..

看到这么水的题目不忍心放弃..就开始随便写..

结果交上去TLE..觉得非常新奇..找了段线段树的程序扔上去AC了.(没天理啊..)

仔细观察题目.才发现..当坐标为0的时候..我可怜的树状数组啊..就开始无限的循环下去了.

还好..赶紧解决..可以把所有坐标加个1..也可以对于0的情况特判.

以下为我AC的程序:

#include <stdio.h>
#include <memory.h>
 
int n,a[15001],b[15001],ans[15001],tree[60000],t;
 
int Query(int a)
{
	if (!a)
		return tree[0];
	int ans = 0;
	while (a)
	{
		ans += tree[a];
		a -= (a & (-a));
	}
	return ans + tree[0];
}
 
void update(int a)
{
	if (!a) { ++ tree[0]; return; }
	while (a <= 32768)
	{
		++ tree[a];
		a += (a & (-a));
	}
}
 
int main()
{
	freopen("input.txt","r",stdin);
	scanf("%d",&n);
	for (int i=1; i<=n; ++i)
		scanf("%d %d",&a[i],&b[i]);
	for (int i=1; i<=n; ++i)
	{
		update(a[i]);
		t = Query(a[i]);
		++ ans[t];
	}
	for (int i=1; i<=n; ++i)
		printf("%d\n",ans[i]);
}

ACM, OI, Ural, 树状数组, 线段树

今天早上省选二试..

一试考差了..活活丢了40分..好吧..我SB.

不过一试只占30%的分数.主要还是看二试.

原本是7:00叫车送我过去的..早上接到电话醒来..6:57..OH MY GOD!

8分钟..起床洗牙刷脸签请假条赶到校门口...(我成神了..?)

7:30差不多赶到三中..

拿到题目.看起来还是有点儿难度的.开始慢慢敲..

旁边的教主比较牛B也比较可怜,瞬间开始切第二题..不过中途流鼻血了...orz..找人要纸巾去.

第三题..没办法..写个简陋的算法打表发现了规律..AC了...(前几天积累的RP还是有用的.)

最后半小时第一题的正确算法闪过脑袋..可是不知道为什么没去写.

好吧..我承认一试对我有些影响..有了第一题那些分数就正好第四名省队了..

怨念着...