程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> POJ 1469二分圖匹配Hopcroft-Karp算法

POJ 1469二分圖匹配Hopcroft-Karp算法

編輯:C++入門知識

題意:

有N個學生和P門課程,讓你判斷能否構成最大匹配。先輸入一個T,表示有T組測試數據;在輸入N和P,P表示有P門課程,N表示有N個學生。之後有P行,比如:

a a1 a2 a3 a4 a5---第一行。1與a1,a2,a3,a4,a5有匹配。

b b1 b2 b3-----第二行。2與b1,b2,b3有匹配。

如果匹配數等於學生數目則YES;否則為NO;

上交模板,因為用了bfs增廣一系列路徑,所以更快……

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define PI acos(-1.0)
#define mem(a,b) memset(a,b,sizeof(a))
#define sca(a) scanf("%d",&a)
#define sc(a,b) scanf("%d%d",&a,&b)
#define pri(a) printf("%d\n",a)
#define lson i<<1,l,mid
#define rson i<<1|1,mid+1,r
#define MM 50005
#define MN 500
#define INF 0x7fffffff
#define eps 1e-7
using namespace std;
typedef long long ll;
int nx,ny,vis[MM],mx[MM],my[MM],dx[MM],dy[MM];
vectore[MM];
queueq;
bool dfs(int u)
{
    int i,l=e[u].size();
    for(i=0;i

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved