1149 PIGS
Time Limit: 1000MS
Memory Limit: 10000K
Total Submissions: 2084
Accepted: 867
DescriptionMirko 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 arives, 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.
InputThe 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.
OutputThe first and only line of the output should contain the number of sold pigs.
Sample Input
Sample Output
SourceCroatia OI 2002 Final Exam - First day
**********************************************************************************************
**********************************************************************************************
#include<stdio.h>
#include<memory.h>
#include<math.h>
#include<stdlib.h>
const int SIZE = 1010;
const int max = 10000000;
struct Point{
int c,f;
}net[SIZE][SIZE];
int pre[SIZE],s,t,n;
int queue[SIZE],head,tail;
bool bfs()
{
int i;
head = tail = 0;
memset(pre,0,sizeof(pre));
queue[tail++] = s;
pre[s] = s;
while(tail != head){
int temp = queue[head++];
for(i = 1; i <= n+2; i++)
if(pre[i] == 0 && (net[temp][i].c>net[temp][i].f &&
net[temp][i].f>=0 || net[i][temp].c>=net[i][temp].f && net[i][temp].f>0)){
if(net[temp][i].f < net[temp][i].c)
pre[i] = temp;
if(net[i][temp].f > 0)
pre[i] = -temp;
if(i == t){
return true;
}
else
queue[tail++] = i;
}
}
return false;
}
int maxflow()
{
int flow = 0,i;
while(bfs()){
int dx = 0x7FFFFFFF;
int temp;
for(i = t; i != s; i = abs(pre[i])){
if(pre[i] >= 0)
temp = net[pre[i]][i].c-net[pre[i]][i].f;
else
temp = net[i][-pre[i]].f;
if(dx > temp)
dx = temp;
}
for(i = t; i != s; i= abs(pre[i])){
if(pre[i] >= 0)
net[pre[i]][i].f += dx;
else
net[i][-pre[i]].f -= dx;
}
flow += dx;
}
return flow;
}
int num[1010],f[1010];
int main()
{
int m,i,j,temp;
scanf("%d %d",&m,&n);
for(i = 1; i <= m; i++){
scanf("%d",&num[i]);
f[i] = 0;
}
int x;
for(j = 2; j <= n+1; j++){
scanf("%d",&temp);
for(int k = 0; k < temp; k++){
scanf("%d",&x);
if(f[x] == 0){
net[1][j].c += num[x];
f[x] = j;
}
else
net[f[x]][j].c = max;
}
scanf("%d",&temp);
net[j][n+2].c = temp;
}
s = 1; t = n+2;
int out = maxflow();
printf("%d/n",out);
return 0;
}
73 3
3 1 10
2 1 2 2
2 1 3 3
1 2 6이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
POJ 1149 PIGS//MAXFLOWMore precisely, the procedure is as following: the customer arives, opens all pig-houses to which he has the key, Mirko ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
