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;  }  /*
*/