电子商务类网站建设实训报告,辽宁建设工程信息网 管网,前端开发工程师是什么专业,wordpress循环调用最新文章看了两篇博客#xff0c;觉得写得不错#xff0c;便收藏之。。 首先是第一篇#xff0c;转自某Final牛 带花树……其实这个算法很容易理解#xff0c;但是实现起来非常奇葩#xff08;至少对我而言#xff09;。 除了wiki和amber的程序我找到的资料看着都不大靠谱 比如昨… 看了两篇博客觉得写得不错便收藏之。。 首先是第一篇转自某Final牛 带花树……其实这个算法很容易理解但是实现起来非常奇葩至少对我而言。 除了wiki和amber的程序我找到的资料看着都不大靠谱 比如昨晚找到一篇鄙视带花树的论文然后介绍了一种O(E)的一般图最大匹配……我以为找到了神论文然后ACM_DIY众神纷纷表示这个是错的……于是神论文成为了”神论文“…… 又比如围观nocow上带花树标程一看……这显然是裸的匈牙利算法……货不对板啊 当然……如果二分图的匈牙利算法还不会请先围观求二分图最大匹配的匈牙利算法。 实际上任意图求最大匹配也是找增广路但是由于奇环的出现找增广路变得困难。 首先明确一点增广路上是不能有重复出现的点的。 二分图中匹配边可以看作是有向的比如定义总是从X集指向Y集。假若定义了起点必须在X集中那么增广路中出现该匹配边时必然是按照这个方向的。所以一个点在增广路中的奇偶性是确定的。 而这个图中从增广路3-1-4-5和2-4-1-6可以看出对于有奇环的任意图1和4这两个点在增广路中所在位置的奇偶性不再一定。于是我们考虑处理这些奇环。 定义奇环包含2k1个点和k条匹配边的一个环。如果不是这样我们找增广路不会走上去 对于这个奇环k条匹配覆盖了2k个点那么显然有一个点未被覆盖。我们拿出这个点来讨论。 比如图中的1号点就是这个这个特殊的点。除了这个点以外其它的点都被覆盖了所以只能向外连非匹配边而1号点可以向外连匹配边或非匹配边。 如果1号点没有被外面的点匹配那么无论从其它的哪个点走进来都能以1为终点找到增广路。(要么顺时针跑到1要么逆时针) 同理如果1号点被外面的点匹配了那么无论从其它的哪个点走进来都能把这个圈看成一个点然后从1的那条匹配边穿出去。(要么顺时针要么逆时针) 于是这个奇环就可以看成一个点其主要特性由1号点体现(诸如和谁匹配了之流)。 这个合成点就叫做花。这个算法的思想就是不断地把奇环合成点直至找到增广路合成了某朵花以后就把整朵花当成一个点。 考虑用BFS搜索增广路。 围观wiki这个图 由于BFS的性质我们找到奇环只能是和同层的点或者下下一层的点。 然后奇环的关键点必然是这棵BFS树里深度最浅的点。然后考虑合成以后花如何展开对应的路径使得我们能够增广。 花套花这个东西想起来都纠结_。 amber的程序里面并没有把点真的合成只是弄了一个表示集合的标号Base然后邻接矩阵就不用变来变去了。 对于花中连向父亲的是匹配边的点他的增广路显然是直接顺着父亲走而如果连向父亲的边是非匹配边的点那么显然是往后走然后跑过红色的横插边然后再向上跑回关键点。 注意到如果连向父子的边是匹配边的点原先是不需要Father这个域来描述的直接用表示匹配的那个域就可以了。但是现在在花中他的Father这个域就要起作用了用来向后指向然后绕过红色横插边然后再跑回关键点。 实在是太精妙了。 1 //Problem:http://acm.timus.ru/problem.aspx?space1num10992 #include cstdio3 #include cstdlib4 #include cstring5 #include iostream6 #include algorithm7 using namespace std;8 const int N250;9 int n;10 int head;11 int tail;12 int Start;13 int Finish;14 int link[N]; //表示哪个点匹配了哪个点15 int Father[N]; //这个就是增广路的Father……但是用起来太精髓了16 int Base[N]; //该点属于哪朵花17 int Q[N];18 bool mark[N];19 bool map[N][N];20 bool InBlossom[N];21 bool in_Queue[N];22 23 void CreateGraph(){24 int x,y;25 scanf(%d,n);26 while (scanf(%d%d,x,y)!EOF)27 map[x][y]map[y][x]1;28 }29 30 void BlossomContract(int x,int y){31 fill(mark,markn1,false);32 fill(InBlossom,InBlossomn1,false);33 #define pre Father[link[i]]34 int lca,i;35 for (ix;i;ipre) {iBase[i]; mark[i]true; }36 for (iy;i;ipre) {iBase[i]; if (mark[i]) {lcai; break;} } //寻找lca之旅……一定要注意iBase[i]37 for (ix;Base[i]!lca;ipre){38 if (Base[pre]!lca) Father[pre]link[i]; //对于BFS树中的父边是匹配边的点Father向后跳39 InBlossom[Base[i]]true;40 InBlossom[Base[link[i]]]true;41 }42 for (iy;Base[i]!lca;ipre){43 if (Base[pre]!lca) Father[pre]link[i]; //同理44 InBlossom[Base[i]]true;45 InBlossom[Base[link[i]]]true;46 }47 #undef pre48 if (Base[x]!lca) Father[x]y; //注意不能从lca这个奇环的关键点跳回来49 if (Base[y]!lca) Father[y]x;50 for (i1;in;i)51 if (InBlossom[Base[i]]){52 Base[i]lca;53 if (!in_Queue[i]){54 Q[tail]i;55 in_Queue[i]true; //要注意如果本来连向BFS树中父结点的边是非匹配边的点可能是没有入队的56 }57 }58 }59 60 void Change(){61 int x,y,z;62 zFinish;63 while (z){64 yFather[z];65 xlink[y];66 link[y]z;67 link[z]y;68 zx;69 }70 }71 72 void FindAugmentPath(){73 fill(Father,Fathern1,0);74 fill(in_Queue,in_Queuen1,false);75 for (int i1;in;i) Base[i]i;76 head0; tail1;77 Q[1]Start;78 in_Queue[Start]1;79 while (head!tail){80 int xQ[head];81 for (int y1;yn;y)82 if (map[x][y] Base[x]!Base[y] link[x]!y) //无意义的边83 if ( Starty || link[y] Father[link[y]] ) //精髓地用Father表示该点是否84 BlossomContract(x,y);85 else if (!Father[y]){86 Father[y]x;87 if (link[y]){88 Q[tail]link[y];89 in_Queue[link[y]]true;90 }91 else{92 Finishy;93 Change();94 return;95 }96 }97 }98 }99
100 void Edmonds(){
101 memset(link,0,sizeof(link));
102 for (Start1;Startn;Start)
103 if (link[Start]0)
104 FindAugmentPath();
105 }
106
107 void output(){
108 fill(mark,markn1,false);
109 int cnt0;
110 for (int i1;in;i)
111 if (link[i]) cnt;
112 printf(%d\n,cnt);
113 for (int i1;in;i)
114 if (!mark[i] link[i]){
115 mark[i]true;
116 mark[link[i]]true;
117 printf(%d %d\n,i,link[i]);
118 }
119 }
120
121 int main(){
122 // freopen(input.txt,r,stdin);
123 CreateGraph();
124 Edmonds();
125 output();
126 return 0;
127 } 然后还有一篇链接请猛戳。。 在北京冬令营的时候yby提到了“带花树开花”算法来解非二分图的最大匹配。 于是我打算看看这是个什么玩意。其实之前我已经对这个算法了解了个大概但是。。。真的不敢去写。 有一个叫Galil Zvi的人应该叫计算机科学家写了篇论文 Efficient Algorithms for Finding Maximal Matching in Graphs 如果你在网上搜不到可以http://builtinclz.abcz8.com/art/2012/Galil%20Zvi.pdf 这篇论文真神啊它解决了4个问题 一般图二分图的最大匹配最大权匹配问题。 算法的思想、故事请自己看论文吧。 这个论文告诉了我们很多有趣的东西例如 用Dinic实现的二分图匹配的时间复杂度其实是O(M*N^0.5)这也许能够解释为什么一般网络流算法比Hungry要快了。 另外带花树算法的正确性的证明比较困难而其时间复杂度是可以做到O(M*N^0.5)的不过要详细实现那么就快能到“ACM最长论文奖”了。 我写了一个实例代码 http://builtinclz.abcz8.com/art/2012/ural1099.cpp 没错这是用来解决URAL 1099 Work Schedule那题的。时间复杂度是ON 简述一下“带花树”算法吧 它的核心思想还是找增广路。假设已经匹配好了一堆点我们从一个没有匹配的节点s开始使用BFS生成搜索树。每当发现一个节点u如果u还没有被匹配那么就可以进行一次成功的增广否则我们就把节点u和它的配偶v一同接到树上之后把丢进队列继续搜索。我们给每个在搜索树上的点一个类型S或者T。当把它的配偶扔进队列的时候我们把标记为T型标记为S型。于是搜索树的样子是这样的 其中黑色竖线相连的两个点是已经匹配好的蓝色斜线表示两个点之间有边但是没有配对。T型的用红色S型的用黑色。 这里有个小问题一个S型点在某一步扩展的时候发现了点如果已经在搜索树上了即出现了环怎么办 我们规定如果的类型是T型就无视这次发现这意味着我们找到了一个长度为偶数的环直接无视 如果连出来的边是指向T型点的就无视这个边。 否则我们找到了一个长度为奇数的环就要进行一次“缩花”的操作所谓缩花操作就是把这个环缩成一个点。 这个图缩花之后变成了个点一个大点或者叫一朵花加原来的个点 缩点完成之后还要把原来环里面的T型点统统变成S型点之后扔到队列里去。 现在是一个点了还是一个S点。 为什么能缩成一个点呢我们看一个长度为奇数的环例如上图中的如果我们能够给它中的任意一个点找一个出度配偶那么环中的其他点正好可以配成对这说明每个点的出度都是等效的。例如假设我们能够给图中的点另找一个配偶例如好了那么环中的剩下个点正好能配成对一个不多一个不少算上和一共对刚刚好。 这就是我们缩点的思想来源。有一个劳苦功高的计算机科学家证明了缩点之前和缩点之后的图是否有增广路的情况是相同的。 缩起来的点又叫一朵花 注意到组成一朵花的里面可能嵌套着更小的花。 当我们最终找到一条增广路的时候要把嵌套着的花层层展开还原出原图上的增广路出来。 嗯现在你对实现这个算法有任何想法吗 天啊还要缩点……写死谁。。。。。。 我一开始也是这么想的。 我看了一眼网上某个大牛的程序之后结合自己的想法很努力地写出了一个能AC的版本。 实现的要点有什么呢 首先我们不“显式”地表示花。我们记录一个N数组表示最终增广的时候的路径上的后继。同时我们维护一个并查集表示每个点现在在以哪个点为根的花里一个花被缩进另一朵花之后就不算花了。还要记录每个点的标记。 主程序是一段BFS。对于每个由发展出来的点分种情况讨论 。是配偶不说夫妻这是非二分图。。。或者现在是一个点在一朵花里直接无视 。是T型点直接无视 。目前单身太好了进行增广 。是一个S型点缩点缩点 缩点的时候要进行的工作 。找和的LCA的根。找LCA可以用各种方法。。。直接朴素也行。 。在N数组中把和接起来表示它们形成环了 。从、分别走到修改并查集使得它们都变成一家人同时沿路把N数组接起来。 N数组很奇妙。每时每刻它实际形成了若干个挂在一起的双向链表来表示一朵花内部的走法。 有权图的最大匹配怎么做 看论文吧。。。用类似KM的方法不过是给每个花再来一个权值。真的很复杂。。。 有一个人写了代码好像是GPL许可证。。。你最好想办法搜到它的网站来看看版权的问题总之我先贴出来 http://builtinclz.abcz8.com/art/2012/mwmatching.py转载于:https://www.cnblogs.com/zhsl/p/3271754.html
