当前位置:网站首页>POJ1149 PIGS 【最大流量】
POJ1149 PIGS 【最大流量】
2022-07-06 11:47:00 【全栈程序员站长】
大家好,又见面了,我是全栈君。
PIGS
Time Limit: 1000MS | Memory Limit: 10000K | |
---|---|---|
Total Submissions: 16555 | Accepted: 7416 |
Description
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
Source
Croatia OI 2002 Final Exam – First day
题目大意 Mirko养着一些猪 猪关在一些猪圈里面 猪圈是锁着的 他自己没有钥匙(汗) 仅仅有要来买猪的顾客才有钥匙 顾客依次来 每一个顾客会用他的钥匙打开一些猪圈 买 走一些猪 然后锁上 在锁上之前 Mirko有机会又一次分配这几个已打开猪圈 的猪 如今给出一開始每一个猪圈的猪数 每一个顾客全部的钥匙 和要买走的猪数 问Mirko最多能卖掉几头猪
题解:对于每一个猪圈的第一个购买的人,加入一条源点到这个人的边,权为这个猪圈的猪数,对于后来的且想要购买该猪圈的人。加入一条第一个购买该猪圈的人到该人的边。权为inf,然后加入每一个人到汇点一条边,权值为该人想要购买的猪的头数。至此,构图完毕。
#include <stdio.h>
#include <string.h>
#define inf 0x3fffffff
#define maxn 110
#define maxm 1002
int pig[maxm], m, n, sink;
int G[maxn][maxn], queue[maxn];
bool vis[maxn]; int Layer[maxn];
bool countLayer() {
memset(Layer, 0, sizeof(Layer));
int id = 0, front = 0, now, i;
Layer[0] = 1; queue[id++] = 0;
while(front < id) {
now = queue[front++];
for(i = 0; i <= sink; ++i)
if(G[now][i] && !Layer[i]) {
Layer[i] = Layer[now] + 1;
if(i == sink) return true;
else queue[id++] = i;
}
}
return false;
}
int Dinic() {
int minCut, pos, maxFlow = 0;
int i, id = 0, u, v, now;
while(countLayer()) {
memset(vis, 0, sizeof(vis));
vis[0] = 1; queue[id++] = 0;
while(id) {
now = queue[id - 1];
if(now == sink) {
minCut = inf;
for(i = 1; i < id; ++i) {
u = queue[i - 1];
v = queue[i];
if(G[u][v] < minCut) {
minCut = G[u][v];
pos = u;
}
}
maxFlow += minCut;
for(i = 1; i < id; ++i) {
u = queue[i - 1];
v = queue[i];
G[u][v] -= minCut;
G[v][u] += minCut;
}
while(queue[id - 1] != pos)
vis[queue[--id]] = 0;
} else {
for(i = 0; i <= sink; ++i) {
if(G[now][i] && Layer[now] + 1 == Layer[i] && !vis[i]) {
vis[i] = 1; queue[id++] = i; break;
}
}
if(i > sink) --id;
}
}
}
return maxFlow;
}
int main() {
//freopen("stdin.txt", "r", stdin);
int i, keys, num;
while(scanf("%d%d", &m, &n) == 2) {
sink = n + 1;
for(i = 1; i <= m; ++i)
scanf("%d", &pig[i]);
memset(G, 0, sizeof(G));
for(i = 1; i <= n; ++i) {
scanf("%d", &keys);
while(keys--) {
scanf("%d", &num);
if(pig[num] >= 0) {
G[0][i] += pig[num]; // 0 is source
pig[num] = -i; // 这里是标记第num个猪圈联通的第一个人
} else G[-pig[num]][i] = inf;
}
scanf("%d", &G[i][sink]);
}
printf("%d\n", Dinic());
}
return 0;
}
2015.4.20
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 105;
const int inf = 0x3f3f3f3f;
int G[maxn][maxn], M, N, S, T;
int pigHouse[maxn*10];
int Dinic(int s, int t);
void getMap()
{
memset(G, 0, sizeof(G));
S = 0; T = N + 1;
int i, j, K, pos;
for (i = 1; i <= M; ++i)
scanf("%d", &pigHouse[i]);
for (i = 1; i <= N; ++i) {
scanf("%d", &K);
while (K--) {
scanf("%d", &pos);
if (pigHouse[pos] >= 0) {
G[S][i] += pigHouse[pos];
pigHouse[pos] = -i;
} else {
G[-pigHouse[pos]][i] = inf;
}
}
scanf("%d", &G[i][T]);
}
}
void solve()
{
cout << Dinic(S, T) << endl;
}
int main()
{
while (cin >> M >> N) {
getMap();
solve();
}
return 0;
}
int queue[maxn];
bool vis[maxn]; int Layer[maxn];
bool countLayer(int s, int t) {
memset(Layer, 0, sizeof(Layer));
int id = 0, front = 0, now, i;
Layer[s] = 1; queue[id++] = s;
while(front < id) {
now = queue[front++];
for(i = s; i <= t; ++i)
if(G[now][i] && !Layer[i]) {
Layer[i] = Layer[now] + 1;
if(i == t) return true;
else queue[id++] = i;
}
}
return false;
}
// 源点,汇点,源点编号必须最小,汇点编号必须最大
int Dinic(int s, int t) {
int minCut, pos, maxFlow = 0;
int i, id = 0, u, v, now;
while(countLayer(s, t)) {
memset(vis, 0, sizeof(vis));
vis[s] = true; queue[id++] = s;
while(id) {
now = queue[id - 1];
if(now == t) {
minCut = inf;
for(i = 1; i < id; ++i) {
u = queue[i - 1];
v = queue[i];
if(G[u][v] < minCut) {
minCut = G[u][v];
pos = u;
}
}
maxFlow += minCut;
for(i = 1; i < id; ++i) {
u = queue[i - 1];
v = queue[i];
G[u][v] -= minCut;
G[v][u] += minCut;
}
while(queue[id - 1] != pos)
vis[queue[--id]] = false;
} else {
for(i = s; i <= t; ++i) {
if(G[now][i] && Layer[now] + 1 == Layer[i] && !vis[i]) {
vis[i] = 1; queue[id++] = i; break;
}
}
if(i > t) --id;
}
}
}
return maxFlow;
}
版权声明:本文博客原创文章,博客,未经同意,不得转载。
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/117136.html原文链接:https://javaforall.cn
边栏推荐
- 利用 clip-path 绘制不规则的图形
- 思维导图+源代码+笔记+项目,字节跳动+京东+360+网易面试题整理
- Reflection and illegalaccessexception exception during application
- 10 schemes to ensure interface data security
- [pytorch] yolov5 train your own data set
- LeetCode_格雷编码_中等_89.格雷编码
- How can my Haskell program or library find its version number- How can my Haskell program or library find its version number?
- Swagger2 reports an error illegal DefaultValue null for parameter type integer
- short i =1; I=i+1 and short i=1; Difference of i+=1
- 系统性详解Redis操作Hash类型数据(带源码分析及测试结果)
猜你喜欢
[玩转Linux] [Docker] MySQL安装和配置
反射及在运用过程中出现的IllegalAccessException异常
DaGAN论文解读
思维导图+源代码+笔记+项目,字节跳动+京东+360+网易面试题整理
Dark horse -- redis
系统性详解Redis操作Hash类型数据(带源码分析及测试结果)
[translation] micro survey of cloud native observation ability. Prometheus leads the trend, but there are still obstacles to understanding the health of the system
zabbix 代理服务器 与 zabbix-snmp 监控
Phoenix Architecture 3 - transaction processing
It's enough to read this article to analyze the principle in depth
随机推荐
[play with Linux] [docker] MySQL installation and configuration
保证接口数据安全的10种方案
usb host 驱动 - UVC 掉包
Leetcode 30. 串联所有单词的子串
1805. 字符串中不同整数的数目
Mind map + source code + Notes + project, ByteDance + JD +360+ Netease interview question sorting
Problems encountered in using RT thread component fish
Dark horse -- redis
今日直播 | “人玑协同 未来已来”2022弘玑生态伙伴大会蓄势待发
Classic 100 questions of algorithm interview, the latest career planning of Android programmers
Interpretation of Dagan paper
[calculating emotion and thought] floor sweeper, typist, information panic and Oppenheimer
Hudi vs Delta vs Iceberg
Phoenix Architecture 2 - accessing remote services
C # - realize serialization with Marshall class
深入分析,Android面试真题解析火爆全网
凤凰架构3——事务处理
LeetCode_ Gray code_ Medium_ 89. Gray code
【pytorch】yolov5 训练自己的数据集
深度剖析原理,看完这一篇就够了