解题报告

二分图第一题。

题目描写叙述：

为了參加即将召开的会议，A国派出M位代表，B国派出N位代表，（N，M<=1000）

会议召开前，选出K队代表，每对代表必须一个是A国的，一个是B国的;

要求每个代表要与还有一方的一个代表联系，除了能够直接联系，也能够电话联系，求电话联系最少

思路：

电话联系最少就要使直接联系最大，又是一一匹配关系，就是二分图的最大匹配。

以下是匈牙利算法。

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#define N 1050

#define M 1050

using namespace std;

int mmap[M][N],vis[N],pre[N],n,m,k;

int dfs(int x)

{

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

    {

        if(!vis[i]&&mmap[x][i])

        {

            vis[i]=1;

            if(pre[i]==-1||dfs(pre[i]))

            {

                pre[i]=x;

                return 1;

            }

        }

    }

    return 0;

}

int main()

{

    int i,j,u,v;

    memset(pre,-1,sizeof(pre));

    memset(vis,0,sizeof(vis));

    scanf("%d%d%d",&m,&n,&k);

    for(i=0;i<k;i++)

    {

        scanf("%d%d",&u,&v);

        mmap[u][v]=1;

    }

    int ans=0;

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

    {

        memset(vis,0,sizeof(vis));

        ans+=dfs(i);

    }

    printf("%d\n",n+m-ans);

}

二分最大匹配也能够用最大流做，当试试模板

#include <queue>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#define inf 99999999

#define N 1050

#define M 1050

using namespace std;

int mmap[M+N][N+M],vis[N],l[N+M],n,m,k;

int bfs()

{

    queue<int>Q;

    Q.push(0);

    memset(l,-1,sizeof(l));

    l[0]=0;

    while(!Q.empty())

    {

        int u=Q.front();

        Q.pop();

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

        {

            if(l[i]==-1&&mmap[u][i])

            {

                l[i]=l[u]+1;

                Q.push(i);

            }

        }

    }

    if(l[n+m+1]>0)

    return 1;

    return 0;

}

int dfs(int x,int f)

{

    int a,i;

    if(x==n+m+1)

    return f;

    for(i=0;i<=n+m+1;i++)

    {

        if(mmap[x][i]&&l[i]==l[x]+1&&(a=dfs(i,min(f,mmap[x][i]))))

        {

            mmap[x][i]-=a;

            mmap[i][x]+=a;

            return a;

        }

    }

    return 0;

}

int main()

{

    int i,j,u,v;

    memset(vis,0,sizeof(vis));

    scanf("%d%d%d",&m,&n,&k);

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

    mmap[0][i]=1;

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

    mmap[i][m+n+1]=1;

    for(i=0;i<k;i++)

    {

        scanf("%d%d",&u,&v);

        mmap[u][v+m]=1;

    }

    int ans=0,a;

    while(bfs())

        while(a=dfs(0,inf))

        ans+=a;

    printf("%d\n",n+m-ans);

}

Conference

3 2 4

1 1

2 1

3 1

3 2

3