POJ-1469 COURSES ( 匈牙利算法 dfs + bfs )
题目链接: http://poj.org/problem?id=1469
Description
- every student in the committee represents a different course (a student can represent a course if he/she visits that course)
- each course has a representative in the committee
Input
program should read sets of data from the std input. The first line of
the input contains the number of the data sets. Each data set is
presented in the following format:
P N
Count1 Student1 1 Student1 2 ... Student1 Count1
Count2 Student2 1 Student2 2 ... Student2 Count2
...
CountP StudentP 1 StudentP 2 ... StudentP CountP
The first line in each data set contains two positive integers
separated by one blank: P (1 <= P <= 100) - the number of courses
and N (1 <= N <= 300) - the number of students. The next P lines
describe in sequence of the courses �from course 1 to course P, each
line describing a course. The description of course i is a line that
starts with an integer Count i (0 <= Count i <= N) representing
the number of students visiting course i. Next, after a blank, you抣l
find the Count i students, visiting the course, each two consecutive
separated by one blank. Students are numbered with the positive integers
from 1 to N.
There are no blank lines between consecutive sets of data. Input data are correct.
Output
result of the program is on the standard output. For each input data set
the program prints on a single line "YES" if it is possible to form a
committee and "NO" otherwise. There should not be any leading blanks at
the start of the line.
Sample Input
2
3 3
3 1 2 3
2 1 2
1 1
3 3
2 1 3
2 1 3
1 1
Sample Output
YES
NO 模板题,使用匈利亚算法找最大匹配,匈利亚算法有dfs和bfs两种实现,dfs代码短,容易理解,bfs有点复杂,据说速度要快一点,我两种都写了一下。
//dfs
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std; int p, n;
bool visit[][];
int stop[];
bool used[]; bool search( int x ){
for( int i = ; i <= n; i++ )
if( visit[x][i] && !used[i] ){
used[i] = true;
if( stop[i] == || search( stop[i] ) ){
stop[i] = x;
return true;
}
} return false;
} int main(){
int T;
scanf( "%d", &T );
while( T-- ){
memset( visit, false, sizeof( visit ) );
memset( stop, , sizeof( stop ) );
scanf( "%d%d", &p, &n );
int flag = true; for( int i = ; i <= p; i++ ){
int temp, a;
scanf( "%d", &temp );
while( temp-- ){
scanf( "%d", &a );
visit[i][a] = true;
}
} for( int i = ; i <= p; i++ ){
if( !flag ) continue;
else{
memset( used, false, sizeof( used ) );
if( !search( i ) ){
flag = false;
}
}
} if( flag ) printf( "YES\n" );
else printf( "NO\n" );
} return ;
}
//bfs
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std; int n, p;
bool visit[][];
int ptos[], stop[], pre[];//ptos,stop记录匹配,pre记录课程匹配时的前驱点
int flag[];//寻找增广路时判断是否已经添加过 int maxmatch(){
int ans = ;
memset( ptos, , sizeof( ptos ) );
memset( stop, , sizeof( stop ) );
memset( flag, false, sizeof( flag ) ); for( int i = ; i <= p; i++ ){ if( ptos[i] == ){//没有匹配
queue<int> Q;
Q.push( i );
pre[i] = ;
bool ok = false;//判断是否找到增广路 while( !Q.empty() && !ok ){//没有找到增广路
int u = Q.front();
Q.pop(); for( int k = ; k <= n && !ok; k++ ){//开始寻找增广路
if( visit[u][k] && flag[k] != i ){
flag[k] = i;
Q.push( stop[k] );
if( stop[k] == ){
ok = true;
int tempp = u,temps = k;
while( tempp != ){//改变匹配
int x = ptos[tempp];
ptos[tempp] = temps;
stop[temps] = tempp;
tempp = pre[tempp];
temps = x;
}
}
else pre[stop[k]] = u;
}
}
}
if( ptos[i] != ) ans++;
}
} return ans;
} int main(){
int T;
scanf( "%d", &T );
while( T-- ){
memset( visit, false, sizeof( visit ) );
scanf( "%d%d", &p, &n ); int temp, a;
for( int i = ; i <= p; i++ ){
scanf( "%d", &temp );
while( temp-- ){
scanf( "%d", &a );
visit[i][a] = true;
}
} if( p == maxmatch() ) printf( "YES\n" );
else printf( "NO\n" );
} return ;
}
最新文章
- contains与compareDocumentPosition
- 深入理解javascript对象系列第二篇——属性操作
- Android 学习笔记之Volley开源框架解析(二)
- [AFUI]App Framework Quickstart
- QT自绘标题和边框
- 关于Java中Arrays.sort()方法TLE
- 使用vim编写hexo文档,并用ultisnips/snipmates/snippets插件补全
- dedecms 下载时弹出提示登录框或直接下载
- ASP.Net Web API 输出缓存 转载 -- Output caching in ASP.NET Web API
- interface 界面&;接口
- class, extends和super es6语法
- myeclipse中的项目 如何在项目视窗中显示setting,classpath等配置文件
- laravel 实现增 与查
- goaccess geoip 测试
- 重复打印相同内容(Doc档)的时候自动生成打印编号
- javase高级技术 - 泛型
- golang container heap&;sort
- MySQL--常见ALTER TABLE 操作
- js和jquery判断该元素中是否有指定class
- javascript常用方法和技巧