POJ-3281Dining 最大流_Apel_dey的博客-程序员宅基地

技术标签: 图论  

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

做法:

建图的方法是:加一个源点和汇点,讲饮料或食物分别连向源点、汇点,对于每一头牛,把它和它喜欢的食物和饮料连边,由于每一头牛在考虑的时候都是只能被一个边流入和流出(因为每一头牛都是只能吃一个食物喝一个饮料),所以把牛拆点(假如拆成牛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

智能推荐

CSS—将文字和图片重叠,元素重叠效果-程序员宅基地

将文字或者其他元素和图片重叠1.上层为块级元素,效果图:设置上边元素的定位为position:relative再根据相对图片的位置调整right、left、top和bottom值2.当上层元素是文字时,效果图:可设置文本框的区域大小,然后将图片设置为背景width: 100%;height: 350px;backgrou..._css给文字图片叠加效果的代码

informix设置数据库默认插入时间_informix 数据库 时间、日期简单操作-程序员宅基地

today当前日期 (date)sysdate 、current 当前时间(datetime)select sysdate from test_table;-- 系统当前时间select current from test_table;-- 系统当前时间select TODAY-1 from test_table;-- 系统前一天日期select sysdate - 1 UNITS year f..._informix建表时间类型默认当前

虹科解决方案 | 如何快速解决CAN与CAN FD之间通信的问题_canfd 分包刷写_虹科电子科技的博客-程序员宅基地

1.CAN FD的发展及优势随着总线技术在汽车电子领域越来越广泛和深入的应用,特别是自动驾驶技术的迅速发展,汽车电子对总线宽度和数据传输速率的要求也越来也高,传统CAN(1MBit/s,8Bytes Payload)已难以满足日益增加的需求。因此在2012年,Bosch发布了新的CAN FD标准 (CAN with Flexible Data Rate) ,CAN FD继承了CAN的绝大多数特性,如同样的物理层,双线串行通信协议,基于非破坏性仲裁技术,分布式实时控制,可靠的错误处理和检测机制等;.._canfd 分包刷写

Failed to compile with 1 error Failed to resolve loader: sass-loader You may need to install it._failed to compile with 1 error 下午2:31:35 failed to_用户昵称已存在__的博客-程序员宅基地

启动项目报错 ERROR Failed to compile with 1 errorFailed to resolve loader: sass-loaderYou may need to install it.已经安装好了ruby,也通过ruby安装好了sass,结果在项目中使用后,启动项目还是报错;后来看到大神文章在此记录一下;解决方法通过npm 安装1、安装sass-loadernpm install sass-loader --save-dev2、安装 node-sass_failed to compile with 1 error 下午2:31:35 failed to resolve loader: sass-lo

springboot整合mybatis,swagger ui_DG_DH168的博客-程序员宅基地

项目整体结构pom.xml文件<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven...

1077篇!ICCV2019接收结果公布,你中了吗?(附7篇论文链接,含Oral)_极市平台的博客-程序员宅基地

原文链接:1077篇!ICCV2019接收结果公布,你中了吗?(附7篇论文链接,含Oral)点击加入**极市CV技术交流群**,交流更多人计算机视觉相关的技术干货ICCV2019接收论文id查看链接:https://docs.google.com/document/d/1ip33oABDWYT9ic7j6NSjcmj67P0BwSMKUJhQpiMjW2E/edit刚刚,计算机视觉三大...

随便推点

You aren‘t using a compiler supported by lombok, so lombok will not work and has been disabled._you aren't using a compiler supported by lombok_梦回沉沦的博客-程序员宅基地

问题在使用IntelliJ IDEA 2020.3 EAP (Ultimate Edition)时提示Lombok不生效java: You aren’t using a compiler supported by lombok, so lombok will not work and has been disabled.解决办法经查以下已经有人在github提出了这个问题,也同时提供了两种方法https://github.com/rzwitserloot/lombok/issues/2592#_you aren't using a compiler supported by lombok

C++学习笔记IO库 1 IO条件状态以及缓冲机制(iostream——输入输出流,fstream——文件流,sstream——string流)_门三o的博客-程序员宅基地

IO类 头文件iostream, 是关联到用户的控制台窗口的。我们常用的cin,cout,cerr,>>运算符,<<运算符,getline()函数等。 除了iostream,还有文件流,和string流 头文件fstream (file stream,文件流):它是对文件的操作 头文件sstram (string stream ,string流):它是对string进行读写等操作。IO类的条件状态 ...

Quadric-error-metric网格简化_quadratic error decimation_senjay的博客-程序员宅基地

1.推导  (以下向量均为列向量)  设平面pip_ipi​的法向量为nin_ini​,xix_ixi​为该平面上任一点,则其在齐次坐标下的方程为:nˉi=(ni,−ni⋅xi)\bar n_i=(n_i,-n_i \cdot x_i)nˉi​=(ni​,−ni​⋅xi​)设空间中任意一点xxx的齐次坐标为xˉ=(x,1)\bar x=(x, 1)xˉ=(x,1)由几何关系可知xxx到pip_ipi​的距离的平方d(x,pi)d(x,p_i)d(x,pi​)为:d(x,pi)=((x−xi_quadratic error decimation

LTE:上行定时提前(一)_提前偏移_yiyeguzhou100的博客-程序员宅基地

http://blog.sina.com.cn/s/blog_927cff010101cwju.html_提前偏移

strstr报段错误问题记录_c语言 strstr 死机_流水石板路的博客-程序员宅基地

使用下面语句,运行程序报段错误:begin = strstr(aucBuf, ':');看了代码好久没发现问题,直到祭出dbg单步调试才找到问题所在行。看了好久才发现,strstr中的第二个入参为字符串,不是字符,改成下面的就可以了:begin = strstr(aucBuf, ":");..._c语言 strstr 死机

Java - Spring与SpringBoot的属性文件配置_温柔流浪的博客-程序员宅基地

Spring的属性文件配置Spring 1.0 分析举例:Spring 1.0 时代 : 纯 .xml 等属性文件配置dao 层 .xml文件配置<?xml version="1.0" encoding="UTF-8"?><beans xmlns="http://www.springframework.org/schema/beans" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"