POJ 1274 The Perfect Stall、HDU 2063 过山车(最大流做二分匹配)

The Perfect Stall

Time Limit: 1000MS   Memory Limit: 10000K
Total Submissions: 24081   Accepted: 10695

Description

Farmer John completed his new barn just last week, complete with all the latest milking technology. Unfortunately, due to engineering problems, all the stalls in the new barn are different. For the first week, Farmer John randomly assigned cows to stalls, but it quickly became clear that any given cow was only willing to produce milk in certain stalls. For the last week, Farmer John has been collecting data on which cows are willing to produce milk in which stalls. A stall may be only assigned to one cow, and, of course, a cow may be only assigned to one stall. 
Given the preferences of the cows, compute the maximum number of milk-producing assignments of cows to stalls that is possible.

Input

The input includes several cases. For each case, the first line contains two integers, N (0 <= N <= 200) and M (0 <= M <= 200). N is the number of cows that Farmer John has and M is the number of stalls in the new barn. Each of the following N lines corresponds to a single cow. The first integer (Si) on the line is the number of stalls that the cow is willing to produce milk in (0 <= Si <= M). The subsequent Si integers on that line are the stalls in which that cow is willing to produce milk. The stall numbers will be integers in the range (1..M), and no stall will be listed twice for a given cow.

Output

For each case, output a single line with a single integer, the maximum number of milk-producing stall assignments that can be made.

Sample Input

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

Sample Output

4

题目链接:POJ 1274

今天用做了这两道题才知道用最大流解决二分匹配的正确姿势 :首先不要一开始就往S、T这两个点里加边,因为很可能一个点会多次与S相连,那这样这个点总的流量就不是1了。

假设二分图的左半部分是集合$L_i$、右半部分是集合$R_i$,那么首先从$L_i$到$R_i$连一条边,然后将$L_i$与$R_i$记录到各自的数字里,然后各自去重,再从S到去重后的左集合均连一条容量为1的边,从右集合$R_i$中连向T也是一条容量为1的边,然后再跑最大流,代码是POJ的题目代码,HDU的把左边也去重就好了。

代码:

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <sstream>
#include <cstring>
#include <bitset>
#include <string>
#include <deque>
#include <stack>
#include <cmath>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define INF 0x3f3f3f3f
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
typedef pair<int,int> pii;
typedef long long LL;
const double PI=acos(-1.0);
const int N=210<<1;
const int M=N*N*2;
struct edge
{
    int to,nxt;
    int cap;
};
edge E[M];
int head[N],tot;
int d[N];
vector<int>stall;

void init()
{
    CLR(head,-1);
    tot=0;
    stall.clear();
}
void add(int s,int t,int c)
{
    E[tot].to=t;
    E[tot].cap=c;
    E[tot].nxt=head[s];
    head[s]=tot++;

    E[tot].to=s;
    E[tot].cap=0;
    E[tot].nxt=head[t];
    head[t]=tot++;
}
int bfs(int s,int t)
{
    CLR(d,INF);
    d[s]=0;
    queue<int>Q;
    Q.push(s);
    while (!Q.empty())
    {
        int now=Q.front();
        Q.pop();
        for (int i=head[now]; ~i; i=E[i].nxt)
        {
            int v=E[i].to;
            if(d[v]==INF&&E[i].cap)
            {
                d[v]=d[now]+1;
                if(v==t)
                    return 1;
                Q.push(v);
            }
        }
    }
    return d[t]!=INF;
}
int dfs(int s,int t,int f)
{
    if(s==t||!f)
        return f;
    int ret=0;
    for (int i=head[s]; ~i; i=E[i].nxt)
    {
        int v=E[i].to;
        if(d[v]==d[s]+1&&E[i].cap>0)
        {
            int d=dfs(v,t,min(f,E[i].cap));
            if(d>0)
            {
                E[i].cap-=d;
                E[i^1].cap+=d;
                f-=d;
                ret+=d;
                if(!f)
                    break;
            }
        }
    }
    if(!ret)
        d[s]=-1;
    return ret;
}
int dinic(int s,int t)
{
    int ret=0;
    while (bfs(s,t))
        ret+=dfs(s,t,INF);
    return ret;
}
int main(void)
{
    int n,m,b,k,i;
    while (~scanf("%d%d",&n,&m))
    {
        init();
        int S=0,T=n+m+1;
        for (i=1; i<=n; ++i)
        {
            scanf("%d",&k);
            add(S,i,1);
            while (k--)
            {
                scanf("%d",&b);
                add(i,n+b,1);
                stall.push_back(b);
            }
        }
        sort(stall.begin(),stall.end());
        stall.erase(unique(stall.begin(),stall.end()),stall.end());
        int R=stall.size();
        for (i=0; i<R; ++i)
            add(n+stall[i],T,1);
        printf("%d\n",dinic(S,T));
    }
    return 0;
}
时间: 12-09

