The Fourth Dimension Space

枯葉北風寒，忽然年以殘，念往昔，語默心酸。二十光陰無一物，韶光賤，寐難安；不畏形影單，道途阻且慢，哪曲折，如渡飛湍。斬浪劈波酬壯志，同把酒，共言歡！ -如夢令

統計

隨筆 - 414
文章 - 13
評論 - 521
引用 - 0

常用鏈接

留言簿(16)

隨筆檔案

文章檔案

Blogs in Computer Vision and Algorithm

CMU CV Group

友情鏈接

n皇后問題精彩分析
RMQ問題的精彩文章
開關燈問題

搜索

閱讀排行榜

評論排行榜

whu 帶花樹算法 template ，研究下..

struct Graph {

int n, match[maxn];

bool adj[maxn][maxn];

void clear() {

memset(adj, 0, sizeof(adj));

n = 0;

}

void insert(const int &u, const int &v) {

get_max(n, max(u, v) + 1);

adj[u][v] = adj[v][u] = 1;

}

int max_match() {

memset(match, -1, sizeof(match));

int ans = 0;

for (int i = 0; i < n; ++i) {

if (match[i] == -1) {

ans += bfs(i);

}

return ans;

}

int Q[maxn], pre[maxn], base[maxn];

bool hash[maxn];

bool in_blossom[maxn];

int bfs(int p) {

memset(pre, -1, sizeof(pre));

memset(hash, 0, sizeof(hash));

for (int i = 0; i < n; ++i) {

base[i] = i;

}

Q[0] = p;

hash[p] = 1;

for (int s = 0, t = 1; s < t; ++s) {

int u = Q[s];

for (int v = 0; v < n; ++v) {

if (adj[u][v] && base[u] != base[v] && v != match[u]) {

if (v == p || (match[v] != -1 && pre[match[v]] != -1)) {

int b = contract(u, v);

for (int i = 0; i < n; ++i) {

if (in_blossom[base[i]]) {

base[i] = b;

if (hash[i] == 0) {

hash[i] = 1;

Q[t++] = i;

}

} else if (pre[v] == -1) {

pre[v] = u;

if (match[v] == -1) {

argument(v);

return 1;

} else {

Q[t++] = match[v];

hash[match[v]] = 1;

}

return 0;

}

void argument(int u) {

while (u != -1) {

int v = pre[u];

int k = match[v];

match[u] = v;

match[v] = u;

u = k;

}

void change_blossom(int b, int u) {

while (base[u] != b) {

int v = match[u];

in_blossom[base[v]] = in_blossom[base[u]] = true;

u = pre[v];

if (base[u] != b) {

pre[u] = v;

}

int contract(int u, int v) {

memset(in_blossom, 0, sizeof(in_blossom));

int b = find_base(base[u], base[v]);

change_blossom(b, u);

change_blossom(b, v);

if (base[u] != b) {

pre[u] = v;

}

if (base[v] != b) {

pre[v] = u;

}

return b;

}

int find_base(int u, int v) {

bool in_path[maxn] = {};

while (true) {

in_path[u] = true;

if (match[u] == -1) {

break;

}

u = base[pre[match[u]]];

}

while (!in_path[v]) {

v = base[pre[match[v]]];

}

return v;

}

};

posted on 2010-04-24 16:43 abilitytao 閱讀(884) 評論(2) 編輯收藏引用

# re: whu 帶花樹算法 template ，研究下.. 2010-12-16 20:41 研究下

# re: whu 帶花樹算法 template ，研究下.. 2011-02-23 12:07 tw

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

The Fourth Dimension Space

導航

統計

常用鏈接

留言簿(16)

隨筆檔案

文章檔案

Blogs in Computer Vision and Algorithm

友情鏈接

搜索

最新評論

閱讀排行榜

評論排行榜

whu 帶花樹算法 template ，研究下..

評論

只有注冊用戶登錄后才能發表評論。




網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理