国际大学生程序设计竞赛例题_3.1圣诞节

1.题意:男女配对,完成配对.要求最高的不满意度最小.
分析:一定存在完美匹配.
2,解决:n男,n女
low,high对应不满意度的下限和上限,利用二分法.
条件:匹配数为n.
3,实现代码:

#include <iostream>
using namespace std;

const int MAXN=1001;

int disp[MAXN][MAXN];//保存不满意度
int mage[MAXN];
int mheight[MAXN];
int wage[MAXN];
int wheight[MAXN];
int sy[MAXN];//记录y是否已经成为别人的匹配
int cx[MAXN],cy[MAXN];//记录各自的匹配对象
int g[MAXN][MAXN];//记录是否可以构成匹配

int n;//配对个数

void buildgraph(int dis)
{
    memset(g,0,sizeof(g));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            g[i][j]=(disp[i][j]<=dis? 1:0);
}

int path(int u)//从u出发,找到一个新的匹配
{
    for(int v=1;v<=n;v++)
    {
        if(g[u][v]&&!sy[v])
        {
            sy[v]=1;
            if(!cy[v]||path(cy[v]))//给v原来的匹配寻找匹配
            {
                cx[u]=v;
                cy[v]=u;
                return 1;
            }
        }
    }
    return 0;
}

int maxmatch()
{
    int temp=0;
    memset(cx,0,sizeof(cx));
    memset(cy,0,sizeof(cy));
    for(int i=1;i<=n;i++)
    {
        if(!cx[i])
        {
            memset(sy,0,sizeof(sy));
            temp+=path(i);
        }
    }
    return temp;
}

int main()
{
    freopen("3.1.in","r",stdin);
    int ans;
    while(cin>>n,n)
    {
        ans=0;
        for(int i=1;i<=n;i++)
            cin>>mheight[i]>>mage[i];
        for(int i=1;i<=n;i++)
            cin>>wheight[i]>>wage[i];
        int low=100000000;
        int high=0;
        int p,q;
        //得到不满意度的最大和最小值.
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
            {
                p=mheight[i]-wheight[j];
                q=mage[i]-wage[j];
                disp[i][j]=p*p+q*q;
                if(low>disp[i][j]) low=disp[i][j];
                if(high<disp[i][j]) high=disp[i][j];
            }
        while(low<=high)
        {
            int mid=(low+high)/2;
            buildgraph(mid);
            int ret=maxmatch();
            if(ret==n)
            {
                ans=mid;
                high=mid-1;
            }
            else
                low=mid+1;
        }
        cout<<ans<<endl;
    }
    return 0;
}