Posted on 四月 6th, 2008.
有史以来做的第一道网络流的题目…用了Dinic,果然好写.原来HopCroft就是简化版的Dinic,有了以前HopCroft的经验,Dinic写起来也就方便的多了.
这道题是裸的网络流,1号节点是源,n号是汇,只要流一下就可以了.
1Y掉,Dinic果然很猛.
附代码,以后Dinic用这个代码套~
{ Drainage Ditches; poj 1273 - sqybi’s code - 最大流 - Dinic}//for my winstyprogram pku1273_sqybi; const nn = 200; mm = 200;
type arr = array[1..nn]of longint;
var n, m, i, x, y, z, s, t, r: longint; head, place, dist: arr; adj, next, f, c: array[-mm..mm]of longint;
function bfs: boolean; var […]
Read Full Post |
Make a Comment ( None so far )
Posted on 四月 6th, 2008.
第一次完成了KM的题目~撒花~
不过还是参考了好多次标程,后面要加强KM的熟练程度~
一定不能再出小毛病…比如把search := false;写做search := true;之类的…
题目第一行输入一个n,表示二分图左右结点分别有n个.
第二行n个数,第i个数xi表示左边第i个结点向右边结点连边时权值为xi^2.
后面n行,第i+2第一个数ki表示左边第i个结点向右边连边的条数,接下来ki个数表示向哪些结点连边.
很裸的KM,随便写写就可以.
附代码.
{
Beloved Sons; SGU 210
- sqybi’s code
- 最大匹配
- KM Kuhn-Munkres
}
//for my winsty
program sgu210_sqybi;
const
fin = ’sgu210.in’;
fout = ’sgu210.out’;
nn = 400;
var
i, j, m, n, x: longint;
b: array[1..nn, 1..nn]of longint;
vx, vy: array[1..nn]of boolean;
a, lx, ly: array[1..nn]of longint;
match: array[1..nn]of longint;
function search(x: longint): boolean;
[…]
Read Full Post |
Make a Comment ( 4 so far )