首页 > ACM题库 > HDU-杭电 > HDU 3081-Marriage Match II-分治-[解题报告]HOJ
2014
03-01

HDU 3081-Marriage Match II-分治-[解题报告]HOJ

Marriage Match II

问题描述 :

Presumably, you all have known the question of stable marriage match. A girl will choose a boy; it is similar as the game of playing house we used to play when we are kids. What a happy time as so many friends playing together. And it is normal that a fight or a quarrel breaks out, but we will still play together after that, because we are kids.
Now, there are 2n kids, n boys numbered from 1 to n, and n girls numbered from 1 to n. you know, ladies first. So, every girl can choose a boy first, with whom she has not quarreled, to make up a family. Besides, the girl X can also choose boy Z to be her boyfriend when her friend, girl Y has not quarreled with him. Furthermore, the friendship is mutual, which means a and c are friends provided that a and b are friends and b and c are friend.
Once every girl finds their boyfriends they will start a new round of this game―marriage match. At the end of each round, every girl will start to find a new boyfriend, who she has not chosen before. So the game goes on and on.
Now, here is the question for you, how many rounds can these 2n kids totally play this game?

输入:

There are several test cases. First is a integer T, means the number of test cases.
Each test case starts with three integer n, m and f in a line (3<=n<=100,0<m<n*n,0<=f<n). n means there are 2*n children, n girls(number from 1 to n) and n boys(number from 1 to n).
Then m lines follow. Each line contains two numbers a and b, means girl a and boy b had never quarreled with each other.
Then f lines follow. Each line contains two numbers c and d, means girl c and girl d are good friends.

输出:

There are several test cases. First is a integer T, means the number of test cases.
Each test case starts with three integer n, m and f in a line (3<=n<=100,0<m<n*n,0<=f<n). n means there are 2*n children, n girls(number from 1 to n) and n boys(number from 1 to n).
Then m lines follow. Each line contains two numbers a and b, means girl a and boy b had never quarreled with each other.
Then f lines follow. Each line contains two numbers c and d, means girl c and girl d are good friends.

样例输入:

1
4 5 2
1 1
2 3
3 2
4 2
4 4
1 4
2 3

样例输出:

2

很久没写过Blog了.

HDU 3081

题意:N个男孩和N个女孩玩过家家游戏,规则是女孩子选男孩子做搭档,女孩子只会选她不讨厌的男孩子和她朋友不讨厌的男孩子(女孩子之间的朋友关系是有传递性的,即:A和B是朋友 B和C是朋友,则有A和C是朋友).每玩一轮游戏,女孩子就要重新选一个搭档,而且不能选以前选过的男孩子,问题是 求最多能玩的轮数.


这题是我在学匈牙利算法时候找的模板题,构图很明了.


2*N个节点代表所有的人,1~N是女孩子,N+1~2N代表男孩子,每个女孩子到她喜欢和她朋友喜欢的男孩子之间有连线.

然后进行二分图的最大匹配.在匹配完成后判断匹配数是否==N,不是的话说明GAME OVER 求得答案,是的话说明游戏能完成,然后进行删边操作,再继续匹配,直到匹配数<N为止.


代码如下:

