二分图的必须边——pku1486

2021年09月15日 阅读数:1
这篇文章主要向大家介绍二分图的必须边——pku1486,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。
题意是判断二分图的边是否惟一
先最大二分匹配下
枚举 A集合的点所链接的边 删除
在最大二分匹配下看匹配数是否与没删前同样,若不同,则说明该边是惟一边
二分图的必须边——pku1486_最大匹配数 二分图的必须边——pku1486_i++_02 View Code
#include<stdio.h>
#include
<string.h>

bool map[59][59];
int mark[59];
int rmark[59];
bool flag[59];
int m,g;

struct data
{
int minx,miny,maxx,maxy;
}node[
59];

struct data1
{
int x,y;
}point[
59];

struct data2
{
char str;
int no;
}temp[
59];

bool dfs(int x)
{
int i;
for(i=1;i<=m;i++)
{
if(map[x][i]==0||flag[i]) continue;

flag[i]
=1;
if(mark[i]==0||dfs(mark[i]))
{
mark[i]
=x;
return 1;
}
}
return 0;
}

int main()
{
int i,k,j;
int count;
int add=0;
while(scanf("%d",&k),k)
{
add
++;
g
=m=k;
memset(map,
0,sizeof(map));
memset(mark,
0,sizeof(mark));
count
=0;

for(i=1;i<=k;i++)
{
scanf(
"%d%d%d%d",&node[i].minx,&node[i].maxx,&node[i].miny,&node[i].maxy);
}
for(i=1;i<=k;i++)
{
scanf(
"%d%d",&point[i].x,&point[i].y);
}

for(i=1;i<=k;i++)
{
for(j=1;j<=k;j++)
{
if(point[j].x>=node[i].minx&&point[j].x<=node[i].maxx)
if(point[j].y>=node[i].miny&&point[j].y<=node[i].maxy)
{
map[i][j]
=1;
}

}
}

for(i=1;i<=g;i++)
{
memset(flag,
0,sizeof(flag));
if(dfs(i)==1) count++;
}
for(i=1;i<=k;i++)//记录mark
{
rmark[i]
=mark[i];
}

int rj;
bool addT=0;
printf(
"Heap %d\n",add);
for(i=1;i<=k;i++)//删除链接的边,看是否最大匹配数是否还为n
{
count
=0;
for(j=1;j<=m;j++)
{
if(rmark[j]==i)
{
rj
=j;
map[i][j]
=0;
break;
}
}


memset(mark,
0,sizeof(mark));
for(j=1;j<=g;j++)
{

memset(flag,
false,sizeof(flag));
if(dfs(j)==1) count++;
}
if(count<k)
{

for(j=1;j<=k;j++)
{
if(rmark[j]==i)
break;
}
if(addT==0)
printf(
"(%c,%d)",'A'-1+i,j);
else
printf(
" (%c,%d)",'A'-1+i,j);
addT
=1;
}

map[i][rj]
=1;
}
if(addT==0)
{
printf(
"none");
}
printf(
"\n\n");
}
}