POJ - 1149-网络流

xiaoxiao2021-02-28  31

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 6Sample Output

7

 建图方式学习的其他人的,如下图(自己画的)

#include <stdio.h> #include <cstdio> #include <algorithm> #include <string.h> #include <queue> #define INF 0x3f3f3f3f using namespace std; const int max_n=1e5+10; int pig[max_n],people[max_n]; int OUT,IN,num; int h[max_n],pre[max_n]; int dis[max_n],flag[max_n]; struct Edge { int u,v; int next,val; }e[max_n]; void add_edge(int u,int v,int val) { e[num].u=u; e[num].v=v; e[num].val=val; e[num].next=h[u]; h[u]=num++; } int BFS(int u) { memset(dis,-1,sizeof(dis)); queue <int> q; q.push(u); dis[u]=0; while(!q.empty()) { u=q.front();q.pop(); for(int i=h[u];i!=-1;i=e[i].next) { int v=e[i].v; if(dis[v]==-1&&e[i].val>0) { dis[v]=dis[u]+1; q.push(v); } } } if(dis[IN]>=0) return 1; return 0; } int dfs(int u,int f) { if(u==IN) return f; if(f<=0) return 0; int a; for(int i=h[u];i!=-1;i=e[i].next) { int v=e[i].v; if(dis[v]==dis[u]+1&&e[i].val>0&&(a=dfs(v,min(f,e[i].val)))) { e[i].val-=a; e[i^1].val+=a; return a; } } return 0; } int dinic() { int res=0; int ans;//printf("******\n"); while(BFS(OUT)) { while((ans=dfs(OUT,INF))) res+=ans; } return res; } int main() { int m,n; while(scanf("%d%d",&m,&n)!=EOF) { memset(h,-1,sizeof(h)); memset(pre,0,sizeof(pre)); memset(flag,0,sizeof(flag)); num=0; IN=n+1;OUT=0; for(int i=1;i<=m;i++) scanf("%d",&pig[i]); for(int i=1;i<=n;i++) { int u,a,b; scanf("%d",&a); for(int j=0;j<a;j++) { scanf("%d",&u); if(!pre[u]) { if(!flag[i]) { add_edge(OUT,i,pig[u]); add_edge(i,OUT,0); flag[i]=num-2; } else { e[flag[i]].val+=pig[u]; } pre[u]=i; } else { add_edge(pre[u],i,INF); add_edge(i,pre[u],0); } } scanf("%d",&b); add_edge(i,IN,b); add_edge(IN,i,0); } int ret=dinic(); printf("%d\n",ret); } }
转载请注明原文地址: https://www.6miu.com/read-2613359.html

最新回复(0)