飞行员配对方案问题（二分图最大匹配）

时间：2022-01-21 01:40:01

     本题一个英国飞行员可以和特定的一个外国飞行员搭配，又要求求最佳的选人方式使选到的人最多，所以一看就是二分图的最大匹配，可以用匈牙利算法搞定。当然也可以建立网络流模型，首先建立源点S和汇点T，源点向所有英国飞行员连流量为1的边，再把所有英国飞行员和能与之搭配的外国飞行员间连一条流量为1的边，最后把所有外国飞行员向汇点T连一条流量为1的边，此时该模型的最大流等于二分图的最大匹配数。又因为要输出一种方案，如果用匈牙利算法就开一个flag数组进行标记，记录二分图左边能匹配右边的哪一个，最后for一遍输出。如果是网络流算法，就for一遍英国飞行员个数，如果它到右边有外国飞行员相连，并且能流的流量为0，说明是满流，说明是一种方案，最后输出就行啦。

匈牙利算法：

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <set>

#define M 211

using namespace std;

int n,m;
int dis[M][M],fy[M],mat[M];
int flag[M];

void init()
{
    scanf("%d%d",&n,&m);
    memset(dis,0,sizeof(dis));
    memset(mat,-1,sizeof(mat));
    memset(flag,-1,sizeof(flag));
    int x,y;
    while(scanf("%d%d",&x,&y)!=EOF&&x!=-1&&y!=-1)
        dis[x][y]=1;
}

bool crosspath(int u)
{
    for(int i=m+1;i<=n;i++)
    {
        if(dis[u][i]==1&&fy[i]==0)
        {
            fy[i]=1;
            if(mat[i]==-1||crosspath(mat[i]))
            {
                flag[u]=i;
                mat[i]=u;
                return true;
            }
        }
    }
    return false;
}

int hungary()
{
    int ans=0;
    for(int i=1;i<=m;i++)
    {
        if(flag[i]==-1)
        {
            memset(fy,0,sizeof(fy));
            ans+=crosspath(i);
        }
    }
    return ans;
}

int main()
{
    freopen("flyer.in","r",stdin);
    freopen("flyer.out","w",stdout);
    init();
    int sum=hungary();
    if(sum==0)
        printf("No Solution!\n");
    else
    {
        printf("%d\n",sum);
        /*for(int i=1;i<=m;i++)
        {
            if(flag[i]!=-1)
                printf("%d %d\n",i,flag[i]);
        }*/
        //输出匹配方案
    }

    return 0;
}



网络流模型：

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <set>

#define M 211*211
#define INF 0x7fffffff

using namespace std;

int n,m;
int num=0;
int p[M];
int q[4*M];
int level[M];

struct node
{
    int a;
    int b;
    int w;
    int next;
}str1[M];

void add(int x,int y,int z)
{
    str1[num].a=x;
    str1[num].b=y;
    str1[num].w=z;
    str1[num].next=p[x];
    p[x]=num++;
}

void init()
{
    scanf("%d%d",&m,&n);
    memset(p,-1,sizeof(p));
    int x,y;
    while(scanf("%d%d",&x,&y)!=EOF&&x!=-1&&y!=-1)
    {
        add(x,y,1);
        add(y,x,0);
    }
}

bool makelevel(int st,int ed)
{
    memset(level,0,sizeof(level));
    level[st]=1;
    int l=0,r=0;
    q[r++]=st;
    while(l<r)
    {
        int k=q[l++];
        if(k==ed)
            return true;
        for(int i=p[k];i!=-1;i=str1[i].next)
        {
            int v=str1[i].b;
            if(!level[v]&&str1[i].w)
            {
                level[v]=level[k]+1;
                q[r++]=v;
            }
        }
    }
    return false;
}

int dfs(int now,int maxf,int ed)
{
    if(now==ed)
        return maxf;
    int ret=0,sf;
    for(int i=p[now];i!=-1;i=str1[i].next)
    {
        int v=str1[i].b;
        if(str1[i].w&&level[v]==level[now]+1)
        {
            int minx=min(maxf-ret,str1[i].w);
            sf=dfs(v,minx,ed);
            str1[i].w-=sf;
            str1[i^1].w+=sf;
            ret+=sf;
            if(ret==maxf)
                return ret;
        }
    }
    return ret;
}

int dinic(int st,int ed)
{
    int ans=0;
    while(makelevel(st,ed))
        ans+=dfs(st,INF,ed);
    return ans;
}

int main()
{
    //freopen("flyer.in","r",stdin);
    //freopen("flyer.out","w",stdout);
    init();
    for(int i=1;i<=m;i++)
    {
        add(200,i,1);
        add(i,200,0);
    }
    for(int i=m+1;i<=n;i++)
    {
        add(i,300,1);
        add(300,i,0);
    }
    printf("%d\n",dinic(200,300));
    for(int i=1;i<=m;i++)
    {
        for(int j=p[i];j!=-1;j=str1[j].next)
        {
            if(str1[j].w==0&&str1[j].b!=0&&j%2==0)
                printf("%d %d\n",i,str1[j].b);
        }

    }
    return 0;
}


标签：

相关文章