题意:养猪场里有 m 个猪圈,每个猪圈都上了锁。有 n 要买猪的顾客依次来到养猪场,每个顾客有一些猪圈的钥匙,而且他们要买一定数量的猪。给你一天里依次来的顾客的信息,有哪些猪圈的钥匙,要买猪的数量。
当每个顾客到来时,他将那些他拥有钥匙的猪圈全部打开;从这些猪圈中挑出一些猪卖给他们;同时,你可以重新调整这些被打开的猪圈的猪的数量;当顾客离开时,猪圈再次被锁上。
注意:猪圈的容量是无限的。
求,你能卖出的猪的最大数量。
思路:这里有一个要考虑的,就是在一个顾客来的时候,卖出猪的同时要怎么分配。
把每个顾客来的时候当作一个状态,在增加一个初始状态做源点和一个结束状态做汇点。
当一个顾客是第个来打开猪圈 i ,那就建一条从源点到该顾客的边,权值为猪圈 i 的初始数量。
不是,那就建一条从上一个打开相同猪圈的顾客到该顾客的边,权值为 无重大。
可以把这个看做是,n人去m个水引水到自己家,但是每个人并不是要把引来的水全部用掉他会,引向能和自己连通的其他人的家里。
那怎么统计,每个人用的水量呢,就建一条从该人到汇点的边,权值就是他用的水的数量,这个题里,就是他要买的猪的数量。 弄清楚这些,就是套模板的事。
模板链接
想法:这个题目主要难点,在建模。要是不知道这是个网络流的题目,我真的是一脸懵逼了。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
const int inf = 1e7;
using namespace std;
typedef long long ll;
int pig[1200], flag_pig[1200], n, m;
//flag_pig 标记每位猪圈上次被谁打开过
int maps[120][120];
int flow[120], pre[120];
int bfs(int s, int t){
queue <int> q;
for(int i=0; i<=n+1; i++)
pre[i] = -1;
pre[s] = s;
flow[s] = inf;
q.push(s);
while(!q.empty()){
int u = q.front();
q.pop();
if(u == t)
break;
for(int i=0; i<=t; i++){
if(pre[i]==-1 && maps[u][i]>0){
pre[i] = u;
flow[i] = min(maps[u][i], flow[u]);
q.push(i);
}
}
}
if(pre[t] == -1)
return -1;
else
return flow[t];
}
void EK(int s, int t){
int a = -1, ans = 0;;
while( (a=bfs(s, t))!=-1 ){
int v = t;
while(v != s){
int u = pre[v];
maps[u][v] -= a;
maps[v][u] += a;
v = u;
}
ans += a;
}
printf("%d
", ans);
}
int main()
{
while(scanf("%d%d", &m, &n)!=EOF){
memset(maps, 0, sizeof(maps));
memset(flow, 0, sizeof(flow));
for(int i=1; i<=m; i++){
scanf("%d", &pig[i]);
flag_pig[i] = 0;
}
for(int i=1; i<=n; i++){//建图
int k;
scanf("%d", &k);
while(k--){
int ki;
scanf("%d", &ki);
if(flag_pig[ki]){
if(maps[flag_pig[ki]][i] != inf)
maps[flag_pig[ki]][i] = inf;
}
else{
maps[0][i] += pig[ki];
flag_pig[ki] = i;
}
}
int b;
scanf("%d", &b);
maps[i][n+1] = b;
}
EK(0, n+1);//开始套Edmonds-Karp算法模板
}
return 0;
}