http://acm.hdu.edu.cn/showproblem.php?pid=1281
比较猎人打鸟问题，可以将车看做是子弹，每个车都有x,y坐标，可将其看做边，行数和列数看成是两个集合的点，该题就变为求最多的匹配边。关键匹配就是指在保证最大匹配的前提下，不能缺少的匹配。也就是说如果缺少这对匹配，那么所求的匹配数不是最大匹配。
#include <iostream>
using namespace std;
const int M=101;
bool g[M][M];
bool visit[M];
int link[M];
int x[M*M],y[M*M];//记录匹配边，用于计算关键匹配
int m,n,k;
bool find(int i)
{
int j;
for(j=1;j<=m;j++)
{
if(g[i][j] && !visit[j])
{
visit[j]=true;
if(link[j]==0 || find(link[j]))
{
link[j]=i;
return true;
}
}
}
return false;
}
int result()
{
int i,res=0;
memset(link,0,sizeof(link));//注意link数组要在这里做初始化，因为link数组要用多次
for(i=1;i<=n;i++)
{
memset(visit,0,sizeof(visit));
if(find(i))
res++;
}
return res;
}
int main()
{
int t,l,c,count=0;
while(cin>>n>>m>>k)
{
count++;
memset(g,0,sizeof(g));
for(t=0;t<k;t++)
{
cin>>x[t]>>y[t];
g[x[t]][y[t]]=true;
}
l=result();
c=0;
for(t=0;t<k;t++)
{
g[x[t]][y[t]]=false;//将(x[t],y[t])设为不连通，求最大匹配，如果变小，说明该边为关键匹配边
if(result()<l)
c++;
g[x[t]][y[t]]=true; //还原状态
}
printf("Board %d have %d important blanks for %d chessmen.\n",count,c,l);
}
return 0;
}
posted on 2011-09-14 00:24
大大木马 阅读(327)
评论(0) 编辑 收藏 引用