#include"stdio.h"
#include"iostream"
#include"string.h"
#include"stdlib.h"
#include"queue"
using namespace std;
int t,m,n,f;
int map[101][101],link[101],vy[101],fa[101],rank[101];
void make_()
{
  for(int i=1;i<=n;i++) rank[i]=0,fa[i]=i;
}
int find_(int x)
{
  if(fa[x]!=x) fa[x]=find_(fa[x]);
  return fa[x];
}
void union_(int x,int y)
{
  int fx,fy;
  fx=find_(x);
  fy=find_(y);
  if(fx==fy) return ;
  if(rank[fx]>rank[fy])
  {
    fa[fy]=fx;
  }
  else
  {
    fa[fx]=fy;
    if(rank[fx]==rank[fy]) rank[fy]++;
  }
}
int xiongyali(int i)
{
  int j,k;
  for(j=1;j<=n;j++)
  {
    if(!vy[j] && map[i][j])
    {
      vy[j]=1;
      if(!link[j] || xiongyali(link[j]))
      {
        link[j]=i;
        return 1;
      }
    }
  }
  return 0;
}
void del()
{
  int i;
  for(i=1;i<=n;i++)
    map[link[i]][i]=0;
}
int solve()
{
  int i,j,k,temp,ans=0;
  while(1)
  {
    memset(link,0,sizeof(link));
    temp=0;
    for(i=1;i<=n;i++)
    {
      memset(vy,0,sizeof(vy));
      if(xiongyali(i)) temp++;
    }
    //printf("%d\n",temp);
    if(temp==n)
    {
      ans++;
      del();
    }
    else break;
  }
  return ans;
}
int main()
{
  int i,j,k,l,p;
  scanf("%d",&t);
  while(t--)
  {
    scanf("%d%d%d",&n,&m,&f);
    for(i=1;i<=n;i++)
      for(j=1;j<=n;j++)
        map[i][j]=0;
    for(i=1;i<=m;i++)
    {
      scanf("%d%d",&j,&k);
      map[j][k]=1;
    }
    make_();
    for(i=1;i<=f;i++)
    {
      scanf("%d%d",&j,&k);
      union_(j,k);
    }
    for(i=1;i<=n;i++)
      for(j=1;j<=n;j++)
        if(j==i) continue;
        else
          if(find_(i)==find_(j))
            for(k=1;k<=n;k++)
              if(map[j][k]) map[i][k]=1;
    int ans=solve();
    printf("%d\n",ans);
  }
  return 0;
}


然后是HDU 3277

题意和HDU 3081 差不多,增加了一个条件K,意思是每个女孩子最多能选K个她不喜欢的男孩子作为搭档.

一开始我天真地认为这题和HDU 3081差不多的,也是用匈牙利算法+删边就可以AC了,记过几次WA后,回想起来发现想法是错的.然后就可耻地看了大牛的题解,大牛的解法是最大流+二分+并查集.

构图是,把每个女孩子拆成两个点Gi1,Gi2 ,与Gi1相连的男孩子是女孩子或她朋友喜欢的,Gi2是女孩子和她朋友都不喜欢的,Gi1到Gi2有流量为K的边,男孩女孩之间边的流量为1,最后增加源点和汇点.源点到Gi1的流量为二分时的mid值,而每个男孩子到汇点的流量也是二分时候的mid值.

构图完毕后,我是用SAP算法求出最大流的,求出最大流max_flow,显然 当max_flow==N*mid 时, mid的值合法,此时left=mid+1;当 max_flow!=N*mid 时,mid值不合法,r=mid-1,最后二分得到最大的合法值,即是我们要得出的答案.


一开始提交的时候TLE了,我以为是SAP()写得不好,然后加了个反向BFS来初始化距离标号,再次提交以后竟然以640ms在Statistic排行第一,不少的惊喜啊,哈哈O(∩_∩)O哈哈~


不过后来发现TLE原因貌似是存边的数组开小了,即使不加那个反向BFS也不会TLE 只会慢150ms.

Marriage Match II

代码如下:

#include"stdio.h"
#include"iostream"
#include"string.h"
#include"stdlib.h"
#include"queue"

#define inf 200000000
using namespace std;
queue<int> q;
int t,m,n,f,K,c,N;
int a[300][300],head[900],fa[301],rank[301],d[900],num[900],dis[900],vis[900];
struct pp
{
  int u,v,flow,next;
}map[200000],mat[200000];
int minn(int x,int y){return x<y?x:y;}

void make_(){ for(int i=0;i<=n;i++) rank[i]=0,fa[i]=i; }
int find_(int x)
{
  if(fa[x]!=x) fa[x]=find_(fa[x]);
  return fa[x];
}
void union_(int x,int y)
{
  int fx,fy;
  fx=find_(x);
  fy=find_(y);
  if(fx==fy) return ;
  if(rank[fx]>rank[fy])
  {
    fa[fy]=fx;
  }
  else

  {
    fa[fx]=fy;
    if(rank[fx]==rank[fy]) rank[fy]++;
  }
}

