hdu1507

题解:

二分图最大匹配

建边和第一题差不多

每两个相邻的建边

然后输出方案

代码:

#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdio>
using namespace std;
const int N=;
int vis[N],a[N][N],ans[N],map[N][N],g[N];
int k,n,m,sum,num;
struct node{int x,y;}p[N*N];
int dfs(int x)
{
for (int i=;i<num;i++)
if (!vis[i]&&a[x][i])
{
vis[i]=;
if (ans[i]==-||dfs(ans[i]))
{
ans[i]=x;
return ;
}
}
return ;
}
void match()
{
sum=;
memset(ans,-,sizeof(ans));
for(int i=;i<num;i++)
{
memset(vis,,sizeof(vis));
if(dfs(i)) sum++;
}
}
int main()
{
while (scanf("%d%d",&n,&m))
{
if (!n&&!m) break;
int u,v;
memset(a,,sizeof(a));
memset(map,,sizeof(map));
scanf("%d",&k);
while (k--)
{
scanf("%d%d",&u,&v);
map[u][v]=;
}
num=;
for (int i=;i<=n;i++)
for (int j=;j<=m;j++)
if (map[i][j]==)
{
p[num].x=i;
p[num++].y=j;
}
for (int l=;l<num;l++)
for (int j=l+;j<num;j++)
if ((abs(p[l].x-p[j].x)==&&p[l].y==p[j].y)
||(abs(p[l].y-p[j].y)==&&p[l].x==p[j].x))
if ((p[l].x+p[l].y)%==)a[j][l]=;else a[l][j]=;
match();
printf("%d\n",sum);
for (int i=;i<num;i++)
if (ans[i]!=-)
printf("(%d,%d)--(%d,%d)\n",p[i].x,p[i].y,p[ans[i]].x,p[ans[i]].y);
printf("\n");
}
return ;
}
上一篇:【定制Android系统】Android O 在ROM中添加自己的 so 库(1)——Android.mk 与 Android.bp 的区别【转】


下一篇:Struts2框架(4)---Action类访问servlet