POJ 1274 The Perfect Stall、HDU 2063 过山车(最大流做二分匹配)的相关文章

HDU 2063.过山车【二分图、二分匹配初接触】【8月3】

过山车 Problem Description RPG girls今天和大家一起去游乐场玩,终于可以坐上梦寐以求的过山车了.可是,过山车的每一排只有两个座位,而且还有条不成文的规矩,就是每个女生必须找个个男生做partner和她同坐.但是,每个女孩都有各自的想法,举个例子把,Rabbit只愿意和XHD或PQK做partner,Grass只愿意和linle或LL做partner,PrincessSnow愿意和水域浪子或伪酷儿做partner.考虑到经费问题,boss刘决定只让找到partner的人

poj 1274 The Perfect Stall 解题报告

题目链接:http://poj.org/problem?id=1274 题目意思:有 n 头牛,m个stall,每头牛有它钟爱的一些stall,也就是几头牛有可能会钟爱同一个stall,问牛与 stall 最大匹配数是多少. 二分图匹配,匈牙利算法入门题,留个纪念吧. 书上看到的一些比较有用的知识: 增广:通俗地说,设当前二分图中,已有 x 个匹配边(代码中match[i] 不为0的个数有x个),现在对 i 点(也就是代码中dfs中的参数 x) 指定一个匹配点 j, 由于 j 可能有匹配点设为

poj 1274 The Perfect Stall (二分匹配)

The Perfect Stall Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 17768   Accepted: 8104 Description Farmer John completed his new barn just last week, complete with all the latest milking technology. Unfortunately, due to engineering pr

POJ 1274 The Perfect Stall【二分图最大匹配】

题意:二分图最大匹配 分析:二分图最大匹配 代码: 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <vector> 5 using namespace std; 6 7 const int maxn = 205; 8 int n; 9 10 int Link[maxn]; 11 int vis[maxn]; 12 vector<int> G[ma

POJ 1274 The Perfect Stall 水二分匹配

题目链接:点击打开链接 嘿嘿 #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<vector> #include<queue> #include<functional> #define N 2011 using namespace std; int lef[N], pn;//lef[v]表示Y集的点v 当前连接

POJ 1274 The Perfect Stall (网络流-最大流)

The Perfect Stall Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 18308   Accepted: 8328 Description Farmer John completed his new barn just last week, complete with all the latest milking technology. Unfortunately, due to engineering pr

hdu 2063 过山车(二分图匹配最大匹配数模板)

过山车 Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 10776    Accepted Submission(s): 4748 Problem Description RPG girls今天和大家一起去游乐场玩,终于可以坐上梦寐以求的过山车了.可是,过山车的每一排只有两个座位,而且还有条不成文的规矩,就是每个女生必须找个个男生做par

HDU 2063 过山车 二分图题解

一个男女搭配的关系图,看可以凑成多少对,基本和最原始的一个二分图谜题一样了,就是 一个岛上可以凑成多少对夫妻的问题. 所以是典型的二分图问题. 使用匈牙利算法,写成两个函数,就非常清晰了. 本程序还带分配释放程序,当然oj一般不需要.但是好的程序一定要. #include <stdio.h> #include <stdlib.h> int K, M, N, a, b; int *linker; bool **gra, *used; void initGraph() { gra =

hdu 2063 过山车(模板)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2063 过山车 Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 21121    Accepted Submission(s): 9154 Problem Description RPG girls今天和大家一起去游乐场玩,终于可以坐上梦寐以求