MyException - 我的异常网
当前位置:我的异常网» 编程 » HDU4685 Prince and Princess 完善匹配+强连通

HDU4685 Prince and Princess 完善匹配+强连通

www.MyException.Cn  网友分享于:2014-12-19  浏览:0次
HDU4685 Prince and Princess 完美匹配+强连通

题意:现在有n个王子,m个公主。现在要给他们配对,王子会和他喜欢的一个人结婚,而公主不能做选择。

这题啃得好费劲,有个类似的题目poj1904,那个题目也是给王子与公主配对,但那个是王子公主各n个,且给定了一个完美匹配,然后求每个王子可以做出的选择且不影响最大匹配数目。那题是先建各条喜欢关系的边,然后在由被选择的公主连一条边到与之配对的王子,强连通之后如果一个王子和一个公主在一个强连通分量中,那么他们结合的话,他们的另一半也各自能在强连通中找到另外的匹配,就是符合题意的结果了。

这个题目算是升级版把,我们需要做的先是用匈牙利算法求出最大匹配res,然后建立m-res个虚拟王子与m-res单身公主准备匹配,建立n-res个虚拟公主与n-res个单身王子准备匹配,过程就是虚拟王子要喜欢每一个公主,同样虚拟公主也要被每一个王子喜欢,这样最大匹配一定是n+m-res.求出一个这样的完美匹配,然后再套用poj1904的思路用强连通做。建议先做下1904呦。

代码:

#include<iostream>
#include<cstdio>
#include<string>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rev(i,a,b) for(int i=(a);i>=(b);i--)
#define clr(a,x) memset(a,x,sizeof a)
#define inf 0x3f3f3f3f
typedef long long LL;
using namespace std;

const int eps=0.00000001;
const int maxn=2005;
const int maxm=maxn*maxn/2;

int first[maxn],link[maxn];
int nex[maxm],w[maxm],v[maxm],u[maxm];
bool done[maxn],g[maxn][maxn];
int n,m,ecnt;

void add_(int a,int b,int c=0)
{
    u[ecnt]=a;
    v[ecnt]=b;
    w[ecnt]=c;
    nex[ecnt]=first[a];
    first[a]=ecnt++;
}
bool dfs(int s)
{
    for(int e=first[s];~e;e=nex[e])
    if(!done[v[e]])
    {
        done[v[e]]=true;
        if(link[v[e]]==-1||dfs(link[v[e]]))
        {
            link[v[e]]=s;
            return true;
        }
    }
    return 0;
}

int hungary(int n)
{
    int ans=0;
    clr(link,-1);
    for(int i=1;i<=n;i++)
    {
        clr(done,false);
        if(dfs(i))ans++;
    }
    return ans;
}
int low[maxn],dfn[maxn],stck[maxn],belong[maxn];
int index,top,scc;
bool ins[maxn];
int num[maxn];
int in[maxn],out[maxn];

void tarjan(int u)
{
    low[u]=dfn[u]=++index;
    stck[top++]=u;
    ins[u]=1;
    for(int e=first[u];~e;e=nex[e])
    {
        if(!dfn[v[e]])
        {
            tarjan(v[e]);
            low[u]=min(low[u],low[v[e]]);
        }
        else if(ins[v[e]])low[u]=min(low[u],dfn[v[e]]);
    }
    if(low[u]==dfn[u])
    {
        int v;
        scc++;
        do
        {
            v=stck[--top];
            ins[v]=false;
            belong[v]=scc;
            num[scc]++;
        }while(v!=u);
    }
}
void solve(int n)
{
    clr(dfn,0);
    clr(ins,0);
    clr(num,0);
    index=scc=top=0;
    for(int i=1;i<=n;i++)
        if(!dfn[i])tarjan(i);
}

