大致题意:
给出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;
}
分享到:
相关推荐
Pascal acm_timus_ural_1099.pas
Ural解题思路 Ural解题思路 Ural解题思路 Ural解题思路
Ural
URAL3D
Pascal acm_timus_ural_1148.pas
URAL(Timus Online Judge)部分测试数据 不全
Ural 1238 源代码 涉及算法(动态规划、贪心、DFS)
ural 题解 yuhch123。 关于yuhch123: ioi2008 金牌第一名,这是当初它做ural 第一卷时的题解
包含了ural题库中Vol_I 到Vol_III的所有题目的解题思路
部分题解 大牛出品 Vol1-3 不是很全,约有200题左右
URAL-PHA
资源分类:Python库 所属语言:Python 资源全名:ural-0.28.0.tar.gz 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059
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++),vc++6.0在XPsp2下编译通过,Timus Online Judge再线测评通过
因为大三了 不弄ACM了 所以这些就删了 删之前希望可以帮到别人
大量线段树题目 ...hdu 1754 求区间最大值 hdu 1166 求区间和 hdu 1698 成段更新 poj 3468 成段更新 ural 1019 覆盖加统计最长同一个颜色 zoj 2301 和上一题差不多,但是这个染色染的是点,注意染色为空的状况
基于张量类模板的线性代数C ++库,可用于表示等级0的张量,标量向量,1的向量,2的矩阵,3的等级3的张量等。它还包括BLAS和LAPACK子例程的接口。
Philip_Dural_UX-UI_Designer:UXUI设计器配置文件
旧版本已被删除,将不难重写 什么是SkillActive? 好吧,就像为父母及其子女提供的优质服务一样,我们将为您提供一些很棒的服务
乌拉尔