文档章节

二分图判断

Airship
 Airship
发布于 2017/09/08 09:59
字数 635
阅读 4
收藏 0
点赞 0
评论 0

题目:http://acm.hdu.edu.cn/showproblem.php?pid=2444

 

题意:给定一个无向图,先判断它是否是二分图,如果是则求出最大匹配,否则输出“No”。

 

二分图是这样一个图: 有两顶点集且图中每条边的的两个顶点分别位于两个顶点集中,每个顶点集中没有边相连接!

判断二分图的常见方法:开始对任意一未染色的顶点染色,之后判断其相邻的顶点中,若未染色则将其染上和相邻顶点不同的颜色, 若已经染色且颜色和相邻顶点的颜色相同则说明不是二分图,若颜色不同则继续判断,用深搜即可。因为是无向二分图的匹配,所以要除以2。

题目:http://acm.hdu.edu.cn/showproblem.php?pid=2444
 
题意:给定一个无向图,先判断它是否是二分图,如果是则求出最大匹配,否则输出“No”。

二分图是这样一个图: 有两顶点集且图中每条边的的两个顶点分别位于两个顶点集中,每个顶点集中没有边相连接!
判断二分图的常见方法:开始对任意一未染色的顶点染色,之后判断其相邻的顶点中,若未染色则将其染上和相邻顶点不同的颜色, 若已经染色且颜色和相邻顶点的颜色相同则说明不是二分图,若颜色不同则继续判断,用深搜即可。因为是无向二分图的匹配,所以要除以2。

[cpp] view plain copy
#include <iostream>  
#include <string.h>  
#include <stdio.h>  
  
using namespace std;  
const int N = 2005;  
  
int head[N],link[N];  
bool vis[N],col[N];  
int cnt,n,m;  
  
struct Edge  
{  
    int to;  
    int next;  
};  
  
Edge edge[N*N];  
  
void Init()  
{  
    cnt = 0;  
    memset(head,-1,sizeof(head));  
    memset(col,0,sizeof(col));  
}  
  
void add(int u,int v)  
{  
    edge[cnt].to = v;  
    edge[cnt].next = head[u];  
    head[u] = cnt++;  
}  
  
bool Color(int u)  
{  
    for(int i=head[u]; ~i; i=edge[i].next)  
    {  
        int v = edge[i].to;  
        if(!col[v])  
        {  
            col[v] = !col[u];  
            if(!Color(v)) return false;  
        }  
        else if(col[v] == col[u])  
            return false;  
    }  
    return true;  
}  
  
bool dfs(int u)  
{  
    for(int i=head[u]; ~i; i=edge[i].next)  
    {  
        int v = edge[i].to;  
        if(!vis[v])  
        {  
            vis[v] = 1;  
            if(link[v] == -1 || dfs(link[v]))  
            {  
                link[v] = u;  
                return true;  
            }  
        }  
    }  
    return false;  
}  
  
int match()  
{  
    int ans = 0;  
    memset(link,-1,sizeof(link));  
    for(int i=1; i<=n; i++)  
    {  
        memset(vis,0,sizeof(vis));  
        if(dfs(i)) ans++;  
    }  
    return ans;  
}  
  
int main()  
{  
    while(~scanf("%d%d",&n,&m))  
    {  
        if(n == 1)  
        {  
            puts("No");  
            continue;  
        }  
        Init();  
        while(m--)  
        {  
            int u,v;  
            scanf("%d%d",&u,&v);  
            add(u,v);  
            add(v,u);  
        }  
        col[1] = 1;  
        if(!Color(1))  
        {  
            puts("No");  
            continue;  
        }  
        printf("%d\n",match()>>1);  
    }  
    return 0;  
}  

 

© 著作权归作者所有

共有 人打赏支持
Airship
粉丝 34
博文 789
码字总数 18996
作品 0
南京
高级程序员
二分图算法模板以及相关知识

说说二分图,其实图论的题难点不在用算法,难在如何建图,只有图建好了,剩下的就简单了,在这说说求二分图的算法,即匈牙利算法,其实一点都不难,也很好理解拿笔写写就行了. //板子, 直接套就行 //...

Anxdada ⋅ 2017/06/22 ⋅ 0

复杂网络分析库NetworkX学习笔记(5):二分图

二分图又称二部图,是图论中的一种特殊模型,它的顶点可分割为两个互不相交的子集,并且图中的每条边所关联的两个顶点分别属于这两个不同的顶点集。二分图在复杂网络分析中有很多应用,例如科...

鉴客 ⋅ 2012/11/03 ⋅ 0

[BZOJ2709] [Violet 1]迷宫花园

http://www.lydsy.com/JudgeOnline/problem.php?id=2709 这题是权限题,版权问题不放题意,我来简要的说一下: 给出一个迷宫,有起始点终点,可以上下左右走,移动的耗时是1,可以改变上下走...

CABI_ZGX ⋅ 02/03 ⋅ 0

司机乘客匹配中的距离和最小问题

