poj 3041 Asteroids (匈牙利算法---二分图最大匹配)
题目：http://poj.org/problem?id=3041
在二分图中，最小点覆盖数=最大匹配数，把光束模型成顶点，小星星模型成连接对应光束的边，这样，等价于求最小点覆盖。
#include<iostream>#include<vector>using namespace std;const int MAXN=501*2;vector<int> G[MAXN];int N,K;int match[MAXN];bool used[MAXN];void add_edge(int u,int v){G[u].push_back(v);G[v].push_back(u);}bool dfs(int v){used[v]=1;for(int i=0;i<G[v].size();i++){int u=G[v][i],w=match[u];if(w<0 || !used[w] && dfs(w)){ match[u]=v;match[v]=u;cout<<u<<" "<<v<<endl; return 1;}}return 0;}int main(){while(cin>>N>>K){for(int i=0;i<K;i++){int u,v;cin>>u>>v;add_edge(u,v+N);}int res=0;memset(match,-1,sizeof(match));for(int v=1;v<=N*2;v++){if(match[v]<0){memset(used,0,sizeof(used));if(dfs(v)) res++;}}cout<<res<<endl;}return 0;}很重要的一个概念就是 增广路（交错路），要明白为什么每次取反之后匹配数会增加一，具体的算法解释自己谷歌吧。