小猪分配 , 最大流

Mirko works on a pig farm that consists of M locked pig-houses and Mirko can‘t unlock any pighouse because he doesn‘t have the keys. Customers come to the farm one after another. Each of them has keys to some pig-houses and wants to buy a certain number of pigs.
All data concerning customers planning to visit the farm on
that particular day are available to Mirko early in the morning so that
he can make a sales-plan in order to maximize the number of pigs sold.

More precisely, the procedure is as following: the customer
arrives, opens all pig-houses to which he has the key, Mirko sells a
certain number of pigs from all the unlocked pig-houses to him, and, if
Mirko wants, he can redistribute the remaining pigs across the unlocked
pig-houses.

An unlimited number of pigs can be placed in every pig-house.

Write a program that will find the maximum number of pigs that he can sell on that day.

Input

The first line of input contains two integers M and N, 1 <= M
<= 1000, 1 <= N <= 100, number of pighouses and number of
customers. Pig houses are numbered from 1 to M and customers are
numbered from 1 to N.

The next line contains M integeres, for each pig-house
initial number of pigs. The number of pigs in each pig-house is greater
or equal to 0 and less or equal to 1000.

The next N lines contains records about the customers in the
following form ( record about the i-th customer is written in the
(i+2)-th line):

A K1 K2 ... KA B It means that this customer has key to the
pig-houses marked with the numbers K1, K2, ..., KA (sorted
nondecreasingly ) and that he wants to buy B pigs. Numbers A and B can
be equal to 0.

Output

The first and only line of the output should contain the number of sold pigs.

Sample Input

3 3
3 1 10
2 1 2 2
2 1 3 3
1 2 6

Sample Output

7

题意 : 有N个顾客,有M个猪圈,每个猪圈有一定的猪,在开始的时候猪圈都是关闭的,
顾客来买猪,顾客打开某个猪圈,可以在其中挑选一定的猪的数量,在这个顾客走后,可以在打开的
猪圈中将某个猪圈的一些猪牵到另外一个打开的猪圈,然后所有的猪圈会关闭,这样下一个顾客来了继续上面的工作

思路分析 :  参考此文章即可 :http://wenku.baidu.com/view/0ad00abec77da26925c5b01c.html代码示例 :  
const int maxn = 1e4+5;
const int inf = 0x3f3f3f3f;

int m, n;
int a[1005];
vector<int>ve[1005];
struct node
{
    int to, flow;
    int next;
}e[maxn];
int head[maxn];
int cnt = 0;
int s, t;

void addedge(int u, int v, int w){
    e[cnt].next = head[u], e[cnt].to = v, e[cnt].flow = w, head[u] = cnt++;
    e[cnt].next = head[v], e[cnt].to = u, e[cnt].flow = 0, head[v] = cnt++;
}
int belong[1005];
int dep[1005], que[maxn];

bool bfs(int s, int t){
    int head1 = 0, tail = 1;
    memset(dep, 0, sizeof(dep));
    que[0] = s; dep[s] = 1;
    while(head1 < tail){
        int v = que[head1++];
        for(int i = head[v]; i != -1; i = e[i].next){
            int to = e[i].to;
            if (e[i].flow && !dep[to]) {
                dep[to] = dep[v]+1;
                que[tail++] = to;
            }
        }
    }
    return dep[t];
}
int dfs(int u, int f1){
    if (f1 == 0 || u == t) return f1;

    int f = 0;
    for(int i = head[u]; i != -1; i = e[i].next){
        int to = e[i].to;
        if (e[i].flow && dep[to] == dep[u]+1){
            int x = dfs(to, min(e[i].flow, f1));
            e[i].flow -= x; e[i^1].flow += x;
            f1 -= x, f += x;
            if (f1 == 0) return f;
        }
    }
    if (!f) dep[u] = -2;
    return f;
}

int maxflow(int s, int t){
    int ans = 0;
    while(bfs(s, t)){
        ans += dfs(s, inf);
    }
    return ans;
}

int main() {
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    int x, y;
    cin >> m >> n;
    s = 0, t = n+1;
    memset(head, -1, sizeof(head));
    for(int i = 1; i <= m; i++) scanf("%d", &a[i]);
    for(int i = 1; i <= n; i++){
        scanf("%d", &x);
        for(int j = 1; j <= x; j++) {
            scanf("%d", &y);
            ve[i].push_back(y);
        }
        scanf("%d", &y);
        addedge(i, t, y);
    }
    for(int i = 1; i <= n; i++){
        for(int j = 0; j < ve[i].size(); j++){
            int v = ve[i][j];
            if (!belong[v]) {
                belong[v] = i;
                addedge(s, i, a[v]);
            }
            else {
                addedge(belong[v], i, inf);
                belong[v] = i;
            }
        }
    }
    printf("%d\n", maxflow(s, t));
    return 0;
}

原文地址:https://www.cnblogs.com/ccut-ry/p/9932842.html

时间: 11-09

小猪分配 , 最大流的相关文章

CUDA实例练习(十):多个cuda流

1 #include <stdio.h> 2 #include <cuda_runtime.h> 3 #include <device_launch_parameters.h> 4 #include "book.h" 5 6 #define N (1024*1024) 7 #define FULL_DATA_SIZE (N * 20) 8 9 __global__ void kernel(int *a, int *b, int *c){ 10 int

