poj 3041 Asteroids (二分图的最小顶点覆盖，匈牙利算法)
poj 3041题目链接 题意：一个nn的网格中，有k个大小为11的小行星，现在可以用激光枪每次消灭一行的小行星或者消灭一列的小行星。问最少需要使用多少次激光枪消灭所有的小行星。
思路：一个建图技巧是：对于网格图，我们可以把某个格子的横纵坐标看成点，而格子所代表的内容看成边来建图。
如果我们按照这样的方式建图，那么这道题的行或者列就成了点，而小行星就成了边。我们要做得是选最少的点，使得这些点覆盖所有的边。
根据Knoig定理，二分图的最小顶点覆盖数等于二分图的最大匹配数。
匈牙利一遍即可。1A
/* ***********************************************
Author :111qqz
Created Time :2016年05月30日 星期一 21时42分55秒
File Name :code/poj/3041.cpp
************************************************ */
1#include <cstdio>
2#include <cstring>
3#include <iostream>
4#include <algorithm>
5#include <vector>
6#include <queue>
7#include <set>
8#include <map>
9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define fst first
14#define sec second
15#define lson l,m,rt<<1
16#define rson m+1,r,rt<<1|1
17#define ms(a,x) memset(a,x,sizeof(a))
18typedef long long LL;
19#define pi pair < int ,int >
20#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6const int N=1E3+7;
7const int M=1E4+7;
8int n,k;
9int cnt;
10struct Edge
11{
12 int v;
13 int nxt;
14}edge[M];
1int head[N];
2bool vis[N];
3int link[N];
1void addedge( int u,int v)
2{
3 edge[cnt].v = v;
4 edge[cnt].nxt = head[u];
5 head[u] = cnt;
6 cnt++;
7}
8void init()
9{
10 ms(head,-1);
11 cnt = 0 ;
12}
1int find( int u)
2{
3 for ( int i = head[u] ; i !=-1 ; i = edge[i].nxt)
4 {
5 int v = edge[i].v;
6 if (vis[v]) continue;
7 vis[v] = true;
8 if (link[v]==-1||find(link[v]))
9 {
10 link[v] = u;
11 return true;
12 }
13 }
14 return false;
15}
16int hungary()
17{
18 int res = 0 ;
19 ms(link,-1);
20 for ( int i = 1 ; i <= n ; i ++)
21 {
22 ms(vis,false);
23 if (find(i)) res++;
24 }
25 return res;
26}
27int main()
28{
29 #ifndef ONLINE_JUDGE
30 freopen("code/in.txt","r",stdin);
31 #endif
1 init();
2 scanf("%d%d",&n,&k);
3 for ( int i = 1 ; i <= k ; i++)
4 {
5 int u,v;
6 scanf("%d%d",&u,&v);
7 addedge(u,v+n);
8 }
9 int ans = hungary();
10 printf("%d\n",ans);
1 #ifndef ONLINE_JUDGE
2 fclose(stdin);
3 #endif
4 return 0;
5}