`

【HDU、二分匹配、最大匹配/新增1005+1008代码】总结

阅读更多
KIDx 的解题报告

给出基本定义:




第一题:hdu 1054 Strategic Game
http://acm.hdu.edu.cn/showproblem.php?pid=1054
求:最小顶点覆盖 == 【最大匹配(双向建图)】/2
证明:最小顶点覆盖 == 最大匹配http://www.matrix67.com/blog/archives/116



第二题:hdu 1068 Girls and Boys
http://acm.hdu.edu.cn/showproblem.php?pid=1068
求:最大独立集 == |P| 减 【最大匹配(双向建图)】/2
由于只能是男女之间有关系,所以必然不存在奇圈【长度为奇数的环】
必然是二分图


如图红点为最小覆盖顶点,有3个,除了这三个点以外的点所组成的集合就是最大独立集,两两之间无任何关系


第三题:hdu 1150 Machine Schedule
http://acm.hdu.edu.cn/showproblem.php?pid=1150
求:最小顶点覆盖 == 最大匹配



第四题:hdu 1151 Air Raid
http://acm.hdu.edu.cn/showproblem.php?pid=1151
求:最小路径覆盖 == |P| 减 【最大匹配】,适用于有向无环图【DAG图】
有环不一定成立……
对于公式:最小路径覆盖=|P|-最大匹配数;
可以这么来理解:
如果匹配数为零,那么P中不存在有向边,于是显然有:
最小路径覆盖=|P|-最大匹配数=|P|-0=|P|;
即P的最小路径覆盖数为|P|;
P'中不在于匹配边时,路径覆盖数为|P|;
如果在P'中增加一条匹配边pi'-->pj'',那么在图P的路径覆盖中就存在一条由pi连接pj的边,也就是说pi与pj 在一条路径上,于是路径覆盖数就可以减少一个;
如此继续增加匹配边,每增加一条,路径覆盖数就减少一条;



第五题:hdu 1281 棋盘游戏
http://acm.hdu.edu.cn/showproblem.php?pid=1281
①求在白色格子最多能放多少个车
放车的条件:
车与车之间不可同行或者同列
根据最大匹配的特性,每个匹配木有公共点,如果把行和列看成点进行最大匹配就可以求出既不同行也不同列的匹配个数maxs,也就是答案了
②求关键放车点的个数【也就是说这个点必须放上一个车才能达到最大匹配数】
思路:枚举可放点【其实就是可匹配的一条边】,让它无效化,然后再求出一个最大匹配tp,如果tp<maxs,说明这条边是关键,所以关键点+1


第六题:hdu 1498 50 years, 50 colors
http://acm.hdu.edu.cn/showproblem.php?pid=1498
爆破气球的条件:一次只能爆破一行或一列,选择一种颜色爆破,给你k次机会,输出不可能爆破完的气球的颜色
利用最大匹配的特性,行和列进行匹配,匹配条件是颜色相同,可以看成最小顶点覆盖,一个匹配边就把同一行或同一列的气球都爆破了
枚举所有颜色分别求出行和列的最大匹配maxs,那么这种颜色至少需要maxs次的爆破才可爆完,则如果 k < maxs 就不可能爆完咯


第七题:hdu 1528and1962 Card Game Cheater
http://acm.hdu.edu.cn/showproblem.php?pid=1528
http://acm.hdu.edu.cn/showproblem.php?pid=1962
给出两组牌,要你配对,求第二组牌赢得的最多分数,对应的牌大的得一分
跟田忌赛马类似
直接求最大匹配,匹配条件是第二组的牌大于第一组的牌



第八题:hdu 1507 Uncle Tom's Inherited Land*
http://acm.hdu.edu.cn/showproblem.php?pid=1507
格子间的匹配,求最大匹配,匹配条件是2个格子相邻,且2个格子都是陆地
给格子编号就可以套模板了【注意要双向建图】


第五题游戏棋盘代码:
#include <iostream>
#include <fstream>
#include <algorithm>
#include <string>
#include <set>
//#include <map>
#include <queue>
#include <utility>
#include <iomanip>
#include <stack>
#include <list>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
//#include <ctime>
#include <ctype.h>
using namespace std;
#define LL __int64
#define inf 0x3fffffff
#define M 105

struct pos{
	int v;
	int i;
};
vector<pos> g[M];
int match[M], n, key;
bool vis[M];

void init ()
{
	int i;
	for (i = 1; i <= n; i++)
		g[i].clear();
}

bool dfs (int u)	//dfs寻找增广路
{
	int i, v;
	for (i = 0; i < g[u].size(); i++)    //v是二分图右边的元素
	{
		v = g[u][i].v;
		if (g[u][i].i == key)    //u-v这条边的编号是key的话无效
			continue;
		if (!vis[v])
		{
			vis[v] = true;
			if (match[v] == 0 || dfs (match[v]))
			{
				match[v] = u;
				return true;
			}
		}
	}
	return false;
}

int main()
{
	int m, k, u, v, maxs, tp, imp, i, cc = 1;
	pos x;
	while (~scanf ("%d%d%d", &n, &m, &k))
	{
		init();
		for (i = 1; i <= k; i++)
		{
			scanf ("%d%d", &u, &v);
			x.v = v, x.i = i;
			g[u].push_back (x);    //u-v边的编号从1到k
		}
		maxs = imp = 0;
		for (key = 0; key <= k; key++)    //枚举要无效化的边编号
		{
		/**********一次匈牙利算法**********/
			tp = 0;
			memset (match, 0, sizeof(match));    //匹配对象
			for (i = 1; i <= n; i++)    //i是二分图左边的元素
			{
				memset (vis, false, sizeof(vis));	//访问标记
				if (dfs (i))    //找到增广路匹配数+1
					tp++;
			}
		/**********一次匈牙利算法**********/
			if (maxs < tp)
				maxs = tp;
			if (tp < maxs)    //删了key这条边就没法得到最大匹配,说明这条边是关键点
				imp++;
		}
		printf ("Board %d have %d important blanks for %d chessmen.\n", cc++, imp, maxs);
	}
	return 0;
}


最后一题:Uncle Tom's Inherited Land*
#include <iostream>
#include <fstream>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <utility>
#include <stack>
#include <list>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
//#include <ctime>
#include <ctype.h>
using namespace std;
#define L long long
#define inf 0x3fffffff
#define M 10005

bool vis[M], num[M];
int n, match[M], c;

bool dfs (int u)	//由于是双向匹配,所以与u相邻的点都要尝试跟u匹配
{
    int i;
	i = u + 1;
	if (i % c != 0)
	{
		if (!num[i] && !vis[i])
        {
            vis[i] = true;
            if (match[i] == -1 || dfs (match[i]))
            {
                match[i] = u;
                return true;
            }
        }
	}
	i = u + c;
	if (i < n)
	{
		if (!num[i] && !vis[i])
        {
            vis[i] = true;
            if (match[i] == -1 || dfs (match[i]))
            {
                match[i] = u;
                return true;
            }
        }
	}
    i = u - 1;
    if (i >= 0 && i % c != c - 1)
    {
        if (!num[i] && !vis[i])
        {
            vis[i] = true;
            if (match[i] == -1 || dfs (match[i]))
            {
                match[i] = u;
                return true;
            }
        }
    }
    i = u - c;
    if (i >= 0)
    {
        if (!num[i] && !vis[i])
        {
            vis[i] = true;
            if (match[i] == -1 || dfs (match[i]))
            {
                match[i] = u;
                return true;
            }
        }
    }
    return false;
}

int main()
{
    int r, m, x, y, maxs, tx, ty, i;
    while (scanf ("%d%d", &r, &c), (r||c))
    {
        n = r * c;
        scanf ("%d", &m);
        memset (num, false, sizeof(num));
        while (m--)
        {
            scanf ("%d%d", &x, &y);
            num[(x-1)*c+y-1] = true;    //坐标转化成编号
        }
	/****************一次匈牙利****************/
        maxs = 0;
        memset (match, -1, sizeof(match));
        for (i = 0; i < n; i++)
        {
            if (num[i])
                continue;
            memset (vis, false, sizeof(vis));
            if (dfs (i))
                maxs++;
        }
	/****************一次匈牙利****************/
        printf ("%d\n", maxs/2);	//双向建图的结果
        for (i = 0; i < n; i++)
        {
            if (!num[i] && match[i] > -1 && !num[match[i]])	
            {
          //判断是否有匹配,并且判断是否已输出过
                x = i / c;    //编号变回坐标
                y = i % c;
                tx = match[i] / c;
                ty = match[i] % c;
                num[i] = num[match[i]] = true;	//一个格子匹配后不可再次出现
                printf ("(%d,%d)--(%d,%d)\n", x+1, y+1, tx+1, ty+1);
            }
        }
    }
    return 0;
}

  • 大小: 3.8 KB
  • 大小: 17.3 KB
  • 大小: 163.1 KB
3
3
分享到:
评论

相关推荐

    vc2019中 源文件<bits/stdc++.h>无法打开

    在C++中,头文件是用来包含特定功能的代码段,例如数据类型、函数声明或类定义。例如: - `&lt;cassert&gt;`:包含断言宏,用于调试。 - `&lt;cctype&gt;`:提供字符分类和转换的函数,如`isdigit()`和`isupper()`。 - `&lt;cmath&gt;...

    HDU二分匹配及其应用

    HDU二分匹配及其应用,此PPT是刘春英老师版权所有, 特此贡献给广大编程爱好者,特别是对于ACMer

    二分匹配题集

    ### 二分匹配题集概览 #### 一、基础知识 **匹配**:在一个二分图\( G \)中,存在一个子图\( G' \),若\( G' \)的边集中任意两条边不共用同一个顶点,则称\( G' \)的边集为\( G \)的一个匹配。 **最大匹配**:在...

    hdu 300+ AC 代码

    HDU 300+ AC 代码集合是一个包含超过300个已通过验证的算法解决方案的资源,这些代码主要用于解决各类计算机编程竞赛中的问题。这些竞赛通常由杭州电子科技大学(HDU)主办,旨在提升参赛者的算法设计、编程和问题...

    万能头文件stdc++.h

    HDU部分支持(G++支持,C++不支持)。 其他国外的oj,还有台湾的oj都支持,CF,Topcoder也都支持。 当然,其实这是一个偷懒的写法,但是会降低编译速度(为何会降低编译速度,我还不能知道,等到之后学编译原理再...

    (HDUACM2010版_13)二分匹配及其应用

    杭电ACM课件2014版之(HDUACM2010版_13)二分匹配及其应用

    ACM HDU题目分类

    ACM HDU 题目分类是指对 HDU 在线判题系统中题目的分类,总结了大约十来个分类。这些分类将有助于编程选手更好地理解和解决问题。 DP 问题 DP(Dynamic Programming,动态规划)是一种非常重要的算法思想,在 ACM ...

    HDUACM2010版13二分匹配及其应用.ppt

    HDUACM2010版13二分匹配及其应用.ppt

    HDU最全ac代码

    "HDU最全ac代码"这个压缩包很可能是包含了在HDU平台上解题通过的完整源代码集合,旨在帮助学习者理解和掌握各种算法,提升编程解决问题的能力。 首先,我们来了解一下ACM/ICPC比赛。这是一项全球性的编程竞赛,参赛...

    ACM hdu 线段树题目+源代码

    ACM hdu 线段树题目+源代码 线段树是一种非常重要的数据结构,它广泛应用于算法竞赛和实际编程中。今天,我们将通过 ACM hdu 的几个题目来学习和掌握线段树的基本概念和应用。 线段树的基本概念 线段树是一种...

    二分匹配及其应用

    "HDUACM2010版_13)二分匹配及其应用.ppt"这份资料应该包含了具体的实例和解题策略,对于参加ACM竞赛或者对算法感兴趣的同学们来说,是一份非常有价值的参考资料。通过学习和实践,我们可以掌握如何在实际问题中有效...

    hdu2000-2014ac代码

    2. **基本算法**:排序(冒泡、选择、插入、快速、归并、堆排序等)、查找(顺序、二分查找等)、递归、动态规划、贪心策略、回溯法等。这些都是解决问题的基础工具,尤其在处理复杂度优化和求解最优化问题时。 3. ...

    杭电HDU ACM 1005

    杭电ACM1005题源代码,AC了的程序,无问题……

    acmhdu1005

    hdu 1005.比较简单的一道题,有兴趣的可以看看。

    HDU1059的代码

    HDU1059的代码

    hdu acm 教案(10)

    在计算机科学和算法竞赛(如HDU ACM)中,二分匹配是一种非常重要的图论概念,常用于解决一系列优化问题。它源于数学中的匹配理论,尤其是在网络流问题和分配问题中有着广泛的应用。二分匹配问题通常在两个大小相等...

    Hdu1000—2169部分代码

    2. **搜索算法**:深度优先搜索(DFS)、广度优先搜索(BFS)、二分查找等。 3. **动态规划**:解决具有重叠子问题和最优子结构的问题。 4. **图论算法**:最短路径算法(Dijkstra、Floyd-Warshall)、拓扑排序、...

    万能头文件#include“bitsstdc++.h” (2).pdf

    总结来说,`#include &lt;bits/stdc++.h&gt;`虽然在编程竞赛或快速原型开发中提供了便捷,但其非标准性、可能导致的编译性能下降、不可移植性和可能的命名冲突等问题,使得在正规的开发环境中应谨慎使用。在编写专业或大型...

    hdu-acm源代码(上百道源代码)

    HDU-ACM源代码是针对国际大学生程序设计竞赛(ICPC,International Collegiate Programming Contest)中的题目,由参赛者或爱好者编写的解决方案集合。这个压缩包包含上百个源代码,涉及了各种算法和编程技巧,是...

    解题代码 hdu1241

    根据给定的文件信息,我们可以得知这是一段用于解决HDU(Hdu Online Judge)编号为1241的问题的代码。该代码主要采用了深度优先搜索(DFS)算法来解决问题。 #### 二、DFS(Depth First Search)算法原理 **定义:...

Global site tag (gtag.js) - Google Analytics