首页 > 代码库 > BZOJ 1741: [Usaco2005 nov]Asteroids 穿越小行星群
BZOJ 1741: [Usaco2005 nov]Asteroids 穿越小行星群
Description
贝茜想驾驶她的飞船穿过危险的小行星群．小行星群是一个NxN的网格(1≤N≤500)，在网格内有K个小行星(1≤K≤10000)． 幸运地是贝茜有一个很强大的武器，一次可以消除所有在一行或一列中的小行星，这种武器很贵，所以她希望尽量地少用．给出所有的小行星的位置，算出贝茜最少需要多少次射击就能消除所有的小行星．
Input
第1行：两个整数N和K，用一个空格隔开．
第2行至K+1行：每一行有两个空格隔开的整数R，C(1≤R，C≤N)，分别表示小行星所在的行和列．
Output
一个整数表示贝茜需要的最少射击次数，可以消除所有的小行星
题解：
二分图，两列点分别表示行、列。
对于一个点(x,y) 由 x向y连边。
最小覆盖即是答案。
代码：
#include<cstdio>#include<algorithm>#include<cstring>//by zrt//problem:using namespace std;typedef long long ll;const double eps=1e-9;int H[505],P[10005],X[10005],tot;int n,k;inline void add(int x,int y){ P[++tot]=y;X[tot]=H[x];H[x]=tot;}bool cover[505];int link[505];int ans;bool find(int k){ for(int i=H[k];i;i=X[i]){ if(!cover[P[i]]){ int q=link[P[i]]; link[P[i]]=k; cover[P[i]]=1; if(q==-1){ ans++;return true; } if(find(q)) return true; link[P[i]]=q; } } return false;}int main(){ #ifdef LOCAL freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); #endif scanf("%d%d",&n,&k); for(int i=0,x,y;i<k;i++){ scanf("%d%d",&x,&y); add(x,y); } memset(link,-1,sizeof link); for(int i=1;i<=n;i++){ memset(cover,0,sizeof cover); find(i); } printf("%d\n",ans); return 0;}
BZOJ 1741: [Usaco2005 nov]Asteroids 穿越小行星群
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。