UVA 11419 SAM I AM（最小点覆盖）

UVA 11419 SAM I AM（最小点覆盖）

题目：​​r*c 的矩阵，有n个方格上有怪物，你可以从边界上发射子弹，子弹会把你发射过去的那一行或者列的全部小怪都清掉。问你最少需要多少发子弹，可以全清掉，然后输出具体方案。来张图片吧：

SampleInput

4 4 3

1 1

1 4

3 2

4 4 2

1 1

2 2

0 0 0

SampleOutput

2 r1 r3

2 r1 r2

最小点覆盖，选出最少的点构成集合S，使得对于图G=(V,E)所有的边都至少有一个端点在集合S里。 本题可以把横纵坐标看做二分图的两边的点，怪物的位置就是联系两点的边信息，这样顺利的转化成最小点覆盖问题，也即最大匹配数。怎样寻找射弹位置？在左侧未覆盖的点拓展匈牙利，树上所有的点都标记，最后结果就是左边（Y轴）未覆盖的点和右边（X轴）覆盖了的点。例如：数据： 4 4 6 4 1 4 2 4 3 1 3 3 3 2 3

void show(){ cout<<"show: "<=1;i--)cout<

恩，就是这样。

代码：

#include#include#includeusing namespace std;const int maxn=2e3+10;const int maxm=1e6+10;int e,r,c,n,head[maxn],edgeto[maxm],next[maxm],linkl[maxn],linkr[maxn];bool S[maxn],T[maxn];void addedge(int u,int v){ edgeto[e]=v; next[e]=head[u]; head[u]=e++;}bool match(int u){ S[u]=1; for(int i=head[u];i!=-1;i=next[i]) if(!T[edgeto[i]]) { T[edgeto[i]]=1; if(!linkl[edgeto[i]]||match(linkl[edgeto[i]])) { linkl[edgeto[i]]=u; linkr[u]=edgeto[i]; return true; } } return false;}int main(){ while(scanf("%d%d%d",&r,&c,&n)&&(r+c+n)) { e=0; memset(head,-1,sizeof(head)); memset(linkl,0,sizeof(linkl)); memset(linkr,0,sizeof(linkr)); for(int i=0;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。