关键词：

二分图匹配

首先还是要了解二分图匹配是个什么东西

? 分图又称作二部图，是图论中的一种特殊模型。 设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图。

? （以上来自百度百科）说简单一些就是对于一个无向图可以将它分为两个集合，对于同一集合内的元素一定没有边相连，而不同集合内的元素存在边相连，这样的图称之为二分图。

那么二分图匹配呢？

? 给定一个二分图，寻找与一个边集的边能够满足任意两条边都不依附在同一个顶点，这样叫做二分图的一个匹配。

? 说的更简单一些也就是让二分图两个集合内的点一个一个对应起来。

? 通常做题时我们对于一个二分图需要求它的一个最大匹配。也就是尽可能让边集中边的数量尽可能的多，尽可能多的点能够匹配在一起。

匈牙利算法

? 求解一个二分图的最大匹配，比较简单也是常用的办法就是匈牙利算法。

? 算法证明比较复杂，所以下面只介绍算法实现的流程。

? 1.让第一个集合中的点去匹配

? 2.如果匹配到的点没有配对，那么就暂时先和这个点匹配起来

? 3.如果匹配到的点已经配对了，那么尝试让与匹配到的这个点匹配的点再去匹配，如果能匹配到，则当前点和匹配到的点就匹配到一起，否则就不能。

? 4.依次再对集合中的下一个点进行这样的匹配操作。

需要注意的是：每一轮操作中，一个点只能被匹配一次。

例题

luogu 2055假期的宿舍 （一道板子题就不多说了x

#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
int read()
    int a=0,f=0;char p=getchar();
    while(!isdigit(p))f|=p==‘-‘;p=getchar();
    while(isdigit(p))a=(a<<3)+(a<<1)+(p^48);p=getchar();
    return f?-a:a;

void print(int x)
    if(x<0)putchar(‘-‘);x=-x;
    if(x>=10)print(x/10);
    putchar(x%10+‘0‘);

int flag1[60],flag2[60];
int n;
vector<int> m[100];
bool gx[100][100];
bool vis[100];
int bf[100];
bool dfs(int x)
    for(int i=0;i<m[x].size();i++)
        int j=m[x][i];
        if(vis[j])continue;
        vis[j]=1;
        if(!bf[j]||dfs(bf[j]))
            bf[j]=x;
            return true;
        
    
    return false;

int main()
    int t;
    t=read();
    while(t--)
        int cnt=0;
        memset(flag1,0,sizeof(flag1));
        memset(flag2,0,sizeof(flag2));
        memset(m,0,sizeof(m));
        memset(gx,0,sizeof(gx));
        memset(bf,0,sizeof(bf));
        n=read();
        for(int i=1;i<=n;i++)
            flag1[i]=read();//如果是1表示是在校学生
        for(int i=1;i<=n;i++)
            flag2[i]=read();//1表示这个在校学生要回家睡觉
            if(flag1[i]==0)flag2[i]=1;
        
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                gx[i][j]=read();
                if(gx[i][j])
                    if(flag1[j])m[i].push_back(j);//如果j在学校有床
                
                if(i==j&&flag1[i])m[i].push_back(j);
                
            
        
        for(int i=1;i<=n;i++)
            if((!flag1[i])||(!flag2[i]))//不是在学生或者他不回家睡觉
                memset(vis,0,sizeof(vis));
                if(!dfs(i))cnt++;
            
        
        if(cnt)cout<<"T_T"<<endl;
        else cout<<"^_^"<<endl;
    

二分图匹配(模板)(代码片段)

二分图匹配附上两种方法：网络流据说所有的二分图题目都可以用网络流跑过去，可能还快一些话不多说，只有代码/*二分图匹配的题大多可用网络流做此处为Dinic模板，详见网络流模板*/#include<iostream>#include<cstdlib>#includ... 查看详情

二分图匹配问题(代码片段)

二分图最大匹配 二分图最大权匹配1#include<bits/stdc++.h>2usingnamespacestd;3constintLEN=1e3+5;4typedeflonglongll;5intn,n1,n2,m;6constintoo=1e9;7llans;8namespaceKM9intqh,qt;10intw[LEN][LEN],q[LEN];11intlx[ 查看详情

二分图匹配(代码片段)

　　记得很早就看过这个算法，但是一直没怎么学。　　二分图:　　 无向图G为二分图的充分必要条件是，G至少有两个顶点，且其所有回路的长度均为偶数。　　 判断一个联通图是否是二分图采用着色法，选取一个起点... 查看详情

二分图匹配——poj1469(代码片段)

