#include<iostream> #include<cstdio> #include<cstring> usingnamespace std; int data[205][205],link[205],visit[205],count,n,m; bool dfs(int x){for(int j=1;j<=m;j++){if(data[x][j]&&!visit[j]){visit[j] = 1;if(link[j]==0||dfs(link[j])){link[j] = x;returntrue;}}}returnfalse; } void hungery(){for(int i=1;i<=n;i++){memset(visit,0,sizeof visit);if(dfs(i)){count++;}} } int main(){int i,j,p,q;while(scanf("%d...
#define _CRT_SECURE_NO_WARNINGS #include<iostream> #include<stdio.h> #include<stdlib.h> usingnamespace std; #define N 500 int n1, n2, ans; int result[N]; bool state[N]; bool map[N][N];bool find(int x) {for (int i = 1; i <= n2; ++i){if (map[x][i] && !state[i]){state[i] = true;if (result[i] == 0 || find(result[i])){result[i] = x;returntrue;}}}returnfalse; } int hungary() {for (int i = 1; i <= n1; ++...
PS：其实不用理解透增广路，交替路，网上有对代码的形象解释，看懂也能做题，下面我尽量把原理说清楚基本概念 （部分来源、部分来源）二分图： 设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图。匹配： 一个匹配即一个包含若干条边的集合，且其中任意两条边没有公共端点。下图标红的边即为匹配? ...
本文转自大牛博客：http://www.byvoid.com/blog/hungary/ 这是一种用增广路求二分图最大匹配的算法。它由匈牙利数学家Edmonds于1965年提出，因而得名。 定义 未盖点：设Vi是图G的一个顶点，假设Vi 不与随意一条属于匹配M的边相关联，就称Vi 是一个未盖点。 交错路：设P是图G的一条路，假设P的随意两条相邻的边一定是一条属于M而还有一条不属于M，就称P是一条交错路。可增广路：两个端点都是未盖点的交错路叫做可增广路。 流程图 伪...
DescriptionRPG girls今天和大家一起去游乐场玩，终于可以坐上梦寐以求的过山车了。可是，过山车的每一排只有两个座位，而且还有条不成文的规矩，就是每个女生必须找个个男生做partner和她同坐。但是，每个女孩都有各自的想法，举个例子把，Rabbit只愿意和XHD或PQK做partner，Grass只愿意和linle或LL做partner，PrincessSnow愿意和水域浪子或伪酷儿做partner。考虑到经费问题，boss刘决定只让找到partner的人去坐过山车，其他的人，...
来源：http://acm.hdu.edu.cn/showproblem.php?pid=2063 题意：有k个组合a,b组合，代表a愿意与b坐过山车，共m个女生 n个男生，问有多少个满意的匹配题解：这是一道匈牙利算法的裸题，用递归询问是否能安排好某个女生，如果能就ans++注意，在同一回合的询问中，某个女生只寻找一次其它男生，第二次寻找时一定无法找到，直接返回0就行这是我第二次做这道题，在前几个月已经做过，没想到这就是传说中的二分图 Orz #include<iostream>...
二部图最大匹配问题定义设简单二部图\(G=< A,B,E>,M\subset E,\)如果\(M\)中任意两条边都不相邻，则称\(M\)是\(G\)的匹配。当\(M\)的边数最多时，\(M\)称作最大匹配。当\(|A|=|B|=n\)时，边数为\(n\)的匹配称作完美匹配。相关概念交错路径和增广交错路径设\(M\)是二部图\(G\)的一个匹配，则称\(M\)中的边为匹配边，\(G\)中不属于\(M\)的边为非匹配边，与匹配边关联的顶点为饱和点。\(G\)中由匹配边和非匹配边交替构成的路径称为交错...
二分图：顶点可以分类两个集合X和Y，所有的边关联的两个顶点恰好一个属于集合X，另一个属于集合Y.二分图匹配：给定一个二分图G，在G的一个子图M中，M的边集中的任意两条边都不依附于同一个顶点，则称M是一个匹配。最大匹配：图中包含边数最多的匹配称为图的最大匹配.完美匹配：如果所有点都在匹配边上，则称这个最大匹配是完美匹配.二分图匹配基本概念：未盖点：设VI是G的一个顶点，如果VI不与任意一条属于匹配M的边相关联，就称VI...
解题报告二分图第一题。题目描述：为了参加即将召开的会议，A国派出M位代表，B国派出N位代表，（N，M<=1000）会议召开前，选出K队代表，每对代表必须一个是A国的，一个是B国的;要求每一个代表要与另一方的一个代表联系，除了可以直接联系，也可以电话联系，求电话联系最少思路：电话联系最少就要使直接联系最大，又是一一匹配关系，就是二分图的最大匹配。下面是匈牙利算法。#include <cstdio> #include <cstring> #include <iostr...
传送门Description现在电视台有一种节目叫做超级英雄，大概的流程就是每位选手到台上回答主持人的几个问题，然后根据回答问题的多少获得不同数目的奖品或奖金。主持人问题准备了若干道题目，只有当选手正确回答一道题后，才能进入下一题，否则就被淘汰。为了增加节目的趣味性并适当降低难度，主持人总提供给选手几个“锦囊妙计”，比如求助现场观众，或者去掉若干个错误答案（选择题）等等。这里，我们把规则稍微改变一下。假设主持...
【书本上的算法往往讲得非常复杂，我计划用一个幽默的例子来描述算法的流程】匈牙利算法是由匈牙利数学家Edmonds于1965年提出，因而得名。匈牙利算法是基于Hall定理中充分性证明的思想，它是部图匹配最常见的算法，该算法的核心就是寻找增广路径，它是一种用增广路径求二分图最大匹配的算法。一.先上基本概念：二分图：简单来说，如果图中点可以被分为两组，并且使得所有边都跨越组的边界，则这就是一个二分图。准确地说：把一个图...
#define _CRT_SECURE_NO_WARNINGS #include<iostream> #include<vector> #include<string> #include<stdio.h> #include<stdlib.h> usingnamespace std;constint N = 101; bool isSushu(int n) {if (n % 2 == 0 || n % 3 == 0) returnfalse;else{for (int i = 5; i*i <= n; i += 6)if (n%i == 0 || n % (i + 2) == 0) returnfalse;returntrue;} } int n1, n2, ans; int result[N]; bool state[N]; bool map[N][N];bool find(int x) ...
CoursesTime Limit: 20000/10000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 4233 Accepted Submission(s): 2014Problem DescriptionConsider a group of N students and P courses. Each student visits zero, one or more than one courses. Your task is to determine whether it is possible to form a committee of exactly P students that satisfies simultaneously the cond...
KM算法 1 #include <bits/stdc++.h>2#define N 15003#define inf 9999999994usingnamespace std;5int a[N],bs[N],nx=0,ny=0,k;6int linky[N],lx[N],ly[N],slack[N];7int visx[N],visy[N],w[N][N];8int min(int a,int b){return (a<b)?a:b;}9int find(int x){ 10 visx[x]=1; 11for(int y=1;y<=ny;y++){ 12if(visy[y]) continue; 13int t=lx[x]+ly[y]-w[x][y]; 14if(t==0){visy[y]=1; 15if(linky[y]==-1||find(linky[y])){ 16 ...
题目大意： 有n个学生，有m对人是认识的，每一对认识的人能分到一间房，问能否把n个学生分成两部分，每部分内的学生互不认识，而两部分之间的学生认识。如果可以分成两部分，就算出房间最多需要多少间，否则就输出No。解题思路：先是要判断是否为二部图，然后求最大匹配。 #include <iostream> #include <cstring> #include <cstdlib> #include <cstdio> #include <vector> #include <cmath> #include <queue> #include <st...