poj 1422 Air Raid (DAG的最小路径覆盖，匈牙利算法)
poj 1422题目链接
题意+思路：DAG的最小路径覆盖。。。匈牙利算法。。。poj 2594的低配版。。
代码实现 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}