<span>HNU13377 Book Club（二分匹配）</span>
题意：有n个人，m种需求，给出m行，每行a,b代表a想要的书在b那里，问能不能通过交换的方法来满足每个人的需求
思路：这题有好多做法。。刚上来思路也有好多
想到了判环，但是如果两环相切这判断很罗嗦，干脆用二分匹配来的直接
就是n与n匹配，想清楚这点就很简单了，版子题了
就是人跟人的最大匹配数嘛。。
/* *********************************************** Author :devil Created Time :2016/4/4 14:36:38 ************************************************ */ #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <string> #include <cmath> #include <stdlib.h> using namespace std; const int N=10010; vector<int>eg[N]; int linker[N]; bool vis[N]; bool dfs(int u) { for(int i=0;i<eg[u].size();i++) { int to=eg[u][i]; if(!vis[to]) { vis[to]=1; if(linker[to]==-1||dfs(linker[to])) { linker[to]=u; return 1; } } } return 0; } int main() { //freopen("in.txt","r",stdin); int n,m,x,y; while(~scanf("%d%d",&n,&m)) { for(int i=0;i<n;i++) eg[i].clear(); for(int i=0;i<m;i++) { scanf("%d%d",&x,&y); eg[x].push_back(y); } memset(linker,-1,sizeof(linker)); for(int i=0;i<n;i++) { memset(vis,0,sizeof(vis)); dfs(i); } int flag=1; for(int i=0;i<n;i++) { if(linker[i]==-1) { flag=0; break; } } if(flag) printf("YES\n"); else printf("NO\n"); } return 0; }
