ural 1109,NYOJ 239,匈牙利算法邻接表

NYOJ 239：http://acm.nyist.net/JudgeOnline/problem.php?pid=239

ural 1109 :http://acm.timus.ru/problem.aspx?space=1&num=1109

NYOJ 月老的难题，是裸的最大匹配，很烦的是邻接阵超时。改用邻接表。

#include <bits/stdc++.h>

using namespace std;

#define maxn 1005

vector <int> G[maxn];

bool use[maxn];

int match[maxn];

int m,n,k;

bool dfs(int u)

{

    for(int i=;i<G[u].size();i++)

    {

        if(use[G[u][i]]==false)

        {

            use[G[u][i]] = true;

            if(match[G[u][i]]==-||dfs(match[G[u][i]]))

            {

                match[G[u][i]] = u;

                return true;

            }

        }

    }

    return false;

}

int main()

{

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

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

    {

        int u,v;

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

        G[u].push_back(v);

    }

    memset(match,-,sizeof(match));

    int ans = ;

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

    {

        memset(use,,sizeof(use));

        if(dfs(i))

            ans ++;

    }

    printf("%d\n",ans);

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

    return ;

}

然后是ural,最小路径覆盖。

题意：

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

就是求最少对数。每个点都要有边相连，这样的边最少是多少——最小路径覆盖。

首先求一下最大匹配(都是一对一)，可能还有没有匹配的人，加上这些人，如案例：最大匹配2，还有左边2号没有匹配。加上这个人。

得公式：

最小路径覆盖 = n+ m - 2 * ans + ans;

#include <bits/stdc++.h>

using namespace std;

#define maxn 1005

vector <int> G[maxn];

bool use[maxn];

int match[maxn];

int m,n,k;

bool dfs(int u)

{

    for(int i=;i<G[u].size();i++)

    {

        if(use[G[u][i]]==false)

        {

            use[G[u][i]] = true;

            if(match[G[u][i]]==-||dfs(match[G[u][i]]))

            {

                match[G[u][i]] = u;

                return true;

            }

        }

    }

    return false;

}

int main()

{

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

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

    {

        int u,v;

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

        G[u].push_back(v);

    }

    memset(match,-,sizeof(match));

    int ans = ;

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

    {

        memset(use,,sizeof(use));

        if(dfs(i))

            ans ++;

    }

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

    return ;

}

巴特西

ural 1109,NYOJ 239,匈牙利算法邻接表

最新文章

热门文章