HDU 1150 && HDU 1151 二分匹配模版题
九野的博客，转载请注明出处：http://blog.csdn.net/acmmmm/article/details/12224561
题意：
左点集范围 右点集范围 映射边数
映射边编号 左点 右点
注意一下点集的范围是1开始的即可
HDU 1150:
#include<iostream> #include<stdio.h> #include<string> #include<string.h> #include<algorithm> #include<set> #include <cstdio> #include <cstring> #include <iostream> #include <math.h> #include <queue> #define N 200#define ll int #define L(x) x<<1 #define R(x) x<<1|1 #define Mid(x,y) (x+y)>>1 using namespace std; inline ll Min(ll a,ll b){return a>b?b:a;} inline ll Max(ll a,ll b){return a>b?a:b;} int lef[N*N];//lef[v]表示右边点v 当前连接的点bool T[N*N];//右边的点是否连过vector<int>G[N];//G是映射，G[X集].push_back(Y集) 注意G的初始化int pn,pm;bool match(int x){for(int i=0;i<G[x].size();i++){int v=G[x][i];if(!T[v]){T[v]=true;if(lef[v]==-1||match(lef[v])){lef[v]=x;return true;}}}return false;}void solve(){int ans=0;memset(lef,-1,sizeof(lef));for(int i=0;i<pn;i++)//左右点集匹配，左点集是 0-(pn-1) 右点集是G[左点].size(){memset(T,0,sizeof(T));if(match(i))ans++;}printf("%d\n",ans);} int main(){ int i,j,way;while(scanf("%d",&pn), pn){scanf("%d%d",&pm,&way);for(i=0;i<=pn;i++)G[i].clear();while(way--){int num,a,b;scanf("%d %d %d",&num,&a,&b);if(a&&b)G[a-1].push_back(b-1);}solve();} return 0; }//HDU 1151:
#include<iostream> #include<stdio.h> #include<string> #include<string.h> #include<algorithm> #include<set> #include <cstdio> #include <cstring> #include <iostream> #include <math.h> #include <queue> #define N 200#define ll int #define L(x) x<<1 #define R(x) x<<1|1 #define Mid(x,y) (x+y)>>1 using namespace std; inline ll Min(ll a,ll b){return a>b?b:a;} inline ll Max(ll a,ll b){return a>b?a:b;} int lef[N*N];//lef[v]表示右边点v 当前连接的点bool T[N*N];//右边的点是否连过vector<int>G[N];//G是映射，G[X集].push_back(Y集) 注意G的初始化int pn,pm;bool match(int x){ for(int i=0;i<G[x].size();i++) { int v=G[x][i]; if(!T[v]) { T[v]=true; if(lef[v]==-1||match(lef[v])) { lef[v]=x; return true; } } } return false;}
void solve(){ int ans=0; memset(lef,-1,sizeof(lef)); for(int i=0;i<pn;i++)//左右点集匹配，左点集是 0-(pn-1) 右点集是G[左点].size() { memset(T,0,sizeof(T)); if(match(i))ans++; } printf("%d\n",pn-ans);} int main(){ int way,t;scanf("%d",&t); while(t--){ scanf("%d%d", &pn, &way);
for(int i=0; i<=pn ; i++)G[i].clear(); while(way--){ int a,b; scanf("%d %d",&a,&b); G[a-1].push_back(b-1); } solve(); } return 0; } /*
*/