首页 > 代码库 > hdu 2063 过山车

hdu 2063 过山车

2024-07-17 12:08:08   221人阅读

 

不知道是我个人问题还是怎么地 单纯看算法完全看不进去 只有读代码才能看出精华

这题应该是最基础的二分匹配了 不过刚刚看懂还是觉得实在是神奇

 

先给一个女生1找个对应的男生

再到下个女生2 如果这个女生找到的男生已经有对应的女生1

再找女生1的增广路

到最后得到最大匹配

（理解得不是很深刻 表达也做不到很清晰= =）

 

#include<stdio.h>#include<string.h>#include<math.h>#include<iostream>#include<algorithm>#include<queue>#include<stack>#define mem(a,b) memset(a,b,sizeof(a))#define ll __int64#define MAXN 1000#define INF 0x7ffffff#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1using namespace std;int map[510][510];int vis[2000];int link[2000];int k,w,m,ans;int find(int x){    int i;    for(i=1;i<=m;i++)    {        if(!vis[i]&&map[x][i])        {            vis[i]=1;            if(!link[i]||find(link[i]))            {                link[i]=x;                return 1;            }        }    }    return 0;}int main(){    int i,j;    int na,nv;    while(scanf("%d",&k)!=EOF&&k)    {                scanf("%d%d",&w,&m);        ans=0;        mem(map,0);        mem(link,0);        for(i=1;i<=k;i++)        {            scanf("%d%d",&nv,&na);            map[nv][na]=1;        }                for(i=1;i<=w;i++)        {            mem(vis,0);            if(find(i)) ans++;        }        printf("%d\n",ans);    }    return 0;}

　　


联系
我们