UVA 11419 SAM I AM (最小点覆盖)
二分图匹配的题目，属于二分图的顶点覆盖问题。
题目有点像之前做过的一道星际陨石的题目。
题目大概的意思是说，给你一个地图，图上有些点上有东西。
现在我有几门大炮，可以放在某一行或者某一列，然后这一行这一列的东西就会被打掉。
现在要求开炮的次数最小，然后输出开炮方案。
如果这道题目只叫你输出开炮的次数，那很简单，套一下二分图匹配的模板就可以过了。
但这道题目还要输出开炮方案，即是输出二分图匹配顶点覆盖选了那几个顶点。
首先题目用二分图匹配做，使用匈牙利算法找增广路
当匹配完以后，我们在跑一次匈牙利算法
（行为点集X，列为点集Y，在地图上的点抽象为连接点集X和点集Y的线）
这个时候已经是满匹配的状态，不可能在找到增广路
首先我们先假定只在行放大炮，有些正解应该在列也放大炮
那么我们什么时候在列放大炮呢？这个问题需要我们解决。
这个问题最后转换为最小顶点覆盖问题，即选择最少的点把所有的边覆盖。
上面我们已经选择了部分行放大炮，把与这些点相连的线删去
这时候我们在看以下这边的线情况，如果没有线剩下，那么就达到目的，是正解。
如果还有线剩下，那说明我们应该在列放一些炮。
剩下的点都是在找增广路中没有匹配的点，要么是孤立的点，没有线相连
要么是在增广过程中，匹配给别人。要消除这样的点的线，就需要在对应的点集Y放炮
而如果在Y放炮，与这个Y相连的线可能会重合，这样既有浪费。
所有把从这个点Y出发的X点标记（不会放炮的位置），这样就能最高效的利用。
最后根据这个标记结果，就可以输出正确答案
题目有点像之前做过的一道星际陨石的题目。
题目大概的意思是说，给你一个地图，图上有些点上有东西。
现在我有几门大炮，可以放在某一行或者某一列，然后这一行这一列的东西就会被打掉。
现在要求开炮的次数最小，然后输出开炮方案。
如果这道题目只叫你输出开炮的次数，那很简单，套一下二分图匹配的模板就可以过了。
但这道题目还要输出开炮方案，即是输出二分图匹配顶点覆盖选了那几个顶点。
首先题目用二分图匹配做，使用匈牙利算法找增广路
当匹配完以后，我们在跑一次匈牙利算法
（行为点集X，列为点集Y，在地图上的点抽象为连接点集X和点集Y的线）
这个时候已经是满匹配的状态，不可能在找到增广路
首先我们先假定只在行放大炮，有些正解应该在列也放大炮
那么我们什么时候在列放大炮呢？这个问题需要我们解决。
这个问题最后转换为最小顶点覆盖问题，即选择最少的点把所有的边覆盖。
上面我们已经选择了部分行放大炮，把与这些点相连的线删去
这时候我们在看以下这边的线情况，如果没有线剩下，那么就达到目的，是正解。
如果还有线剩下，那说明我们应该在列放一些炮。
剩下的点都是在找增广路中没有匹配的点，要么是孤立的点，没有线相连
要么是在增广过程中，匹配给别人。要消除这样的点的线，就需要在对应的点集Y放炮
而如果在Y放炮，与这个Y相连的线可能会重合，这样既有浪费。
所有把从这个点Y出发的X点标记（不会放炮的位置），这样就能最高效的利用。
最后根据这个标记结果，就可以输出正确答案
题解写的有点冗余，还是能看懂。模拟两次会理解的更加清楚
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<functional>
#define maxn 1005
using namespace std;
int r,c,k;
int visx[maxn],visy[maxn];
int cx[maxn],cy[maxn];
int maps[maxn][maxn];
int match[maxn];
int dfs(int x)//DFS增广
{
visx[x]=1;
for(int y=1;y<=c;y++)
{
if(maps[x][y]&&!visy[y])
{
visy[y]=1;
if(cy[y]==0||dfs(cy[y]))
{
cx[x]=y;
cy[y]=x;
return 1;
}
}
}
return 0;
}
int MaxMatch()
{
int sum=0;
memset(cx,0,sizeof cx);
memset(cy,0,sizeof cy);
for(int i=1;i<=r;i++)
{
memset(visx,0,sizeof visx);
memset(visy,0,sizeof visy);
sum+=dfs(i);
}
return sum;
}
void init()
{
memset(maps,0,sizeof maps);
memset(visx,0,sizeof visx);
memset(visy,0,sizeof visy);
memset(cx,0,sizeof cx);
memset(cy,0,sizeof cy);
}
int main()
{
int i,a,b;
while(scanf("%d%d%d",&r,&c,&k)!=EOF)
{
init();
if(r==0&&c==0&&k==0)
break;
for(i=1;i<=k;i++)
{
scanf("%d%d",&a,&b);
maps[a][b]=1;
}
int ans=MaxMatch();
printf("%d",ans);
memset(visx,0,sizeof visx);
memset(visy,0,sizeof visy);
for ( i = 1; i <= r; i++)//找最小顶点
if (cx[i]== 0)
dfs(i);
for(i=1;i<=r;i++)
if(!visx[i])
printf(" r%d",i);
for(i=1;i<=c;i++)
if(visy[i])
printf(" c%d",i);
cout<<endl;
}
}
查看3道真题和解析