iOS Working with Streams 处理流 官方文档翻译(四)

原文地址:developer 这个篇章蛮长的,也翻译了好长时间.祝大家周末愉快! 处理流 本章讨论了如何创建.打开.读写流检查错误.它还描述了如何阅读一个read streams,如何写一个write streams,如 何防止读或写流时阻塞,以及如何通过代理服务器引导流. 使用读取流 核心基础流可用于读写文件或使用网络套接字.除了创建这些流的过程中,他们的行为类似. 创建一个读取流 首先创建一个读取流.清单2创建一个读取一个文件流 清单2创建一个从文件读取流 CFReadStreamRef m

分配内存(Linux设备驱动程序)

分配内存 介绍设备驱动程序中使用内存的方法: 如何最好地利用系统内存资源. kmalloc函数 kmalloc内存分配引擎是一个功能强大的工具. #include <linux/slab.h> void *kmalloc(size_t size, int flags); 参数分配表示flags能够以多种方式控制kmalloc的行为. 标志GFP_KERNEL表示内存分配是代表运行在内核空间的进程执行的,这意味着调用它的函数正代表 某个进程执行系统调用. 使用GFP_KERNEL允许kmallo

sockt套接字编程

一.Socket简介 Socket是进程通讯的一种方式,即调用这个网络库的一些API函数实现分布在不同主机的相关进程之间的数据交换. 几个定义: (1)IP地址:即依照TCP/IP协议分配给本地主机的网络地址,两个进程要通讯,任一进程首先要知道通讯对方的位置,即对方的IP. (2)端口号:用来辨别本地通讯进程,一个本地的进程在通讯时均会占用一个端口号,不同的进程端口号不同,因此在通讯前必须要分配一个没有被访问的端口号. (3)连接:指两个进程间的通讯链路. (4)半相关:网络中用一个三元组可以在

socket计划编制的原则

socket编程原理 1.问题的引入 1) 普通的I/O操作过程: UNIX系统的I/O命令集,是从Maltics和早期系统中的命令演变出来的,其模式为打开一读/写一关闭(open-write-read-close).在一个用户进程进行I/O操作时,它首先调用"打开"获得对指定文件或设备的使用权,并返回称为文件描写叙述符的整型数,以描写叙述用户在打开的文件或设备上进行I/O操作的进程.然后这个用户进程多次调用"读/写"以数据传输.当全部的传输操作完毕后,用户进程关闭

文件创建读取 删除

在ASP.NET中,文件处理的整个过程都是围绕着System.IO 这个名称空间展开的.这个名称空间中具有执行文件读.写所需要的类.本文从最基本的操作开始,解释在ASP.NET中文件处理的概念,包括如从一个文件中读取内容.如何向一个文件中写入内容和如何删除一个文件. 前面已经提到,要想在ASP.NET 页面中进行文件处理,必须要有"System.IO"名称空间.所以,第一步就是引入这个名称空间: <%@ Import Namespace="System.IO"

socket tcp

一.Socket简介 Socket是进程通讯的一种方式,即调用这个网络库的一些API函数实现分布在不同主机的相关进程之间的数据交换. 几个定义: (1)IP地址:即依照TCP/IP协议分配给本地主机的网络地址,两个进程要通讯,任一进程首先要知道通讯对方的位置,即对方的IP. (2)端口号:用来辨别本地通讯进程,一个本地的进程在通讯时均会占用一个端口号,不同的进程端口号不同,因此在通讯前必须要分配一个没有被访问的端口号. (3)连接:指两个进程间的通讯链路. (4)半相关:网络中用一个三元组可以在

基本的TCP套接字编程

上图基本展示了TCP客户端与服务器编程的基本的流程. 1.面向连接编程(TCP) 面向连接的网络应用程序开发流程比较固定,需要开发者创建服务器与客户端两个应用程序,通过网络是想进程间的通讯. ●     服务器端流程 1        创建套接字(socket) 2        服务绑定(bind) 3        服务侦听(listen) 4        处理新到连接(accept) 5       数据收发(recv\send) 6       套接字关闭(close) ●     客

第六次小组会议——项目管理

软件项目管理计划:巧克力爱好者匿名项目 这份开发巧克力爱好者匿名软件产品的计划是由五个人的小组拟制的,这五个人分别是阮梦绯,胡瑗,李斌,陈金栋,程鹏. 1 简介 1.1 项目概述 1.1.1  意图.范畴和目标 这个项目的目标是开发一个软件产品,能够为各种巧克力上瘾者提供咨询和医疗. 1.1.2  假设和限制 包含以下限制: 必须满足最后期限. 产品必须是可靠的. 产品必须是能用的. 1.1.3  项目可交付使用    将在最后期限前交付. 1.1.4  时间表 需求流 分析流 设计流 实现流

Java中I/O流之数据流

Java 中的数据流: 对于某问题:将一个 long 类型的数据写到文件中,有办法吗?    转字符串 → 通过 getbytes() 写进去,费劲,而且在此过程中 long 类型的数需要不断地转换. 现在,Java 中的数据流能够很好的解决这个问题(不需要转换,直接写进去) 1. DataInputStream 与 DataOutputStream 分别继承自 InputStream.OutputStream, 它属于处理流,需要分别套接在 InputStream.OutputStream 类