这个是在工作中遇到的一个实际的算法问题,问题描述如下,当前有m个司机,n个乘客,每个司机和每个乘客的距离由经纬度可以计算得到,如何匹配可以使其去接乘客的距离和最小?(只能一个司机接...

necther ⋅ 05/03 ⋅ 0

BJ模拟 Mortal Kombat【二分图匹配+tarjan】

题目大意: 给一张n个黑点,m个白点的二分图,问对于任意一对相连的黑白点对(i,j),判断边(i, j)是否能成为该二分图最大匹配的匹配边,能输出0,否则输出1。 n<=300,m<=1500,n<=m 解题思路:...

cdsszjj ⋅ 05/06 ⋅ 0

ACM程序设计大赛题目分类

第一类:基础算法 (1) 基础算法:枚举,贪心,递归,分治,递推,构造,模拟 (2) 动态规划:背包问题,树形dp,状态压缩dp,单调性优化,插头dp (3) 搜索:dfs,bfs,记忆化搜索,优化...

齐勇cn ⋅ 2016/04/20 ⋅ 0

12.15~12.16培训总结

图论我在九月份打了很多板,基础较熟练,但对二分图匹配和网络流、费用流以及各种模型不太熟练。 二分图主要有这些模型 (部分参考lrj) 二分图最小覆盖(选择尽量少的点,使得每条边至少有一...

myjs999 ⋅ 2017/12/17 ⋅ 0

图论 应用篇

上次写了篇图的基本构造方法,运用图这种强大的数据结构结构,还能解决实际应用中的许多问题,今天这篇就主要整理一些常见的应用 一、路径问题 路径问题在图的处理领域是非常重要的。如我们最...

丶legend ⋅ 2017/11/05 ⋅ 0

二分图知识点总结

最大匹配:在二分图中,最多的没有公共顶点的边的数量。(用匈牙利算法) 最小点覆盖:在二分图中,所有边至少有一个顶点在一个点集

wang3312362136 ⋅ 02/01 ⋅ 0

[BZOJ2663][Beijing wc2012]灵魂宝石(二分+二分图匹配)

传送门 因为问题是单调的,R小肯定匹配的少,R大肯定匹配的多,所以一眼可以二分+二分图匹配。 难点就在要求最小值和最大值,最小值好求,但是最大值呢? 因为二分图匹配算法是求得最大匹配,...

cabi_zgx ⋅ 03/23 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

BS与CS的联系与区别【简】

C/S是Client/Server的缩写。服务器通常采用高性能的PC、工作站或小型机,并采用大型数据库系统,如Oracle、Sybase、InFORMix或 SQL Server。客户端需要安装专用的客户端软件。 B/S是Brower/...

anlve ⋅ 49分钟前 ⋅ 0

发生了什么?Linus 又发怒了?

在一个 Linux 内核 4.18-rc1 的 Pull Request 中,开发者 Andy Shevchenko 表示其在对设备属性框架进行更新时,移除了 union 别名,这引发了 Linus 的暴怒。 这一次 Linus Torvalds 发怒的原...

问题终结者 ⋅ 今天 ⋅ 0

在树莓派上搭建一个maven仓库

在树莓派上搭建一个maven仓库 20180618 lambo init 项目说明 家里有台树莓派性能太慢。想搭建一个maven私服, 使用nexus或者 jfrog-artifactory 运行的够呛。怎么办呢,手写一个吧.所在这个...

林小宝 ⋅ 今天 ⋅ 0

Spring发展历程总结

转自与 https://www.cnblogs.com/RunForLove/p/4641672.html 目前很多公司的架构,从Struts2迁移到了SpringMVC。你有想过为什么不使用Servlet+JSP来构建Java web项目,而是采用SpringMVC呢?...

onedotdot ⋅ 今天 ⋅ 0

Python模块/包/库安装(6种方法)

Python模块/包/库安装(6种方法) 冰颖机器人 2016-11-29 21:33:26 一、方法1: 单文件模块 直接把文件拷贝到 $python_dir/Lib 二、方法2: 多文件模块,带setup.py 下载模块包(压缩文件zip...

cswangyx ⋅ 今天 ⋅ 0

零基础学习大数据人工智能,学习路线篇!系统规划大数据之路?

大数据处理技术怎么学习呢?首先我们要学习Python语言和Linux操作系统,这两个是学习大数据的基础,学习的顺序不分前后。 Python:Python 的排名从去年开始就借助人工智能持续上升,现在它已经...

董黎明 ⋅ 今天 ⋅ 0

openJdk和sun jdk的区别

使用过LINUX的人都应该知道,在大多数LINUX发行版本里,内置或者通过软件源安装JDK的话,都是安装的OpenJDK, 那么到底什么是OpenJDK,它与SUN JDK有什么关系和区别呢? 历史上的原因是,Ope...

jason_kiss ⋅ 今天 ⋅ 0

梳理

Redux 是 JavaScript 状态容器,提供可预测化的状态管理。 它是JS的状态容器,是一种解决问题的方式,所以即可以用于 react 也可以用于 vue。 需要理解其思想及实现方式。 应用中所有的 stat...

分秒 ⋅ 今天 ⋅ 0

Java 后台判断是否为ajax请求

/** * 是否是Ajax请求 * @param request * @return */public static boolean isAjax(ServletRequest request){return "XMLHttpRequest".equalsIgnoreCase(((HttpServletReques......

JavaSon712 ⋅ 今天 ⋅ 0

Redis 单线程 为何却需要事务处理并发问题

Redis是单线程处理,也就是命令会顺序执行。那么为什么会存在并发问题呢? 个人理解是,虽然redis是单线程,但是可以同时有多个客户端访问,每个客户端会有 一个线程。客户端访问之间存在竞争...

码代码的小司机 ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部