首页 > 代码库 > pku 3041 Asteroids（最小点覆盖）
pku 3041 Asteroids（最小点覆盖）
题意：
N*N的矩阵，有K个敌人，坐标分别是(C1,C1),.....,(Rk,Ck)。
有一个武器，每发射一次，可消掉某行或某列上的所有的敌人。
问消灭所有敌人最少需要多少发。
思路：
二分建图：左边N个点代表行号，右边N个点代表列号。如果第i行第j列上有敌人，则将左边点i和右边点j连一条线。
则转化为求此二分图的最小点覆盖，即最大匹配。【这个建图思想太妙了！赞！】
代码：
int n,k;vector<int> graph[505];bool bmask[505];int cx[505],cy[505];int findPath(int u){ int L=graph[u].size(); rep(i,0,L-1){ int v=graph[u][i]; if(!bmask[v]){ bmask[v]=true; if(cy[v]==-1||findPath(cy[v])){ cy[v]=u; cx[u]=v; return 1; } } } return 0;}int MaxMatch(){ int ans=0; rep(i,1,n) cx[i]=cy[i]=-1; rep(i,1,n) if(cx[i]==-1){ mem(bmask,false); ans+=findPath(i); } return ans;}int main(){ while(scanf("%d%d",&n,&k)!=EOF){ rep(i,1,n) graph[i].clear(); while(k--){ int r,c; scanf("%d%d",&r,&c); graph[r].push_back(c); } int dd=MaxMatch(); printf("%d\n",dd); }}
pku 3041 Asteroids（最小点覆盖）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。