`
暴风雪
  • 浏览: 375015 次
  • 性别: Icon_minigender_2
  • 来自: 杭州
社区版块
存档分类
最新评论

[一般图最大匹配]URAL 1099:Work Scheduling

阅读更多

大致题意:
    给出n个士兵,再给出多组士兵之间两两可以匹配的关系。已知某个士兵最多只能与一个士兵匹配。求最多能够有多少对匹配,并输出这些匹配。

 

大致思路:

    最大匹配问题,对于二分图来说用的是匈牙利算法,求一般图最大匹配用的是带花树开花算法。这里面要注意一点,输出匹配时,要把match[i]和match[match[i]]同时设为-1。

 

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std;
#define MAXE 250*250*2
#define MAXN 250
#define SET(a,b) memset(a,b,sizeof(a))
deque<int> Q;
//g[i][j]存放关系图:i,j是否有边,match[i]存放i所匹配的点
bool g[MAXN][MAXN],inque[MAXN],inblossom[MAXN];
int match[MAXN],pre[MAXN],base[MAXN];

//找公共祖先
int findancestor(int u,int v){
    bool inpath[MAXN]={false};
    while(1){
        u=base[u];
        inpath[u]=true;
        if(match[u]==-1)break;
        u=pre[match[u]];
    }
    while(1){
        v=base[v];
        if(inpath[v])return v;
        v=pre[match[v]];
    }
}

//压缩花
void reset(int u,int anc){
    while(u!=anc){
        int v=match[u];
        inblossom[base[u]]=1;
        inblossom[base[v]]=1;
        v=pre[v];
        if(base[v]!=anc)pre[v]=match[u];
        u=v;
    }
}

void contract(int u,int v,int n){
    int anc=findancestor(u,v);
    //SET(inblossom,0);
    memset(inblossom,0,sizeof(inblossom));
    reset(u,anc);reset(v,anc);
    if(base[u]!=anc)pre[u]=v;
    if(base[v]!=anc)pre[v]=u;
    for(int i=1;i<=n;i++)
        if(inblossom[base[i]]){
            base[i]=anc;
            if(!inque[i]){
                Q.push_back(i);
                inque[i]=1;
            }
        }
}

bool dfs(int S,int n){
    for(int i=0;i<=n;i++)pre[i]=-1,inque[i]=0,base[i]=i;
    Q.clear();Q.push_back(S);inque[S]=1;
    while(!Q.empty()){
        int u=Q.front();Q.pop_front();
        for(int v=1;v<=n;v++){
            if(g[u][v]&&base[v]!=base[u]&&match[u]!=v){
                if(v==S||(match[v]!=-1&&pre[match[v]]!=-1))contract(u,v,n);
                else if(pre[v]==-1){
                    pre[v]=u;
                    if(match[v]!=-1)Q.push_back(match[v]),inque[match[v]]=1;
                    else{
                        u=v;
                        while(u!=-1){
                            v=pre[u];
                            int w=match[v];
                            match[u]=v;
                            match[v]=u;
                            u=w;
                        }
                        return true;
                    }
                }
            }
        }
    }
    return false;
}

int main(){
    int n,m,a,b,ans,i;
    while(scanf("%d",&n)!=EOF){
        ans=0;          //最多有几对匹配
        memset(match,-1,sizeof(match));
        memset(g,0,sizeof(g));
        while(scanf("%d%d",&a,&b)!=EOF&&a!=0){
            g[a][b]=g[b][a]=1;
        }
        for(i=1;i<=n;i++){
            if(match[i]==-1&&dfs(i,n)){
                ans++;
            }
        }
        cout<<ans*2<<endl;
        for(i=1;i<=n;i++){
            if(match[i]!=-1){
                printf("%d %d\n",i,match[i]);
                match[i]=match[match[i]]=-1;
            }
        }
    }
    return 0;
}
 
0
1
分享到:
评论

相关推荐

    acm_ural_1099

    Pascal acm_timus_ural_1099.pas

    Ural URAL 解题思路

    Ural解题思路 Ural解题思路 Ural解题思路 Ural解题思路

    Ural

    Ural

    URAL3D

    URAL3D

    acm_ural_1148

    Pascal acm_timus_ural_1148.pas

    URAL部分测试数据

    URAL(Timus Online Judge)部分测试数据 不全

    Ural 1238 源代码

    Ural 1238 源代码 涉及算法(动态规划、贪心、DFS)

    ural vol I 题解 by yuhch123 pdf

    ural 题解 yuhch123。 关于yuhch123: ioi2008 金牌第一名,这是当初它做ural 第一卷时的题解

    ural题解

    包含了ural题库中Vol_I 到Vol_III的所有题目的解题思路

    ural部分题解

    部分题解 大牛出品 Vol1-3 不是很全,约有200题左右

    URAL-PHA

    URAL-PHA

    Python库 | ural-0.28.0.tar.gz

    资源分类:Python库 所属语言:Python 资源全名:ural-0.28.0.tar.gz 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059

    ACM练习题库

    URAL http://acm.timus.ru 俄罗斯乌拉尔大学在线题库 SGU http://acm.sgu.ru/ 俄罗斯圣萨拉托夫州大学在线题库 ELJ http://acm.mipt.ru/judge/bin/problems.pl?lang=en file:///M|/acm/ACM大量习题题库及建议培养...

    Ural ACM 1000源代码(c++)

    Ural ACM 1000源代码(c++),vc++6.0在XPsp2下编译通过,Timus Online Judge再线测评通过

    hdu pku ural 题目分类

    因为大三了 不弄ACM了 所以这些就删了 删之前希望可以帮到别人

    线段树题目

    大量线段树题目 ...hdu 1754 求区间最大值 hdu 1166 求区间和 hdu 1698 成段更新 poj 3468 成段更新 ural 1019 覆盖加统计最长同一个颜色 zoj 2301 和上一题差不多,但是这个染色染的是点,注意染色为空的状况

    Ural-开源

    基于张量类模板的线性代数C ++库,可用于表示等级0的张量,标量向量,1的向量,2的矩阵,3的等级3的张量等。它还包括BLAS和LAPACK子例程的接口。

    Philip_Dural_UX-UI_Designer:UXUI设计器配置文件

    Philip_Dural_UX-UI_Designer:UXUI设计器配置文件

    skillactive:UNIT-Ural 2021的项目

    旧版本已被删除,将不难重写 什么是SkillActive? 好吧,就像为父母及其子女提供的优质服务一样,我们将为您提供一些很棒的服务

    ural

    乌拉尔

Global site tag (gtag.js) - Google Analytics