POJ-3281Dining 最大流_3281dining 挑程-程序员宅基地

技术标签: 图论  

这题是挑战程序设计竞赛的例题,因为师兄讲了所以就补了

做法:

建图的方法是:加一个源点和汇点,讲饮料或食物分别连向源点、汇点,对于每一头牛,把它和它喜欢的食物和饮料连边,由于每一头牛在考虑的时候都是只能被一个边流入和流出(因为每一头牛都是只能吃一个食物喝一个饮料),所以把牛拆点(假如拆成牛1,牛2),就在牛1和牛2之间连一条边。然后源点到汇点跑一遍dinic就可以了。

代码:
#pragma GCC optimize(2)
//#include <bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#ifdef DEBUG
# pragma GCC optimize(0)
#endif // DEBUG
#define mem(x,y) memset(x,y,sizeof(x))
#define startcoding ios::sync_with_stdio(false);\
        cin.tie(0);
using namespace std;namespace NYAM{
/*************************************************/
    typedef long long ll;
    typedef unsigned long long ull;
    typedef long double ld;
/**************************************************/
const int maxm=3e5+5;
const int inf=0x3f3f3f3f;
const int maxn=505;
int head[maxn];
struct edge
{
    int cap,to,next;
}e[maxm];
int dis[maxn];
int s,t,ecnt;
void ins(int u,int v,int cap)
{
    e[ecnt].to=v;
    e[ecnt].next=head[u];
    e[ecnt].cap=cap;
    head[u]=ecnt++;
    e[ecnt].to=u;
    e[ecnt].next=head[v];
    e[ecnt].cap=0;
    head[v]=ecnt++;
}
int bfs()
{
    mem(dis,-1);
    queue<int>q;
    dis[s]=0;
    q.push(s);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=head[u];i>=0;i=e[i].next)
        {
            int v=e[i].to;
            if(e[i].cap>0&&dis[v]==-1)
            {
                dis[v]=dis[u]+1;
                q.push(v);
            }
        }
    }
    return dis[t]!=-1;
}
int dfs(int u,int f)
{
    int tmp;
    if(u==t) return f;
    for(int i=head[u];i>=0;i=e[i].next)
    {
        int v=e[i].to;
        if(e[i].cap>0&&dis[v]==dis[u]+1)
        {
            tmp=dfs(v,min(f,e[i].cap));
            if(tmp>0)
            {
                e[i].cap-=tmp;
                e[i^1].cap+=tmp;
                return tmp;
            }
        }
    }
    dis[u]=-1;
    return 0;
}
int dinic()
{
    int ans=0;
    while(bfs())
    {
        //cout<<"aha"<<endl;
        int tmp=dfs(s,inf);
        while(tmp>0)
        {
            ans+=tmp;
            tmp=dfs(s,inf);
        }
    }
    return ans;
}
void main()
{
    startcoding
    t=504;
    int n,f,d;
    while(cin>>n>>f>>d)
    {
        mem(head,-1);
        ecnt=0;
        for(int i=1;i<=f;i++) ins(s,i,1);
        //for(int i=1;i<=n;i++) ins(f+i,f+n+i,1);       //对牛拆点 
        for(int i=1;i<=d;i++) ins(f+2*n+i,t,1);
        for(int i=1;i<=n;i++)
        {
            ins(f+i,f+n+i,1);
            int F,D,x;
            cin>>F>>D;
            for(int j=1;j<=F;j++)
            {
                cin>>x;
                ins(x,f+i,1);
            }
            for(int j=1;j<=D;j++)
            {
                cin>>x;
                ins(f+n+i,f+2*n+x,1);
            }
        }
        cout<<dinic()<<endl;
    }
    return;
}
}
int main(){
    #ifndef ONLINE_JUDGE
        freopen("in.txt","r",stdin);
    #endif  //ONLINE_JUDGE
    NYAM::main();
    exit(0);
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/Apel_dey/article/details/80173939

智能推荐

读《研磨设计模式》-代码笔记-工厂方法模式-程序员宅基地

文章浏览阅读75次。[b]声明:本文只为方便我个人查阅和理解,详细的分析以及源代码请移步 原作者的博客[url]http://chjavach.iteye.com/[/url][/b][code="java"]package design.pattern;/* * 工厂方法模式:使一个类的实例化延迟到子类 * 某次,我在工作不知不觉中就用到了工厂方法模式(称为模板方法模式更..._代码 : 磨厂

认证、授权、凭证、保密、传输、验证-程序员宅基地

文章浏览阅读800次,点赞10次,收藏8次。以摘要代替明文如果密码本身比较复杂,那么一次简单的哈希摘要就至少可以保证,即使在传输过程中有信息泄露,也不会被逆推出原信息;即使密码在一个系统中泄露了,也不至于威胁到其他系统的使用。但这种处理不能防止弱密码被彩虹表攻击所破解。

@德人合科技——天锐绿盾 | 图纸加密软件有哪些功能呢?-程序员宅基地

文章浏览阅读647次,点赞7次,收藏6次。天锐绿盾加密软件是一款全面保障企业电脑数据和安全使用的加密软件。

XML语法以及DTD的详解_dtdparser.jar 作用-程序员宅基地

文章浏览阅读1.2w次,点赞8次,收藏29次。XML简介:XML是指可扩展标记语言(eXtensible Markup Language),它是一种标记语言,很类似HTML。它被设计的宗旨是传输数据,而非显示数据。XML标签没有被预定义,需要用户自行定义标签。XML技术是W3C组织(World Wide Web Consortium万维网联盟)发布的,目前遵循的是W3C组织于2000年发布XML1.0规范。XML被广泛认为是继Ja_dtdparser.jar 作用

雨中冒险2逆向修改_雨中冒险2爆率修改-程序员宅基地

文章浏览阅读6.8k次,点赞6次,收藏12次。雨中冒险2(Risk of Rain 2)破解修改,成就解锁教程_雨中冒险2爆率修改

构建多领域异构数据融合的统一数据集_异构数据融合概念-程序员宅基地

文章浏览阅读593次,点赞26次,收藏9次。构建多领域异构数据融合的统一数据集作者:禅与计算机程序设计艺术1. 背景介绍随着大数据时代的到来,各个领域都产生了大量的异构数据。如何有效地整合和利用这些多源、多类型的数据资源,已经成为当前亟需解决的关键问题。构建一个统一的数据集,不仅能够提高数据的利用效率,还能为跨_异构数据融合概念

随便推点

WPF3D图片轮播效果-程序员宅基地

文章浏览阅读650次。原文:WPF3D图片轮播效果 版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/m0_37591671/article/details/68059169 1. 效果图:(1)初始化:(2..._wpf实现图片环形旋转轮动效果

软件测试之缺陷_软件问题严重等级-程序员宅基地

文章浏览阅读1.8k次。软件缺陷, 通常又被叫做bug或者defect, 即为软件或程序中存在的某种破坏正常运行能力的问题、错误,其存在会导致软件产品在某种程度上不能满足用户的需求.软件缺陷是指存在于软件(程序、数据、文档中的)那些不符合用户需求的问题._软件问题严重等级

java中的character_什么是Java Character类?Character类的常用方法详解-程序员宅基地

文章浏览阅读3k次。前面给大家介绍一下Java Number类,那么下面的文章要给大家讲到的就是Java Character类,你对于Java Character类了解多少呢?你知道JavaCharacter类的常用方法都有哪些吗?Character类是字符数据类型char的包装类,Character类的对象包含类型为char的单个字段,这样的话就能够将基本数据类型当对象来处理。下面的话是Character类的常用方..._java character

7-1 3-2计算圆的周长和面积_湖北经济学院李祥圆的周长跟面积-程序员宅基地

文章浏览阅读563次。2021级-JAVA03 基础语法2--控制语句_湖北经济学院李祥圆的周长跟面积

Unity画线(Vectrosity5.6.1插件)_unity vectrosity 插件下载-程序员宅基地

文章浏览阅读4.9k次。Unity画线(Vectrosity5.6.1插件)_unity vectrosity 插件下载

数据杂谈&:CIO和CTO的区别(首席信息官&首席技术官)_cio大还是cto大-程序员宅基地

文章浏览阅读6.4k次。首席信息官(又称CIO,chief information officer的缩写),中文意思大概是“首席信息官”或者“信息主管”,是负责公司信息即使是和系统所有领域的高级官员。产生背景现代企业正常运营,要靠物流,资金和信息流的畅通为基础,与企业信息化进程和企业流程再造密切相关。中国企业纷纷开始设立首席信息官这个职位。在人们的印象中,中国的IT应用市场一贯是金融与电信两大行业唱主角。据统计,2001年中国银行信息化建设投资的总体规模为260亿元,同年电信业行业信息化的整体市场规模为427.8亿元。另一个_cio大还是cto大

推荐文章

热门文章

相关标签