文档章节

hdoj_1083/poj_1469_Courses 匹配匈牙利算法

電泡泡
 電泡泡
发布于 2013/10/01 14:57
字数 172
阅读 34
收藏 0
点赞 0
评论 0
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;

int ti, N, M, tp, tt;
bool use[310];
int g[110][310], from[310], tot;

bool match(int n){
    for(int i=1; i<=M; i++){
        if(!use[i] && g[n][i]){
            use[i] = 1;
            if(!from[i] || match(from[i])){
                from[i] =n;
                
                //cout<<"*"<<n<<" "<<i<<" "<<endl;
           
                return  true;
            }
        }
    }
    return false;
}

int hungary(){
    tot=0;
    for(int i=1; i<=N; i++){
        memset(use, 0, sizeof(use));
        if(match(i)){
            tot++;
        }
    }
    return tot;
}

int main(){
    cin>>ti;
    while(ti--){
        memset(g, 0, sizeof(g));
        memset(from, 0, sizeof(from));
        cin>>N>>M;
        for(int i=1; i<=N; i++){
            cin>>tp;
            for(int j=1; j<=tp; j++){
                cin>>tt;
                
                //g[tt][i]=true不用建雙向,更新會出錯
                g[i][tt]=true;
            }
        }
        int temp=hungary();
        //cout<<"hungary "<<temp<<endl;
        if(N==temp){
            cout<<"YES"<<endl;
        }
        else{
            cout<<"NO"<<endl;
        }
    }
    //system("pause");
    return 0;
}

© 著作权归作者所有

共有 人打赏支持
電泡泡
粉丝 25
博文 183
码字总数 69717
作品 0
衡阳
poj 1469 COURSES

COURSES 3 33 1 2 32 1 21 13 32 1 32 1 31 1 Sample Output YESNO Source [Submit] [Go Back] [Status] [Discuss] 我的解答: 不清楚每个学生是不是一定要分到课,只考虑每个课都得分到学生,...

locusxt
2013/12/07
0
0
一个搞ACM需要掌握的算法

ACM的竞赛性强,因此自己应该和自己的实际应用联系起来.适合自己的才是好的,有的人不适合搞算法,喜欢系统架构,因此不要看到别人什么就眼红,发挥自己的长处,这才是重要的. 第一阶段:练经典常用...

long0404
2015/06/24
0
0
学习算法之路(转)

路漫漫其修远兮,吾将上下而求索。。。 ======================================================== 转一个搞ACM需要的掌握的算法. 要注意,ACM的竞赛性强,因此自己应该和自己的实际应用联系起...

长平狐
2013/01/06
163
0
算法进阶路径

第一阶段:练经典常用算法,下面的每个算法给我打上十到二十遍,同时自己精简代码, 因为太常用,所以要练到写时不用想,10-15分钟内打完,甚至关掉显示器都可以把程序打 出来. 1.最短路(Fl...

暖冰
2016/04/02
82
1
poj 1274 The Perfect Stall

The Perfect Stall Description Farmer John completed his new barn just last week, complete with all the latest milking technology. Unfortunately, due to engineering problems, all......

locusxt
2013/12/07
0
0
简明刷题指南

Cover 1. 刷题网站 HDUOJ HDOJ Welcome To PKU JudgeOnline POJ PAT image.png Codeforces CodeForces AtCoder Atcoder Virtual Judge Vjudge 2. 刷题步骤 以HDUOJ为例 首先注册网站账号 点击......

SpiffyEight77
01/06
0
0
匈牙利算法

匈牙利算法 有vN 和uN两个点集构成的二分图 通过深度遍历, 找u0-u1匹配增广轨 -------- 为u0找增光轨找到res++ 连线 为u1找增广轨找到res++连线 为u2找增广轨 假如u2能匹配v5,v6的都被u1,u0...

Ink_cherry
2017/05/16
0
0
数学:匈牙利算法

匈牙利算法:它由匈牙利数学家Edmonds于1965年提出,因而得名。此算法的核心就是寻找增广路径,通过增广路径来求二分图最大匹配的一种算法。 通过这个图片来讲述一下。黑色代表ABCD四只小狗,...

pricker
2015/09/12
270
0
二分图算法模板以及相关知识

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

Anxdada
2017/06/22
0
0
hduoj题目分类

基础题:1000、1001、1004、1005、1008、1012、1013、1014、1017、1019、1021、1028、1029、1032、1037、1040、1048、1056、1058、1061、1070、1076、1089、1090、1091、1092、1093、1094、1...

hlearning
2014/02/25
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

大数据教程(2.13):keepalived+nginx(多主多活)高可用集群搭建教程【自动化脚本】

上一章节博主为大家介绍了目前大型互联网项目的keepalived+nginx(主备)高可用系统架构体系,相信大家应该看了博主的文章对keepalived/nginx技术已经有一定的了解,在本节博主将为大家分享k...

em_aaron
5分钟前
0
0
Git 2.18版本发布:支持Git协议v2,提升性能

在最新的官方 Git 客户端正式版2.18中添加了对 Git wire 协议 v2 的支持,并引入了一些性能与 UI 改进的新特性。在 Git 的核心团队成员 Brandon Williams 公开宣布这一消息前几周,Git 协议 ...

六库科技
10分钟前
0
0
Java8新特性之接口

在JDK8以前,我们定义接口类中,方法都是抽象的,并且不能存在静态方法。所有的方法命名规则基本上都是 public [返回类型] [方法名](参数params) throws [异常类型] {}。 JDK8为接口的定义带...

developlee的潇洒人生
48分钟前
0
0
aop + annotation 实现统一日志记录

aop + annotation 实现统一日志记录 在开发中,我们可能需要记录异常日志。由于异常比较分散,每个 service 方法都可能发生异常,如果我们都去做处理,会出现很多重复编码,也不好维护。这种...

长安一梦
58分钟前
2
0
将博客搬至CSDN

AHUSKY
今天
1
0
Python web框架Django学习(1)

1.Django简介 (1)Python下有许多款不同的 Web 框架。Django是重量级选手中最有代表性的一位。许多成功的网站和APP都基于Django。Django是一个开放源代码的Web应用框架,由Python写成。 (2...

十年磨一剑3344
今天
0
0
Databook-数据之书

Databook-数据之书 用于数据分析的Jupyter Notebooks。 不需购买服务器,快速开始自己的数据分析过程。 源码:https://github.com/openthings/databook 作者:openthings,https://github.co...

openthings
今天
7
0
Python PIPEs

https://www.python-course.eu/pipes.php https://www.tutorialspoint.com/python/os_pipe.htm

zungyiu
今天
1
0
gRPC学习笔记

gRPC编程流程 1. proto文件定义 proto文件用于定义需要通过gRPC生成的接口,可以理解为接口定义文档 2. 通过构建工具生成服务基类代码-Maven或Gradle 3. 服务端开发 服务端实现类须实现通过构...

OSC_fly
今天
0
0
Docker Mac (三) Dockerfile 及命令

Dockerfile 最近学习docker的时候,遇到一件怪事,关于docker镜像可能会被破坏,还不知道它会有此措施 所以需要了解构建Dockerfile的正确方法 Dockerfile是由一系列命令和参数构成的脚本,这些命...

___大侠
今天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部