Ural 1109 Conference（最小路径覆盖数）

题意：A国家有M个代表，B国有N个代表，其中有K对代表可以进行谈判（一个是A国的，一个是B国的），并且每一个代表至少被包含在其中一对中（也就是说，每个人可以至少找到另外一个人谈判），每一对谈判需要一对电话联系（一对电话联系数目算1），现在使每个人都能进行电话联系的最少联系数目

思路：既然是求最少的联系数目，也就是找最少的对数。可以先找到最大二分匹配（此时的匹配全都不重复，都是一对一的），然后加上剩下未匹配的人得数目即可（因为每个人肯定至少找到另外一个人进行谈判）

n：A国代表人数

m：B国代表人数

最大二分匹配的人数=ans

未匹配的人数=n+m-2*ans

所求结果=最大二分匹配的人数+未匹配的人数=ans+n+m-2*ans=n+m-ans

ps:其实这题就是求的最小路径覆盖数

最小路径覆盖数=顶点数-最大匹配数

#include<iostream>

#include<stdio.h>

#include<string.h>

using namespace std;

#define MAXN 1024

int n,m,k,x,y,pre[MAXN];

//二分图中X集和Y集的节点数各为n、m，边数为k；匹配边集为pre，其中节点i所在的匹配边为(pre[i],i)

bool v[MAXN],a[MAXN][MAXN];

//设二分图相邻矩阵为a，Y集合中节点的访问标志为v，若Y集合中的节点j已访问，则v[j]=true

bool dfs(int i){//判断以X集合中的节点i为起点的增广路径是否存在

    int j;

    for(j=; j<=m; j++){

        if(!v[j]&&a[i][j]){//搜索所有与i相邻的未访问点

            v[j]=;//访问节点j

            if(pre[j]==-||dfs(pre[j])){

                //若j的前驱是未盖点或者存在由j的前驱出发的增广路径，则设定(i,j)为匹配边，返回成功标志

                pre[j]=i;

                return true;

            }

        }

    }

    return false;//返回失败标志

}

int main(){

    int i,ans;

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

    memset(a,,sizeof(a));//二分图的相邻矩阵初始化

    memset(pre,-,sizeof(pre));//匹配边集初始化为空

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

        scanf("%d%d",&x,&y);

        a[x][y]=;

    }

    ans=;//匹配边数初始化为0

    for(i=; i<=n; i++){//枚举X集的每个节点

        memset(v,,sizeof(v));//设Y集合中的所有节点的未访问标志

        if(dfs(i)) ans++;//若节点i被匹配边覆盖，则匹配边数+1

    }

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

    return ;

}

巴特西

Ural 1109 Conference（最小路径覆盖数）

最新文章

热门文章