void add(int u,int v,int flow)
{
  mat[c].u=u;
  mat[c].v=v;
  mat[c].flow=flow;
  mat[c].next=head[u];

  head[u]=c++;
  mat[c].u=v;
  mat[c].v=u;
  mat[c].flow=0;
  mat[c].next=head[v];
  head[v]=c++;
}
void bfs()
{

  int i,j,u,v;
  for(i=0;i<N;i++) {dis[i]=inf;vis[i]=0;}
  dis[N]=0;
  vis[N]=1;
  q.push(N);
  while(!q.empty())
  {
    u=q.front();
    q.pop();
    for(i=head[u];i!=-1;i=mat[i].next)
    {
      v=mat[i].v;
      if(!vis[v])
      {
        dis[v]=dis[u]+1;
        vis[v]=1;
        q.push(v);
      }
    }

  }
}
int dfs(int u,int flow)
{
  int pos,temp,f,i,v;
  if(u==N) return flow;
  pos=N;
  temp=flow;
  for(i=head[u];i!=-1;i=map[i].next)
  {
    v=map[i].v;
    if(d[u]==d[v]+1 && map[i].flow)
    {
      f=dfs(v,minn(temp,map[i].flow));
      temp-=f;

      map[i].flow-=f;
      map[i^1].flow+=f;
      if(temp==0 || d[0]>=N) return flow-temp;
    }
    if(map[i].flow && d[v]<pos) pos=d[v];
  }
  if(temp==flow)
  {
    num[d[u]]--;
    if(num[d[u]]==0) d[0]=N;
    else
    {
      d[u]=pos+1;
      num[d[u]]++;
    }
  }
  return flow-temp;

}
int SAP()
{
  int i,ans=0;
  for(i=0;i<=N;i++)
  {
    d[i]=dis[i];
    num[i]=0;
  }
  while(d[0]<N)
  {
    ans+=dfs(0,inf);

  }
  return ans;
}
int main()
{
  int i,j,k,l,p,r,mid,max_flow,ans;
  scanf("%d",&t);
  while(t--)
  {
    scanf("%d%d%d%d",&n,&m,&K,&f);
    N=3*n+1;
    memset(a,0,sizeof(a));
    for(i=1;i<=m;i++)
    {
      scanf("%d%d",&j,&k);

      a[j][k]=1;
    }
    make_();
    for(i=1;i<=f;i++)
    {
      scanf("%d%d",&j,&k);
      union_(j,k);
    }    

    for(i=1;i<=n;i++)
      for(j=1;j<=n;j++)
        if(j!=i && find_(j)==find_(i))
          for(k=1;k<=n;k++)
            if(a[j][k]) a[i][k]=1;
    for(i=0;i<=N;i++) head[i]=-1;
    c=0;
    for(i=1;i<=n;i++)
    {
      add(i,i+n,K);
      for(j=1;j<=n;j++)
        if(a[i][j])
          add(i,j+(n<<1),1);
        else
          add(i+n,j+(n<<1),1);
    }

    p=c;
    for(i=1;i<=n;i++)
    {
      add(0,i,0);
      add(i+(n<<1),N,0);
    }
    bfs();
    l=0;r=n;
    while(l<=r)
    {
      mid=(l+r)>>1;
      for(i=p;i<c;i+=2) mat[i].flow=mid; 
      for(i=0;i<c;i++) map[i]=mat[i];
      max_flow=SAP();
      if(max_flow==mid*n) {l=mid+1;ans=mid;}
        else r=mid-1;
    }
    printf("%d\n",ans);
  }
  return 0;
}

参考:http://blog.csdn.net/pygzx/article/details/8094398


  1. 很高兴你会喜欢这个网站。目前还没有一个开发团队,网站是我一个人在维护,都是用的开源系统,也没有太多需要开发的部分,主要是内容整理。非常感谢你的关注。