【带花树专题】
PS:...我还是不懂什么是带花树,就只能套套模板了。
下面是几个带花树的题...目前只能找到这点。
Ural-1099 Work scheduling 难度:*
http://acm.timus.ru/problem.aspx?space=1&num=1099
大意:有N个士兵,每个士兵可以另一个士兵巡逻,给出M组士兵愿意在一起巡逻,求出最大的士兵配置方案。
分析:直接求最大匹配就好了,然后输出所有的组合
ZJU 3316 Game 难度:**
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3316
大意:有N个棋子在棋盘上,2个人轮流拿走一个棋子,第一步可以拿任意一个,而之后每一步必须拿上一步拿走的棋子曼哈顿长度L以内的棋子,问,后手是否能赢
分析:把每一个棋子与周围距离为L的棋子都连上边后,形成一些联通块。易知,一轮游戏只能在某一个联通块里开始直到结束。那么,如果有一个联通块不是完美匹配,先手就可以走那个没被匹配到的点,后手不论怎么走,都必然走到一个被匹配的点上,先手就可以顺着这个交错路走下去,最后一定是后手没有路可走,因为如果还有路可走,这一条交错路,就是一个增广路,必然有更大的匹配。
总结:判断是否是完美匹配。
HDU 3446 daizhenyang's chess 难度:***
http://acm.hdu.edu.cn/showproblem.php?pid=3446
大意:有一个R*C的棋盘,棋盘上有一些格子是幸运的格子,棋盘上只有一个棋子:king。king有一定的走路范围:20个格子如题中图所示。两个人轮流走,每个人可以移动king走到没被走过的幸运的格子上。问,先手是否能赢。
分析:这题与上一题某方面是一样的。都是与增广路有关。把所有能连的边先连上,我们先不算king,求一次匹配。然后我们再算上king,求一次匹配。如果第二次匹配的结果比第一次大,说至少明存在一条增广路,且增广路的起点为king所在的点,那么,我们沿着这条路走下去,最后后手必然无路可走。
总结:2次匹配。
HDU 3551 hard problem 难度:****
http://acm.hdu.edu.cn/showproblem.php?pid=3551
大意:给出一个无向图,并给出一个子图的每个点的度数,问是否能去掉一些边,得到这个子图。
分析:因为我们要求出这样的一个子图,是删去一些边,使其度数减少,所以,我们先把每条边拆成2个点,(u,e)和(e,v),这两个点连一条边,若匹配这条边表示边e(u,v)不被删除,然后我们把每个点拆成deg[i]-D[i]个点(deg[i]为原图度数,D[i]为子图度数),然后对所有该点和他的边(i,e)组成的点连一条边,表示这个点缺少的度数,可以由这儿得到。接着,求匹配,如果是完美匹配,即:每个度数都找到了可以使他减少的边。这个子图可以得到。
总结:让每个需要减少的度数匹配到该点所连接的一条边。
下面是我自己用的带花树的模板,暂时没有出现问题:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 | # include <iostream> # include <stdio.h> # include <string.h> # include <cmath> # include <algorithm> # include <queue> using namespace std; #define MAXE 250 * 250 * 2 #define MAXN 250 #define SET(a,b) memset(a,b,sizeof(a)) deque< int > Q; //g[i][j]存放关系图:i,j是否有边,match[i]存放i所匹配的点 bool g[MAXN][MAXN],inque[MAXN],inblossom[MAXN]; int match[MAXN],pre[MAXN],base[MAXN]; //找公共祖先 int findancestor( int u, int v) { bool inpath[MAXN]={ false }; while ( 1 ) { u=base[u]; inpath[u]= true ; if (match[u]==- 1 ) break ; u=pre[match[u]]; } while ( 1 ) { v=base[v]; if (inpath[v]) return v; v=pre[match[v]]; } } //压缩花 void reset( int u, int anc) { while (u!=anc) { int v=match[u]; inblossom[base[u]]= 1 ; inblossom[base[v]]= 1 ; v=pre[v]; if (base[v]!=anc)pre[v]=match[u]; u=v; } } void contract( int u, int v, int n) { int anc=findancestor(u,v); SET(inblossom, 0 ); reset(u,anc);reset(v,anc); if (base[u]!=anc)pre[u]=v; if (base[v]!=anc)pre[v]=u; for ( int i= 1 ;i<=n;i++) if (inblossom[base[i]]) { base[i]=anc; if (!inque[i]) { Q.push_back(i); inque[i]= 1 ; } } } bool dfs( int S, int n) { for ( int i= 0 ;i<=n;i++)pre[i]=- 1 ,inque[i]= 0 ,base[i]=i; Q.clear();Q.push_back(S);inque[S]= 1 ; while (!Q.empty()) { int u=Q.front();Q.pop_front(); for ( int v= 1 ;v<=n;v++) { if (g[u][v]&&base[v]!=base[u]&&match[u]!=v) { if (v==S||(match[v]!=- 1 &&pre[match[v]]!=- 1 ))contract(u,v,n); else if (pre[v]==- 1 ) { pre[v]=u; if (match[v]!=- 1 )Q.push_back(match[v]),inque[match[v]]= 1 ; else { u=v; while (u!=- 1 ) { v=pre[u]; int w=match[v]; match[u]=v; match[v]=u; u=w; } return true ; } } } } } return false ; } int solve( int n) { SET(match,- 1 ); int ans= 0 ; for ( int i= 1 ;i<=n;i++) if (match[i]==- 1 &&dfs(i,n)) ans++; return ans; } |