HDU4685 Prince and Princess 完美搭配+良好的沟通-白红宇

HDU4685 Prince and Princess 完美搭配+良好的沟通

阅读量：7075 次

发布时间：2019-06-28

本文共 2762 字，大约阅读时间需要 9 分钟。

意甲冠军：今天，有n王子，m公主。现在给他们配对，与王子会嫁给一个男人，他喜欢。公主无法做出选择。

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

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

代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #include
            
             #include
             
              #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 0x3f3f3f3ftypedef 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

你可能感兴趣的文章

快速体验 Sentinel 集群限流功能，只需简单几步