「POJ1149」PIGS

2014年12月27日5,6940

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

题解

一开始感觉和飘飘乎居士的乌龟好像是一样的。。。

然后一看md n*m=10w

。。。

只能膜拜神犇的建模了

[网络流建模汇总][Edelweiss]

http://wenku.baidu.com/link?url=5vBWTkDBeEKYqNiwsqWFdhL7cU-KNXgzYPKriPifFCXw8Qs8DWBrlScSSiNkFMUSGsTkuPKlePeqhlFVk62z0QoCnTKqis9oUs93FXyVjdW

每个顾客用一个结点表示，向汇连其购买上限的边

对于每个猪圈，源向打开它的第一个顾客连该猪圈猪的数量的边

对于每个猪圈，每个顾客向下一个顾客连inf的边

#include<cstdio>
#include<cmath>
#include<ctime>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<set>
#define ll long long
#define mod 1000000007
#define inf 1000000000
using namespace std;
int read()
{
    int f=1,x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int m,n,T,cnt=1;
int h[105],q[105],last[105],cur[105];
int pig[1005];
vector<int> a[105];//每个顾客开的猪圈
int L[1005];
struct edge{
	int next,v,to;
}e[100005];
void insert(int u,int v,int w)
{
	e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;e[cnt].v=w;
	e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;e[cnt].v=0;
}
bool bfs()
{
	int head=0,tail=1;
	memset(h,-1,sizeof(h));
	q[0]=0;h[0]=0;
	while(head!=tail)
	{
		int now=q[head];head++;
		for(int i=last[now];i;i=e[i].next)
			if(e[i].v&&h[e[i].to]==-1)
			{
				h[e[i].to]=h[now]+1;
				q[tail++]=e[i].to;
			}
	}
	return h[T]!=-1;
}
int dfs(int x,int f)
{
	if(x==T)return f;
	int w,used=0;
	for(int i=cur[x];i;i=e[i].next)
		if(h[e[i].to]==h[x]+1)
		{
			w=dfs(e[i].to,min(f-used,e[i].v));
			e[i].v-=w;e[i^1].v+=w;
			if(e[i].v)cur[x]=i;
			used+=w;if(used==f)return f;
		}
	if(!used)h[x]=-1;
	return used;
}
int dinic()
{
	int tmp=0;
	while(bfs())
	{
		for(int i=0;i<=T;i++)cur[i]=last[i];
		tmp+=dfs(0,inf);
	}
	return tmp;
}
int main()
{
	m=read();n=read();T=n+1;
	for(int i=1;i<=m;i++)pig[i]=read();
	for(int i=1;i<=n;i++)
	{
		int x=read(),y;
		while(x--)
		{
			y=read();
			a[i].push_back(y);
		}
		y=read();
		insert(i,T,y);
	}
	for(int i=1;i<=n;i++)
		for(int j=0;j<a[i].size();j++)
		{
			int v=a[i][j];
			if(!L[v])
			{
				L[v]=i;
				insert(0,i,pig[v]);
			}
			else 
			{
				insert(L[v],i,inf);
				L[v]=i;
			}
		}
	printf("%d\n",dinic());
	return 0;
}

100

101

102

103

104

105

106

107

#include<cstdio>

#include<cmath>

#include<ctime>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<queue>

#include<set>

#define ll long long

#define mod 1000000007

#define inf 1000000000

using namespace std;

int read()

{

int f=1,x=0;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int m,n,T,cnt=1;

int h[105],q[105],last[105],cur[105];

int pig[1005];

vector<int> a[105];//每个顾客开的猪圈

int L[1005];

struct edge{

int next,v,to;

}e[100005];

void insert(int u,int v,int w)

{

e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;e[cnt].v=w;

e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;e[cnt].v=0;

}

bool bfs()

{

int head=0,tail=1;

memset(h,-1,sizeof(h));

q[0]=0;h[0]=0;

while(head!=tail)

{

int now=q[head];head++;

for(int i=last[now];i;i=e[i].next)

if(e[i].v&&h[e[i].to]==-1)

{

h[e[i].to]=h[now]+1;

q[tail++]=e[i].to;

}

return h[T]!=-1;

}

int dfs(int x,int f)

{

if(x==T)return f;

int w,used=0;

for(int i=cur[x];i;i=e[i].next)

if(h[e[i].to]==h[x]+1)

{

w=dfs(e[i].to,min(f-used,e[i].v));

e[i].v-=w;e[i^1].v+=w;

if(e[i].v)cur[x]=i;

used+=w;if(used==f)return f;

}

if(!used)h[x]=-1;

return used;

}

int dinic()

{

int tmp=0;

while(bfs())

{

for(int i=0;i<=T;i++)cur[i]=last[i];

tmp+=dfs(0,inf);

}

return tmp;

}

int main()

{

m=read();n=read();T=n+1;

for(int i=1;i<=m;i++)pig[i]=read();

for(int i=1;i<=n;i++)

{

int x=read(),y;

while(x--)

{

y=read();

a[i].push_back(y);

}

y=read();

insert(i,T,y);

}

for(int i=1;i<=n;i++)

for(int j=0;j<a[i].size();j++)

{

int v=a[i][j];

if(!L[v])

{

L[v]=i;

insert(0,i,pig[v]);

}

else

{

insert(L[v],i,inf);

L[v]=i;

}

printf("%d\n",dinic());

return 0;

}

« 「CF498C」Array and Operations 「网络流24题」最长递增子序列问题 »

hzwer.com _ Home | http://hzwer.com

「POJ1149」PIGS

分类目录

热门文章

Myfriends

近期评论