文档章节

hdoj_1083/poj_1469_Courses 匹配匈牙利算法

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

© 著作权归作者所有

共有 人打赏支持
上一篇: 状态dp
電泡泡
粉丝 24
博文 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
算法进阶路径

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

暖冰
2016/04/02
82
1
学习算法之路(转)

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

长平狐
2013/01/06
163
0
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

没有更多内容

加载失败,请刷新页面

加载更多

高并发编程:解析HashMap

底层实现原理 在JDK1.8以前版本中,HashMap的实现是数组+链表,它的缺点是即使哈希函数选择的再好,也很难达到元素百分百均匀分布,而且当HashMap中有大量元素都存到同一个桶中时,这个桶会有...

小刀爱编程
12分钟前
0
0
程序员请不要假装很努力,因为结果不会陪你演戏

前言: 我一直相信这样一句话:真正的危机,来源于在正确的时间做不正确的事。没有在正确的时间,为下一步做出积累,这才是危机的根源。 比如,当你迈过了30岁这个坎,你的能力还局限于程序的...

Java干货分享
17分钟前
1
0
Fio随机读IOPS测试值可能偏大的原因分析

问题描述: 在使用fio进行虚拟机磁盘(Ceph的RBD,格式化为ext4文件系统)的IOPS测试时,发现randread比预估值高许多; 在使用相同参数进行randwrite测试之后,再进行randread时会出现此现象...

LastRitter
21分钟前
0
0
JavaScript引用类型Object常见用法实例分析

1、JavaScript数据类型 (1)基本类型 5种基本类型:Undefined、Null、Boolean、Number、String (2)引用类型 5种引用类型:Object、Array、Date、RepExp、Function (3)基本类型与引用类型的异同...

peakedness丶
28分钟前
0
0
教你理清SpringBoot与SpringMVC的关系

spring boot就是一个大框架里面包含了许许多多的东西,其中spring就是最核心的内容之一,当然就包含spring mvc。spring mvc 是只是spring 处理web层请求的一个模块。因此他们的关系大概就是这...

别打我会飞
32分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部