竹子听

3月30日 二分图最大匹配模板题

https://uoj.ac/problem/78

#include<cstdio>

#include<cstring>

int girls[501],boys[501],map[501][501],nx,ny,waitings[501];

void clear()

{

memset(girls,0,sizeof(int));

memset(boys,0,sizeof(int));

memset(map,0,sizeof(int));

memset(waitings,0,sizeof(int));

}

int dfs(int x)//其实这一段才是重点，侧重一个”腾“字

{

int temp=0,t;

for(int i=1;i<=ny;i++)

if(map[x][i]==1&&!waitings[i])//waitings表示曾经试过的，就不试了

{

waitings[i]=1;

if(boys[i]&&dfs(boys[i])||!boys[i])

{

girls[x]=i,boys[i]=x;

return 1;

}

}

return 0;

 }

int main()

{

int m,c=0;

scanf("%d%d%d",&nx,&ny,&m);

clear();

int temp1,temp2;

for(int i=1;i<=m;i++)

{

scanf("%d%d",&temp1,&temp2);

map[temp1][temp2]=1;

}

for(int i=1;i<=nx;i++)

{

if(dfs(i)) c++;

memset(waitings,0,sizeof(waitings));

}

printf("%d\n",c);

for(int i=1;i<=nx;i++)

printf("%d ",girls[i]);

} 

//昨晚写的45个点只过了9个，没有改完就睡了，睡前看了一下别人的程序，哇塞好短，大概是我自己想复杂了。这是一个好的开始。