#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<cstdlib> #include<algorithm> #include<ctime> using namespace std; const int N=205; bool gra[N][N],state[N]; int result[N],ans,n,m,s,x; bool find(int a){for(int i=1;i<=m;i++){if(gra[a][i]&&!state[i]){state[i]=1;if(!result[i]||find(result[i])){result[i]=a;return true;}}}return false; } int main(){scanf("%d%d",&n,&m);for(i...
学习出https://blog.csdn.net/sunny_hun/article/details/80627351 题：poj1325 #include<iostream> #include<cstring> #include<cstdio> #include<algorithm> using namespace std; inline int read(){int sum=0,x=1;char ch=getchar();while(ch<0||ch>9){if(ch==-)x=0;ch=getchar();}while(ch>=0&&ch<=9)sum=(sum<<1)+(sum<<3)+(ch^48),ch=getchar();return x?sum:-sum; } inline void write(int x){if(x<0)putchar(-),x=-x;if(x...
因为没有重复串，所以把有包含关系的串连边之后是个DAG，也就是二分图，就变成求二分图的最大独立集=n-最小点覆盖=n-最大匹配 关于包含关系，建出AC自动机，然后把串放上去找子串，但是如果每次都一路找到根就会T，所以每次只找最近的一个，并且对于没有结尾id的点承接father的id，这样就O(1)的找到最近子串了 然后再用floyd传递闭包把关系建出图来 然后跑匈牙利，输出方案就是把一个匹配环里同一侧的都dfs标记一下，最后输出没有被...
在看这道题之前，我们先来了解一下什么是二分图及与二分图匹配的相关概念及基础知识。 基础知识 故名思义，二分图本质上还是由点和边构成的数据结构，与之不同的是，二分图相当于把一张图分成了两个部分，也就是两个部。部与部之间的点没有边相连，以下的几个图都可以算作二分图： （图中的箭头无意义，并不代表有向边） 现在来简单说一下匹配和最大匹配（因为只涉及匈牙利算法，所以不讲其他杂七杂八的东西。最小点覆盖什么的以后...
upd: 单向连边 \(a \rightarrow b\) ，显然应该在每一轮搜索中标记 \(b\) 集合的点。我误标记了 \(a\) ，这样就没有任何 \(a\) 类节点可以更改匹配了，完蛋。bool hungary(int p, int id){for (int i = Fs[p]; i; i = Nx[i]) {int t = Vs[i];if (Mk[t] == id)continue;Mk[t] = id;if (!Lnk[t] || hungary(Lnk[t], id)) {Lnk[t] = p;return 1;}}return 0;}int main(){ans = 0;for (i = 1; i <= n; ++i)ans += hungary(i);printf("%d...
https://www.luogu.org/problemnew/show/P3386#include<cstdio> int e[1005][1005],match[1005],book[1005]; // match数组用来记录配对关系 int n,m,t; int dfs(int u) {for(int v=1; v<=m; v++){if(book[v]==0&&e[u][v]==1){book[v]=1; // 标记v点已经被访问 if(match[v]==0||dfs(match[v])) // 如果点v未被配对，或者点v的匹配对象找到了新的配对。 {match[v]=u; // 更新配对关系 return 1;}}}return 0; } int main() {int a,b;...
本文转自大牛博客：http://www.byvoid.com/blog/hungary/ 这是一种用增广路求二分图最大匹配的算法。它由匈牙利数学家Edmonds于1965年提出，因而得名。 定义 未盖点：设Vi是图G的一个顶点，如果Vi 不与任意一条属于匹配M的边相关联，就称Vi 是一个未盖点。 交错路：设P是图G的一条路，如果P的任意两条相邻的边一定是一条属于M而另一条不属于M，就称P是一条交错路。 可增广路：两个端点都是未盖点的交错路叫做可增广路。 流程图...
匈牙利算法又被称为增广路算法。什么是增广路？对于任意一组匹配S，属于S的边被称为匹配边，不属于S的被称为非匹配边。如果二分图中存在一条连接两个非匹配点的路径path，使得非匹配边与匹配边在path上交替出现，那么我们称path是匹配S的一条增广路。增广路的性质：1.长度为奇数2.路径上第1、3、5...、len条边是非匹配边，第2、4、6...、len-1条边是匹配边。正因为以上性质，我们可以把增广路上所有边的状态取反，则匹配+1。进一步...
题意： 给出一个N*N的地图N 地图里面有K个障碍 你每次可以选择一条直线 消除这条直线上的所有障碍 （直线只能和列和行平行） 问最少要消除几次 题解： 如果（x，y）上有一个障碍 则把X加入点集 V1 、Y加入点集V2 并且X Y连一条边 这样构成一个新图 如果选择 V1中的点 X 那么就相当于消去 (X,y)中的所有Y 要找使最小点覆盖 那就是跑一遍 匈牙利就行了 详细证明见二分图最小点覆盖Knig定理 其中 x y需要连单向边 不然会...
点此看题面 大致题意： 有一个\(N*N\)的\(01\)矩阵，可以任意交换若干行和若干列，问是否有方案使得左上角到右下角的连线上全是\(1\)。题意转换 首先，让我们来对题意进行一波转化。 如果我们把\(x\)坐标看作一张二分图左半部分的点，把\(y\)坐标看作右半部分的点，那么题意就转化成了求这张图是否存在完美匹配。 又由于每次只能交换行与列，因此每行存在的元素和每列存在的元素是固定不变的。 因此，在行与列不停交换的过程中，这...
1191: [HNOI2006]超级英雄Hero Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 6172 Solved: 2763[Submit][Status][Discuss] Description现在电视台有一种节目叫做超级英雄,大概的流程就是每位选手到台上回答主持人的几个问题,然后根据回答问题的 多少获得不同数目的奖品或奖金。主持人问题准备了若干道题目，只有当选手正确回答一道题后，才能进入下一题 ，否则就被淘汰。为了增加节目的趣味性并适当降低难度，主持人总提供给...
在阅读《算法的乐趣》的时候，实在难以理解第七章中关于匈牙利算法的描述，所以劣者在网上搜刮各种资料，整理如下，既为了自己复习之用，也为了后来者的方便 匈牙利算法解决了舞伴的快速匹配问题，什么是舞伴快速匹配问题呢？男女双方都有各自的最优选择名单，在一轮轮的选择过后，最终会得到一个结果，这个过程就是快速匹配问题。 匈牙利算法如下： 定义struct tagMaxMatch { int edge[MAX][MAX]; //顶点和关系的图 bool on_...
题目传送门 毒瘤出题人zzk出了个二分图匹配的题（18.10.04模拟赛T2），逼我来学二分图匹配。 网络流什么的llx讲完之后有点懵，还是匈牙利比较好理解(绿与被绿)。 对于左边的点一个一个匹配，记录右边哪个点跟左边的i匹配：cp[i] 如果还没有配对，就直接配上。 如果已经有匹配了，每次dfs找增广路(看看能不能换一下)，如果成功，那么匹配数增加一。 1 #include<cstdio>2 #include<cstring>3 #include<algorithm>4 using namespace s...
二分图的最大匹配：匈牙利算法 讲之前本蒟蒻先普及一个重要专业名词 增广路。 如果你仔细读过并画过图，不难发现如果找到一条增广路，那么配对的个数就会加1。 所以说，增广路的本质其实就是一条路径的起点和终点都未配对的点的边。匈牙利算法： 这个叫匈牙利算法(Hungarian method)的东西是由匈牙利数学家Edmonds于1965年提出，所以叫匈牙利算法。匈牙利算法是二分图匹配最常见的算法，该算法的核心就是寻找增广路径，它是一种用增...
如下图：要求最多可以凑成多少对对象 ? 大佬博客：https://blog.csdn.net/cillyb/article/details/55511666 模板：int link[maxn],vis[maxn]; bool dfs(int x) {for(int i = 1; i <= num; i++){if(!vis[i] && cp[x][i]){vis[i] = 1;if(link[i] == 0 || dfs(link[i])){link[i] = x;return true;}}}return false; }int hunyary() {int sum = 0;memset(link, 0, sizeof(link));for(int i = 1; i <= num; i++){memset(vis, 0, sizeof(v...