hdu 2444 The Accomodation of Students (交叉染色法+匈牙利算法)

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