int main()
{
    int t,a,b,c,k,cas=1,key=1000;
    scanf("%d",&t);
    while(t--)
    {
        clr(first,-1);ecnt=0;
        clr(g,false);
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&k);
            while(k--)
            {
                scanf("%d",&a);
                if(!g[i][a])
                {
                    g[i][a]=1;
                    add_(i,a+key);
                }
            }
        }
        int res=hungary(n);
        int nn=n+m-res;
        for(int i=n+1;i<=nn;i++)
            for(int j=1;j<=nn;j++)
            add_(i,j+key),g[i][j]=1;
        for(int i=1;i<=n;i++)
            for(int j=m+1;j<=nn;j++)
            add_(i,j+key),g[i][j]=1;
        hungary(nn);

        ecnt=0;clr(first,-1);
        for(int i=1;i<=nn;i++)
            if(link[i+key]!=-1)add_(i+nn,link[i+key]);

        for(int i=1;i<=nn;i++)
            for(int j=1;j<=nn;j++)
            if(g[i][j])add_(i,j+nn);
        solve(2*nn);
        printf("Case #%d:\n",cas++);
        int ans[1000];
        for(int i=1;i<=n;i++)
        {
            int en=0;
            for(int j=1;j<=m;j++)
                if(g[i][j]&&belong[j+nn]==belong[i])ans[en++]=j;
            printf("%d",en);
            for(int i=0;i<en;i++)
                printf(" %d",ans[i]);
            puts("");
        }
    }
    return 0;
}


文章评论

10个帮程序员减压放松的网站
10个帮程序员减压放松的网站
程序员都该阅读的书
程序员都该阅读的书
Web开发人员为什么越来越懒了?
Web开发人员为什么越来越懒了?
鲜为人知的编程真相
鲜为人知的编程真相
老程序员的下场
老程序员的下场
初级 vs 高级开发者 哪个性价比更高?
初级 vs 高级开发者 哪个性价比更高?
要嫁就嫁程序猿—钱多话少死的早
要嫁就嫁程序猿—钱多话少死的早
5款最佳正则表达式编辑调试器
5款最佳正则表达式编辑调试器
Java 与 .NET 的平台发展之争
Java 与 .NET 的平台发展之争
60个开发者不容错过的免费资源库
60个开发者不容错过的免费资源库
2013年美国开发者薪资调查报告
2013年美国开发者薪资调查报告
 程序员的样子
程序员的样子
Java程序员必看电影
Java程序员必看电影
什么才是优秀的用户界面设计
什么才是优秀的用户界面设计
总结2014中国互联网十大段子
总结2014中国互联网十大段子
那些性感的让人尖叫的程序员
那些性感的让人尖叫的程序员
聊聊HTTPS和SSL/TLS协议
聊聊HTTPS和SSL/TLS协议
我是如何打败拖延症的
我是如何打败拖延症的
“肮脏的”IT工作排行榜
“肮脏的”IT工作排行榜
如何成为一名黑客
如何成为一名黑客
程序员的鄙视链
程序员的鄙视链
Google伦敦新总部 犹如星级庄园
Google伦敦新总部 犹如星级庄园
编程语言是女人
编程语言是女人
程序员眼里IE浏览器是什么样的
程序员眼里IE浏览器是什么样的
十大编程算法助程序员走上高手之路
十大编程算法助程序员走上高手之路
2013年中国软件开发者薪资调查报告
2013年中国软件开发者薪资调查报告
Web开发者需具备的8个好习惯
Web开发者需具备的8个好习惯
程序员的一天:一寸光阴一寸金
程序员的一天:一寸光阴一寸金
每天工作4小时的程序员
每天工作4小时的程序员
我跳槽是因为他们的显示器更大
我跳槽是因为他们的显示器更大
代码女神横空出世
代码女神横空出世
中美印日四国程序员比较
中美印日四国程序员比较
如何区分一个程序员是“老手“还是“新手“?
如何区分一个程序员是“老手“还是“新手“?
为啥Android手机总会越用越慢?
为啥Android手机总会越用越慢?
程序员周末都喜欢做什么?
程序员周末都喜欢做什么?
写给自己也写给你 自己到底该何去何从
写给自己也写给你 自己到底该何去何从
当下全球最炙手可热的八位少年创业者
当下全球最炙手可热的八位少年创业者
那些争议最大的编程观点
那些争议最大的编程观点
做程序猿的老婆应该注意的一些事情
做程序猿的老婆应该注意的一些事情
漫画:程序员的工作
漫画:程序员的工作
程序员必看的十大电影
程序员必看的十大电影
程序员和编码员之间的区别
程序员和编码员之间的区别
老美怎么看待阿里赴美上市
老美怎么看待阿里赴美上市
程序员最害怕的5件事 你中招了吗?
程序员最害怕的5件事 你中招了吗?
10个调试和排错的小建议
10个调试和排错的小建议
旅行,写作,编程
旅行,写作,编程
为什么程序员都是夜猫子
为什么程序员都是夜猫子
不懂技术不要对懂技术的人说这很容易实现
不懂技术不要对懂技术的人说这很容易实现
亲爱的项目经理,我恨你
亲爱的项目经理,我恨你
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有