【带花树专题】
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)组成的点连一条边，表示这个点缺少的度数，可以由这儿得到。接着，求匹配，如果是完美匹配，即：每个度数都找到了可以使他减少的边。这个子图可以得到。
总结：让每个需要减少的度数匹配到该点所连接的一条边。
下面是我自己用的带花树的模板，暂时没有出现问题：
#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;
}
2010年9月29日 03:20
好东西，YM~
模板收下了。
2010年10月06日 23:08
@wamaker: 错了别找我
2012年3月01日 21:35
有向图能用吗？
2021年9月21日 20:36
Though the decision is up to you, many people benefit from hiring a site to get the maids they need rather than trying to handle someone themselves. The reason for this is straightforward. You executed someone else who is going to be responsible for ensuring your investment is worthwhile.
2024年11月20日 15:05
Just admiring your work and wondering how you managed this blog so well. It’s so remarkable that I can't afford to not go through this valuable information whenever I surf the internet!
2024年11月20日 15:31
Thanks for sharing nice information with us. i like your post and all you share with us is uptodate and quite informative, i would like to bookmark the page so i can come here again to read you, as you have done a wonderful job.
2024年11月20日 15:39
I’ve been surfing online more than three hours the web will be a lot more useful than ever before.
2024年11月20日 15:40
Thanks for the nice blog. It was very useful for me. I'm happy I found this blog. Thank you for sharing with us,I too always learn something new from your post.
2024年11月20日 15:48
mobile online slots games that can be played for real money No minimum deposit Each game has many interesting things. Whether it's game graphics, background music, rules of play There are also a variety of winning styles and a full range of games to choose from.
2024年11月20日 15:49
Nursing coursework writing services are essential and they have become very popular for those seeking custom nursing research writing services since most of them seek Nursing Assignment Writing Services.
2024年11月20日 16:29
Only aspire to mention ones content get the job done
2024年11月20日 16:30
Students find American History Writing Services as being of great assistance since they are able to complete their American history research paper services and American history assignment writing services on time.
2024年11月20日 16:50
I am overpowered by your post with such a decent theme. Typically I visit your web journals and get refreshed through the data you incorporate yet the present blog would be the most obvious. Well done!
2024年11月20日 17:45
I have a hard time describing my thoughts on content, but I really felt I should here. Your article is really great. I like the way you wrote this information.
2024年11月20日 17:46
I think this is an informative post and it is very beneficial and knowledgeable. Therefore, I would like to thank you for the endeavors that you have made in writing this article. All the content is absolutely well-researched. Thanks...
2024年11月20日 17:55
I am continually amazed by the amount of information available on this subject. What you presented was well researched and well worded in order to get your stand on this across to all your readers
2024年11月20日 17:56
I have added and shared your site to my social media accounts to send people back to your site because I am sure they will find it extremely helpful too.
2024年11月20日 17:58
I am overpowered by your post with such a decent theme. Typically I visit your web journals and get refreshed through the data you incorporate yet the present blog would be the most obvious. Well done!
2024年11月20日 18:10
All the contents you mentioned in post is too good and can be very useful. I will keep it in mind, thanks for sharing the information keep updating, looking forward for more posts.Thanks
2024年11月20日 18:32
An fascinating discussion is value comment. I think that it is best to write extra on this matter, it won’t be a taboo topic however generally people are not enough to talk on such topics. To the next. Cheers
2024年11月20日 18:38
Pretty good post. I just stumbled upon your blog and wanted to say that I have really enjoyed reading your blog posts. Any way I'll be subscribing to your feed and I hope you post again soon. Big thanks for the useful info
2024年11月20日 18:44
mobile online slots games that can be played for real money No minimum deposit Each game has many interesting things. Whether it's game graphics, background music, rules of play There are also a variety of winning styles and a full range of games to choose from.
2024年11月20日 19:01
This is as shown by an overall perspective astounding substance! I have by a wide edge usually around regarded taking a gander at your fixations and have displayed at the genuine that you are ideal concerning wearisome them. You are striking.
2024年11月20日 19:07
"Something is happening in the crowd." It is then captured on the screen of a cart running along the course without a person on it. The cart turns right along the slope and descends.
2024年11月20日 19:45
what i don't comprehended may be very you are presently now not definitely extensively more all around favored than you might be presently. You're extraordinarily clever. You understand along those traces significantly on the subject of this concern, created me as far because it matters for me envision it from such endless extraordinary factors. Its like human beings are not blanketed besides if it is one factor to do with lady loopy! Your person stuffs first rate. Constantly take care of it up! You are very a whole lot favored than you will be at this second.
2024年11月20日 20:18
Skunks are known for their distinctive odor and their tendency to dig under structures, such as porches and decks, in search of food or shelter. Wildlife removal experts must carefully trap and relocate skunks to avoid provoking their defensive spray. Additionally, exclusion methods are employed to block access points and discourage skunks from returning.
2024年11月20日 20:21
It is a good site post without fail. Not too many people would actually, the way you just did. I am impressed that there is so much information about this subject that has been uncovered and you’ve defeated yourself this time, with so much quality. Good Works!
2024年11月20日 20:45
I have a hard time describing my thoughts on content, but I really felt I should here. Your article is really great. I like the way you wrote this information.