首页 > 代码库 > POJ 1149 PIGS 迈克卖猪问题 网络流构图+三种AC方法
POJ 1149 PIGS 迈克卖猪问题 网络流构图+三种AC方法
题目链接：POJ 1149 PIGS
PIGS
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 |
分析：
本题关键在如何构图，构好图就可以套模板直接求解了。其实大部分的网络流题目只要能够图就基本简单了。不过构图是个费脑力的过程。
构图方法如下：
（1）设一个源点s、一个汇点t，
（2）将顾客看做中间节点，
（3）s和每个猪圈的第一个顾客连边，容量为开始时猪圈中猪的数目。如果和某个节点有重边，则将容量值合并（因为源点流出的流量就是所有猪圈能提供的猪的数目），
（4）顾客j紧跟在顾客i之后打开某个猪圈，则边<i, j>的容量为INF，因为如果顾客j紧跟顾客i之后打开某个猪圈，那么迈克就有可能根据顾客j的要求将其他猪圈中的猪调整到该猪圈，这样顾客j就能买到尽可能多的猪，
（5）每个顾客和汇点之间连边，边的容量是顾客所希望买的猪的数目。
完成构图后，可以进行最大流的求解了。三种方法
（1）EK算法，最短增广路算法（即先用BFS求增广路，然后再增广，但是每次都要BFS，时间复杂度不好。
实现如下：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
#define maxn 1010
#define INF 0x3f3f3f3f
int ans, s, t, n;
int a[maxn], pre[maxn];
int flow[maxn][maxn];
int cap[maxn][maxn];
void EK()
{
queue<int> q;
memset(flow, 0, sizeof(flow));
ans = 0;
while(1)
{
memset(a, 0, sizeof(a));
a[s] = INF;
q.push(s);
while(!q.empty()) //bfs找增广路径
{
int u = q.front();
q.pop();
for(int v = 1; v <= n; v++)
if(!a[v] && cap[u][v] > flow[u][v])
{
pre[v] = u;
q.push(v);
a[v] = min(a[u], cap[u][v]-flow[u][v]);
}
}
if(a[t] == 0) break;
for(int u = t; u != s; u = pre[u]) //改进网络流
{
flow[pre[u]][u] += a[t];
flow[u][pre[u]] -= a[t];
}
ans += a[t];
}
}
int main()
{
//freopen("poj_1149.txt", "r", stdin);
int m, x, A, B, pig[maxn], pre[maxn];
memset(cap, 0, sizeof(cap));
scanf("%d%d", &m, &n);
memset(pre, -1, sizeof(pre));
s = 0; t = n+1;
for(int i = 1; i <= m; i++)
scanf("%d", &pig[i]);
for(int i = 1; i <= n; i++)
{
scanf("%d", &A);
for(int j = 0; j < A; j++)
{
scanf("%d", &x);
if(pre[x] == -1)
cap[s][i] += pig[x];
else
cap[pre[x]][i] = INF;
pre[x] = i;
}
scanf("%d", &cap[i][t]);
}
n += 2;
EK();
printf("%d\n", ans);
return 0;
}
（2）Dinic算法。与EK同属SAP算法， 利用层次图来找最短路，然后用DFS增广。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
#define maxn 1010
#define INF 0x3f3f3f3f
struct Edge
{
int from, to, cap;
};
vector<Edge> EG;
vector<int> G[maxn];
int n, s, t, ans, d[maxn], cur[maxn];
void addEdge(int from, int to, int cap)
{
EG.push_back((Edge){from, to, cap});
EG.push_back((Edge){to, from, 0});
int x = EG.size();
G[from].push_back(x-2);
G[to].push_back(x-1);
}
bool bfs()
{
memset(d, -1, sizeof(d));
queue<int> q;
q.push(s);
d[s] = 0;
while(!q.empty())
{
int x = q.front();
q.pop();
for(int i = 0; i < G[x].size(); i++)
{
Edge& e = EG[G[x][i]];
if(d[e.to] == -1 && e.cap > 0)
{
d[e.to] = d[x]+1;
q.push(e.to);
}
}
}
return (d[t]!=-1);
}
int dfs(int x, int a)
{
if(x == t || a == 0) return a;
int flow = 0, f;
for(int& i = cur[x]; i < G[x].size(); i++)
{
Edge& e = EG[G[x][i]];
if(d[x]+1 == d[e.to] && (f = dfs(e.to, min(a, e.cap))) > 0)
{
e.cap -= f;
EG[G[x][i]^1].cap += f;
flow += f;
a -= f;
if(a == 0) break;
}
}
return flow;
}
void Dinic()
{
ans = 0;
while(bfs())
{
memset(cur, 0, sizeof(cur));
ans += dfs(s, INF);
}
}
int main()
{
//freopen("poj_1149.txt", "r", stdin);
int m, x, A, B, pig[maxn], pre[maxn];
scanf("%d%d", &m, &n);
memset(pre, -1, sizeof(pre));
s = 0; t = n+1;
for(int i = 1; i <= m; i++)
scanf("%d", &pig[i]);
for(int i = 1; i <= n; i++) {
scanf("%d", &A);
for(int j = 0; j < A; j++) {
scanf("%d", &x);
if(pre[x] == -1)
addEdge(s, i, pig[x]);
else
addEdge(pre[x], i, INF);
pre[x] = i;
}
scanf("%d", &B);
addEdge(i, t, B);
}
n += 2;
Dinic();
printf("%d\n", ans);
return 0;
}
（3）ISAP，改进ISAP算法，是目前最好算法。也是通过层次网络找最短路，但是反向BFS，且BFS只需要运行一次
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
#define maxn 1010
#define INF 0x3f3f3f3f
struct Edge
{
int from, to, cap, flow;
};
vector<Edge> EG;
vector<int> G[maxn];
int n, s, t, ans, d[maxn], cur[maxn], p[maxn], num[maxn];
bool vis[maxn];
void addEdge(int from, int to, int cap)
{
EG.push_back((Edge){from, to, cap, 0});
EG.push_back((Edge){to, from, 0, 0});
int x = EG.size();
G[from].push_back(x-2);
G[to].push_back(x-1);
}
void bfs()
{
memset(vis, false, sizeof(vis));
queue<int> q;
vis[t] = true;
d[t] = 0;
q.push(t);
while(!q.empty()) {
int x = q.front();
q.pop();
for(int i = 0; i < G[x].size(); i++) {
Edge& e = EG[G[x][i]^1];
if(!vis[e.from] && e.cap > e.flow) {
vis[e.from] = true;
d[e.from] = d[x]+1;
q.push(e.from);
}
}
}
}
int augment()
{
int x = t, a = INF;
while(x != s) {
Edge& e = EG[p[x]];
a = min(a, e.cap-e.flow);
x = EG[p[x]].from;
}
x = t;
while(x != s) {
EG[p[x]].flow += a;
EG[p[x]^1].flow -= a;
x = EG[p[x]].from;
}
return a;
}
void ISAP()
{
ans =0;
bfs();
memset(num, 0, sizeof(num));
for(int i = 0; i < n; i++)
num[d[i]]++;
int x = s;
memset(cur, 0, sizeof(cur));
while(d[s] < n) {
if(x == t) {
ans += augment();
x = s;
}
bool flag = false;
for(int i = cur[x]; i < G[x].size(); i++) {
Edge& e = EG[G[x][i]];
if(e.cap > e.flow && d[x] == d[e.to]+1) {
flag = true;
p[e.to] = G[x][i];
cur[x] = i;
x = e.to;
break;
}
}
if(!flag) {
int m = n-1;
for(int i = 0; i < G[x].size(); i++) {
Edge& e = EG[G[x][i]];
if(e.cap > e.flow)
m = min(m, d[e.to]);
}
if(--num[d[x]] == 0) break;
num[d[x] = m+1]++;
cur[x] = 0;
if(x != s)
x = EG[p[x]].from;
}
}
}
void Clear()
{
EG.clear();
for(int i = 0; i < n; ++i)
G[i].clear();
}
int main()
{
//freopen("poj_1149.txt", "r", stdin);
int m, x, A, B, pig[maxn], pre[maxn];
scanf("%d%d", &m, &n);
memset(pre, -1, sizeof(pre));
s = 0; t = n+1;
for(int i = 1; i <= m; i++)
scanf("%d", &pig[i]);
for(int i = 1; i <= n; i++)
{
scanf("%d", &A);
for(int j = 0; j < A; j++)
{
scanf("%d", &x);
if(pre[x] == -1)
addEdge(s, i, pig[x]);
else
addEdge(pre[x], i, INF);
pre[x] = i;
}
scanf("%d", &B);
addEdge(i, t, B);
}
n += 2;
ISAP();
printf("%d\n", ans);
Clear();
return 0;
}
比较POJ 1149 PIGS 迈克卖猪问题 网络流构图+三种AC方法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。