Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:数据有点问题(附Stoer-wagner详解)

Posted by chr32 at 2014-12-20 15:07:48 on Problem 2914
In Reply To:数据有点问题(附Stoer-wagner详解) Posted by:Sona at 2009-04-20 23:27:43
> 原来一个很明显的错误程序,样例都通过不了,都AC了。。。
> 
> //这是那个论文,转载
> 
> 最小割 Stoer-Wagner 算法 
> Etrnls 2007-4-15 
> Stoer-Wagner 算法用来求无向图 G=(V, E)的全局最小割。 
>  
> 算法基于这样一个定理:对于任意s, t   V ∈ ,全局最小割或者等于原图的s-t 最小割,或者等于将原图进行 Contract(s, 
> t)操作所得的图的全局最小割。 
>  
> 算法框架: 
> 1. 设当前找到的最小割MinCut 为+∞  
> 2. 在 G中求出任意 s-t 最小割 c,MinCut = min(MinCut, c)   
> 3. 对 G作 Contract(s, t)操作,得到 G'=(V', E'),若|V'| > 1,则G=G'并转 2,否则MinCut 为原图的全局最
> 小割  
>  
> Contract 操作定义: 
> 若不存在边(p, q),则定义边(p, q)权值w(p, q) = 0 
> Contract(a, b): 删掉点 a, b 及边(a, b),加入新节点 c,对于任意 v  V ∈ ,w(v, c) = w(c, v) = w(a, v) + w(b, 
> v) 
>  
> 求 G=(V, E)中任意 s-t 最小割的算法: 
> 定义w(A, x) = ∑w(v[i], x),v[i]  A ∈  
> 定义 Ax 为在x 前加入 A 的所有点的集合(不包括 x)  
> 1. 令集合 A={a},a为 V中任意点  
> 2. 选取 V - A中的 w(A, x)最大的点 x加入集合 A  
> 3. 若|A|=|V|,结束 
> 令倒数第二个加入 A的点为 s,最后一个加入 A的点为 t,则s-t 最小割为 w(At, t) 
> 

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator