文档章节

hdoj_1083/poj_1469_Courses 匹配匈牙利算法

電泡泡
 電泡泡
发布于 2013/10/01 14:57
字数 172
阅读 34
收藏 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

没有更多内容

加载失败,请刷新页面

加载更多

jQuery学习笔记180924

jQuery - AJAX 简介 什么是 AJAX? AJAX = 异步 JavaScript 和 XML(Asynchronous JavaScript and XML)。 简短地说,在不重载整个网页的情况下,AJAX 通过后台加载数据,并在网页上进行显示...

颖伙虫
27分钟前
1
0
springboot整合vue小试牛刀

序 本文主要研究一下如何在springboot工程整合vue maven <dependency> <groupId>org.springframework.boot</groupId> <artifactId>spring-boot-starter-we......

go4it
28分钟前
1
0
使用python的profiler工具

主要用来检测python coding的执行时间 fly profiler

steel7c4
33分钟前
0
0
大数据日知录笔记

硬件成本的快速下降,使得电子设备的无处不在成为可能,数据无处不在,无时不在. IBM用3V(Volume,Velocity,Variety)来描述大数据的特点,后来又增加了Value这个维度,即价值密度低的数据成为大数据...

凌渡
42分钟前
0
0
IDEA、WebStorm最新永久激活方式

今天早上一大早打开IDEA发现激活已过期,遂开始寻找激活码。但是一直不成功,后来终于找到一种比较靠谱的激活方式。在此记录下来,以备不时之需。 目前网上现有的激活方式大概有这么三种 激活...

耒耒耒耒耒
今天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部