↓ Skip to main content
111qqz’s blog
  1. Tags/

二分图匹配

2016

poj 1274 The Perfect Stall （匈牙利算法）

·1 min
ACM 二分图匹配 匈牙利算法
poj 1274题目链接 裸的匈牙利。 1/* *********************************************** 2Author :111qqz 3Created Time :2016年05月25日 星期三 17时49分22秒 4File Name :code/poj/1274.cpp 5************************************************ */ 6 7#include <cstdio> 8#include <cstring> 9#include <iostream> 10#include <algorithm> 11#include <vector> 12#include <queue> 13#include <set> 14#include <map> 15#include <string> 16#include <cmath> 17#include <cstdlib> 18#include <ctime> 19#define fst first 20#define sec second 21#define lson l,m,rt<<1 22#define rson m+1,r,rt<<1|1 23#define ms(a,x) memset(a,x,sizeof(a)) 24typedef long long LL; 25#define pi pair < int ,int > 26#define MP make_pair 27 28using namespace std; 29const double eps = 1E-8; 30const int dx4[4]={1,0,0,-1}; 31const int dy4[4]={0,-1,1,0}; 32const int inf = 0x3f3f3f3f; 33const int N=405; 34int n,m; 35int head[N]; 36int cnt; 37int link[N]; 38bool vis[N]; 39struct Edge 40{ 41 int v; 42 int nxt; 43}edge[N*N]; 44void addedge(int u,int v) 45{ 46 edge[cnt].v = v; 47 edge[cnt].nxt = head[u]; 48 head[u] = cnt; 49 cnt++; 50} 51 52bool dfs( int u) 53{ 54 // cout<<"u:"<<u<<endl; 55 for ( int i = head[u] ; i!=-1 ; i = edge[i].nxt) 56 { 57 int v = edge[i].v; 58// cout<<"v:"<<v<<endl; 59 if (vis[v]) continue; 60 vis[v] = true; 61 62 if (link[v]==-1||dfs(link[v])) 63 { 64 link[v] = u; 65 return true; 66 } 67 } 68 return false; 69} 70int hung() 71{ 72 int res = 0 ; 73 ms(link,-1); 74 for ( int i = 1 ; i <= n ; i++) 75 { 76 ms(vis,false); 77 if (dfs(i)) res++; 78 } 79 80 return res; 81} 82int main() 83{ 84 #ifndef ONLINE_JUDGE 85 freopen("code/in.txt","r",stdin); 86 #endif 87 88 while (scanf("%d%d",&n,&m)!=EOF) 89 { 90 ms(head,-1); 91 cnt = 0 ; 92 93 for ( int i = 1 ; i <= n ; i++) 94 { 95 int num; 96 scanf("%d",&num); 97 while (num--) 98 { 99 int x; 100 scanf("%d",&x); 101 x = x + n; 102 addedge(i,x); 103 } 104 } 105 int ans = hung(); 106 printf("%d\n",ans); 107 } 108 109 #ifndef ONLINE_JUDGE 110 fclose(stdin); 111 #endif 112 return 0; 113}