hdu 3277 二分+拆点最大流

By | 05月05日

Marriage Match III

Time Limit: 10000/4000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1080 Accepted Submission(s): 311

Problem Description

Presumably, you all have known the question of stable marriage match. A girl will choose a boy; it is similar as the ever game of play-house . What a happy time as so many friends play 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. As 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. On the other hand, in order to play more times of marriage match, every girl can accept any K boys. If a girl chooses a boy, the boy must accept her unconditionally whether they had quarreled before or not.

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 an integer T, means the number of test cases.
Each test case starts with three integer n, m, K and f in a line (3<=n<=250, 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.


For each case, output a number in one line. The maximal number of Marriage Match the children can play.

Sample Input

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

Sample Output


题意:与hdu 3081 差不多,只是多了一个每一个女孩可以选择k个不喜欢的男孩的条件。



/* *********************************************** Author :xianxingwuguan Created Time :2014/1/18 0:58:25 File Name :E.cpp ************************************************ */ #pragma comment(linker, "/STACK:102400000,102400000")  #include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <string> #include <math.h> #include <stdlib.h> #include <time.h> using namespace std; #define inf 0x3f3f3f3f const int maxn=100000; int head[10000],tol,dep[10000],n; struct node {        int next,to,from,cap; }edge[300000]; void add(int u,int v,int cap) {        edge[tol].from=u;        edge[tol].to=v;        edge[tol].cap=cap;        edge[tol].next=head[u];        head[u]=tol++;         edge[tol].from=v;        edge[tol].to=u;        edge[tol].cap=0;        edge[tol].next=head[v];        head[v]=tol++; } int bfs(int s,int t) {        int que[maxn],front=0,rear=0;        memset(dep,-1,sizeof(dep));        dep[s]=0;que[rear++]=s;        while(front!=rear)        {               int u=que[front++];front%=maxn;               for(int i=head[u];i!=-1;i=edge[i].next)               {                      int v=edge[i].to;                      if(edge[i].cap>0&&dep[v]==-1)                      {                             dep[v]=dep[u]+1;                             que[rear++]=v;                             rear%=maxn;                             if(v==t)return 1;                      }               }        }        return 0; } int dinic(int s,int t) {        int i,res=0,top;        int Stack[maxn],cur[maxn];        while(bfs(s,t))        {               memcpy(cur,head,sizeof(head));               int u=s;top=0;               while(1)               {                      if(u==t)                      {                             int min=inf,loc;                             for(int i=0;i<top;i++)                             if(min>edge[Stack[i]].cap)                             {                                    min=edge[Stack[i]].cap;                                    loc=i;                             }                             for(int i=0;i<top;i++)                             {                                    edge[Stack[i]].cap-=min;                                    edge[Stack[i]^1].cap+=min;                             }                             res+=min;                             top=loc;                             u=edge[Stack[top]].from;                      }                      for(int i=cur[u];i!=-1;cur[u]=i=edge[i].next)                      if(edge[i].cap&&dep[u]+1==dep[edge[i].to])break;                      if(cur[u]!=-1)                      {                             Stack[top++]=cur[u];                             u=edge[cur[u]].to;                      }                      else                      {                             if(top==0)break;                             dep[u]=-1;                             u=edge[Stack[--top]].from;                      }               }        }        return res; } int fa[10000]; int find(int x) {       if(fa[x]!=x)         fa[x]=find(fa[x]);       return fa[x]; } int vis[330][333],K; bool judge(int mid) {       memset(head,-1,sizeof(head));tol=0;       for(int i=1;i<=n;i++)       {        add(0,i,mid);       add(i,i+n,K);       add(i+2*n,3*n+1,mid);       }       for(int i=1;i<=n;i++)        for(int j=1;j<=n;j++)        {          if(vis[i][j])              add(i,j+2*n,1);          else               add(i+n,j+2*n,1);         }       if(dinic(0,3*n+1)==mid*n)       return 1;       return 0; } int main() {       //freopen("data.in","r",stdin);       //freopen("data.out","w",stdout);       int T,i,j,k,m,f;       scanf("%d",&T);       while(T--)       {       scanf("%d%d%d%d",&n,&m,&K,&f);      memset(head,-1,sizeof(head));tol=0;         memset(vis,0,sizeof(vis));      vector<int> ss[500];      while(m--)      {          scanf("%d%d",&i,&j);            vis[i][j]=1;            ss[i].push_back(j);      }            for(i=1;i<=n;i++)fa[i]=i;       while(f--)      {          scanf("%d%d",&i,&j);            int fx=find(i);         int fy=find(j);         if(fx==fy)continue;         fa[fx]=fy;       }       for(i=1;i<=n;i++)            {          for(j=1;j<=n;j++)            {              if(find(i)!=find(j))continue;               int cnt=ss[i].size();               for(k=0;k<cnt;k++)                  vis[j][ss[i][k]]=1;              cnt=ss[j].size();               for(k=0;k<cnt;k++)                  vis[i][ss[j][k]]=1;           }        }       int left=0,right=n,mid;         while(left<right)        {          mid=(left+right+1)>>1;            if(judge(mid))left=mid;         else right=mid-1;        }       printf("%dn",left);       }       return 0; }

Similar Posts:

  • POJ2391 Ombrophobic Bovines(二分+拆点+最大流)

    链接:http://poj.org/problem?id=2391 题意: 有n个点,m条边(无向边),先输入n个点的信息,前面那个是这个点内已经有的牛,后面的是这个点最多可以容纳几头牛.m条边就是起点,终点,所需时间.问:所有奶牛都在点内安排好,所需的最少时间.如果无解输出-1. 根据题意,我们会想到一个思路,就是二分最大距离,然后跑最大流,这是一个初级思路,我写了这个之后发现是错的,仔细思考以后发现这样一种情况.不同的点间接连接着,我们二分的最大距离是x的话,这些点的距离最大确实都不超过x,

  • HDU 3277 Marriage Match III

    二分答案跑最大流.. //author: CHC //First Edit Time: 2014-08-11 16:00 //Last Edit Time: 2014-08-11 16:49 #include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <set> #include <vector> #include <map

  • HDU 3277 Marriage Match III【并查集+二分+最大流】

    题意: 有 2*n个同学,n男n女,知道了 有 m 对 男女之间木有吵过架,现在这 n 个女生要找对象,要求没有和她吵过架或者没有和她的一个朋友吵过架, 当 n 个女生都找到对象的时候算作一轮,然后重新找,满足每个女生都不能找和上次一样的对象,而且每个女生除了自己没有吵过架的人外,最多 可一和 k 个男生成为朋友,问最多能进行多少轮. 分析: 建图: 将每个女生 i 拆成两个点 i 和 i+n 如果女生 i 可以和 男生 j 没吵过架,就在 i 和 j 之间连一条容量为 1 的边 否则在 i+n

  • hdu 3376 Matrix Again 最大费用流

    Matrix Again Time Limit: 5000/2000 MS (Java/Others)    Memory Limit: 102400/102400 K (Java/Others) Total Submission(s): 3656    Accepted Submission(s): 1077 Problem Description Starvae very like play a number game in the n*n Matrix. A positive intege

  • Tour(hdu 3488,KM+拆点)

    http://acm.hdu.edu.cn/showproblem.php?pid=3488 http://acm.hust.edu.cn/vjudge/contest/view.action?cid=29327#problem/F F - Tour Description In the kingdom of Henryy, there are N (2 <= N <= 200) cities, with M (M <= 30000) one-way roads connecting t

  • HDU 3488 Tour 最小费用最大流||最大匹配

    题意:选一条路线,使得经过n条路,并且有环,回到起点 分析:n条路分别从n个不同的点出发,到达不同的点,用最大匹配可解 把每个点拆成2个,一个进,一个出,连接源点跟所有进入点,容量为1,费用为0,连接所以出点和汇点,容量为1,费用为0 对于每条边(u,v,w),连接u,v+n,容量为1,费用为w: 费用流 #include <iostream> #include<cstdio> #include<string> #include<algorithm> #in

  • HDU 4240 Route Redundancy 一条流最大的路径

    题目来源:HDU 4240 Route Redundancy 题意:求最大流与一条流最大的路径的比值 前者最大流求出 后者是每一条路的最小值再取大 思路:我用的是dinic 可以在DFS的时候在传递一个参数 表示当前增广路可以通过最大的流量 然后当x==t 到达汇点时 在取他们的最大值 #include <cstdio> #include <queue> #include <vector> #include <cstring> #include <al

  • HDU 4292 Food(建图+最大流)

    请不要随便指点别人该怎么做.每个人的人生都应该自己掌握.你给不了别人一切.你也不懂别人的忧伤. 微笑不代表快乐.哭泣不一定悲伤 不努力怎么让关心你的人幸福.不努力怎么让看不起你的人绝望. 我用生命在奋斗--lx_Zz ------------------------------------------------------------- ------------------------- 华丽的分割线 ---------------------------- -----------------

  • POJ 3281【拆点 &amp;&amp; 最大流经典建图】

    Dining Time Limit: 2000MS   Memory Limit: 65536K Total Submissions: 11097   Accepted: 5096 Description Cows are such finicky eaters. Each cow has a preference for certain foods and drinks, and she will consume no others. Farmer John has cooked fabulo

  • bzoj 1927 星际竞速(拆点费用流)

    题目链接 http://www.lydsy.com/JudgeOnline/problem.php?id=1927 好嘛,现在我要正式用某神犇的博客上的题的顺序开始刷题了... 这道题将每个能力爆发模式的费用,即单点费用拆成两个点,再加边.要加入一个源点和汇点.本蒟蒻只会写有点耗时的spfa版,若有那个神犇会zkw费用流,请教一下= =||. #include<cstdio> #include<cstring> #include<iostream> #include&l