poj 1422 Air Raid (DAG的最小路径覆盖，匈牙利算法)

  1/* ***********************************************
  2Author :111qqz
  3Created Time :2016年05月26日 星期四 20时24分15秒
  4File Name :code/poj/r2594.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=505;
 34int n,m;
 35bool conc[N][N];
 36bool vis[N];
 37int link[N];
 38void floyd()
 39{
 40    for ( int k = 1 ; k <= n ; k++)
 41	for ( int i = 1 ; i <= n ; i++)
 42	    for ( int j = 1 ; j <= n ; j++)
 43		if (conc[i][k]&&conc[k][j]) conc[i][j] = true;
 44}
 45
 46
 47bool dfs( int u)
 48{
 49    for ( int i = 1 ; i <= n ; i++)
 50    {
 51	if (conc[u][i])
 52	{
 53	    if (vis[i]) continue;
 54	    vis[i] = true;
 55	    if (link[i]==-1||dfs(link[i]))
 56	    {
 57		link[i] = u;
 58		return true;
 59	    }
 60	}
 61    }
 62    return false;
 63}
 64int hungary()
 65{
 66    int res = 0 ;
 67    ms(link,-1);
 68    for ( int i = 1 ; i <= n ; i++)
 69    {
 70	ms(vis,false);
 71	if (dfs(i)) res++;
 72    }
 73    return res;
 74}
 75int main()
 76{
 77	#ifndef  ONLINE_JUDGE
 78	freopen("code/in.txt","r",stdin);
 79  #endif
 80
 81	while (scanf("%d%d",&n,&m)!=EOF)
 82	{
 83	    if (n==0&&m==0) break;
 84	    ms(conc,false);
 85	    for ( int i = 1 ; i <= m ; i++)
 86	    {
 87		int u,v;
 88		scanf("%d%d",&u,&v);
 89		conc[u][v] = true;
 90	    }
 91
 92	    floyd();
 93	    int ans = hungary();
 94	    printf("%d\n",n-ans);
 95
 96	}
 97
 98  #ifndef ONLINE_JUDGE
 99  fclose(stdin);
100  #endif
101    return 0;
102}