关于本题二分图的匹配关系始终是加单向边用左边去匹配右边，match表示的是右边的人匹配的对应的左边的点 /*关于本题二分图的匹配链接的关系始终是单向边用左边去匹配右边，match表示的是右边的人匹配的对应的左边的点... 查看详情

二分图最大匹配(代码片段)

二分图的概念二分图又称作二部图，是图论中的一种特殊模型。设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边(i,j)所关联的两个顶点i和j分别属于这两个不同的顶点集(iinA,jinB)，则称图G为... 查看详情

二分图匹配(代码片段)

二分图匹配这是一个绿与被绿的故事......首先二分图就是一张图能分成两个点集，集合内部没有连边，两集合之间有若干连边现在有这么一张图要求最多有多少对点能匹配成功首先，我们给张起灵匹配。我们发现他只能和吴邪匹... 查看详情

二分图(代码片段)

二分图二分图定义判断1存图以及加边2核心部分3完整代码二分图最大匹配1定义2求二分图最大匹配3完整代码二分图最小点覆盖1定义2定理二分图最大独立集1定义2定理二分图最大加权匹配题单定义给出一张图（通常是无向图），... 查看详情

hdu1669二分图多重匹配+二分(代码片段)

Jamie‘sContactGroupsTimeLimit:15000/7000MS(Java/Others)    MemoryLimit:65535/65535K(Java/Others)TotalSubmission(s):747    AcceptedSubmission(s):303ProblemDescri 查看详情

acm模板判断二分图+二分图最大匹配(代码片段)

参考文章：https://www.luogu.com.cn/blog/Repulser/solution-p3386POJ2492ABug’sLife判断无向图是否为二分图，注意图可能不连通。#include<iostream>#include<cstdio>#include<cstring>#include<vector> 查看详情

二分图——匈牙利算法简述(代码片段)

昨天模拟，有一道高维宇宙，二分图匹配是正解，但是二分图匹配有点忘了，复习一下。二分图匹配其实就是两个集合有一些元素可以匹配，试图找到最多匹配的一种情况。二分图中的两个可以连得边用数组来实现。每一个元素... 查看详情

二分图匹配模板(代码片段)

题目描述给定一个二分图，结点个数分别为n,m，边数为e，求二分图最大匹配数输入输出格式输入格式： 第一行，n,m,e第二至e+1行，每行两个正整数u,v，表示u,v有一条连边 输出格式： 共一行，二分图最大匹配 输入... 查看详情

tracerdeploymentuvalive-8271二分图匹配(代码片段)

复习二分图又想起了这道题，裸的二分图匹配，直接匈牙利算法就可以了，mark一下这个比较好用的稠密图匈牙利算法模板题目：题目链接AC代码：#include<iostream>#include<cstdio>#include<cstdlib>#include<algorithm>#include<cs... 查看详情

landoffarmshdu-5556二分图匹配(代码片段)

FarmerJohnandhisbrothershavefoundanewland.Theyaresoexcitedanddecidetobuildnewfarmsontheland.Thelandisarectangleandconsistsof N×MN×Mgrids.Afarmconsistsofoneormoreconnectedgrids.Twogrid 查看详情

poj3057evacuation二分图匹配+最短路(代码片段)

POJ3057Evacuation二分图匹配+最短路题目描述Firescanbedisastrous,especiallywhenafirebreaksoutinaroomthatiscompletelyfilledwithpeople.Roomsusuallyhaveacoupleofexitsandemergencyexits,butwitheveryonerushingoutatthesam 查看详情

二分图匹配(代码片段)

匈牙利算法   https://blog.csdn.net/c20180630/article/details/70175814模板题hdu2063#include<bits/stdc++.h>usingnamespacestd;constintN=550;intk,m,n,cnt;boolvis[N];intma[N],last[N];structorz 查看详情

二分图匹配模板题(代码片段)

2013-2014 ACM-ICPC, NEERC, Eastern Subregional Contest 1/*************************************************************************2>FileName:a.cpp3>Author:QWX4>M 查看详情

二分图匹配（入门篇）(代码片段)

二分图匹配writebyBigYellowDog1.什么是二分图？有一个无向图，如果所有的点可以被所有的边分成两个点集。则说这个图为二分图下图就是一个标准二分图：2.什么是二分图匹配？现有一个二分图E，还有它的子集M。如果M中任意一条... 查看详情

二分图(代码片段)

二分图概念二分图：把一个图的顶点划分为两个不相交集U和V，使得每一条边都分别连接U、V中的顶点。如果存在这样的划分，则此图为一个二分图。二分图的一个等价定义是：不含有「含奇数条边的环」的图。图1是一个二分图... 查看详情