本文主要是介绍POJ 1149 PIGS (最大流Dinic)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：话说一个猪圈管理员，他本身没有猪圈的钥匙。每天会有许多顾客来买猪，这些顾客自己带着某些猪圈的钥匙。每当一个顾客来买猪，这些打开的猪圈里的猪可以随意流动，买完猪之后打开的猪圈全部关闭。现在已知每个猪圈里猪的的数量，每一名顾客拥有的钥匙以及他想购买的猪的数量。求管理员可以卖出的最大数量。
题解：构图是难点在于猪的流动。我是这样想的，假设顾客A可以打开了猪圈1,3,5，他需要购买numA头猪，由于每次被打开的猪圈之间的猪可以自由分配，那么猪圈1,3,5就可以视作一个集合X，当顾客A买完猪之后，集合X剩下的值为X-numA；如果下一次有一位顾客B可以打开猪圈2,4,5，他需要买numB头猪，将2,4,5其视作集合Y。由于X,Y之间有一个公共点5，那么集合Y的最大数量等于Y+X-numA。这样就比较清晰了。所有到达顾客A的流分作两部分，一部分流向汇点（numA）。另一部分流向顾客B（X-numA）。所以从A至B有一条边。
#include <iostream>
using namespace std;
#define MAX 2000
#define INF 999999999
#define min(a,b) (a<b?a:b)
struct Edge
{
int st, ed;
int next;
int flow;
} edge[MAX*10];
bool key[101][1001]; // key[i][j] == true 表示第i名顾客拥有猪圈j的钥匙
int head[MAX], out[MAX];
int que[MAX], stk[MAX];
int leve[MAX], house[MAX];
int E, M, N, src, dest;
void add_edge ( int u, int v, int val )
{
edge[E].st = u;
edge[E].ed = v;
edge[E].flow = val;
edge[E].next = head[u];
head[u] = E++;
edge[E].st = v;
edge[E].ed = u;
edge[E].flow = 0;
edge[E].next = head[v];
head[v] = E++;
}
bool dinic_bfs ()
{
int front, rear, u, v, i;
memset(leve,-1,sizeof(leve));
front = rear = 0;
que[rear++] = src;
leve[src] = 0;
while ( front != ( rear + 1 ) % MAX )
{
u = que[front];
front = ( front + 1 ) % MAX;
for ( i = head[u]; i != -1; i = edge[i].next )
{
v = edge[i].ed;
if ( leve[v] == -1 && edge[i].flow > 0 )
{
leve[v] = leve[u] + 1;
que[rear] = v;
rear = ( rear + 1 ) % MAX;
}
}
}
return leve[dest] >= 0;
}
int Dinic ()
{
int top, u, i;
int maxFlow = 0, minf;
while ( dinic_bfs () )
{
top = 0; u = src;
for ( i = src; i <= dest; i++ )
out[i] = head[i];
while ( out[src] != -1 )
{
if ( u == dest )
{
minf = INF;
for ( i = top - 1; i >= 0; i-- )
minf = min ( edge[stk[i]].flow, minf );
maxFlow += minf;
for ( i = top - 1; i >= 0; i-- )
{
edge[stk[i]].flow -= minf;
edge[stk[i]^1].flow += minf;
if ( edge[stk[i]].flow == 0 ) top = i;
}
u = edge[stk[top]].st;
}
else if ( out[u] != -1 && leve[u] + 1 == leve[edge[out[u]].ed] && edge[out[u]].flow > 0 )
{
stk[top++] = out[u];
u = edge[out[u]].ed;
}
else
{
while ( top > 0 && u != src && out[u] == -1 )
u = edge[stk[--top]].st;
out[u] = edge[out[u]].next;
}
}
}
return maxFlow;
}
int main()
{
scanf("%d%d",&M,&N);
src = E = 0;
dest = M + N + 1;
memset(key,0,sizeof(key));
memset(head,-1,sizeof(head));
int i, j, k, A, B;
for ( i = 1; i <= M; i++ )
{
scanf("%d",&house[i]);
add_edge ( src, i, house[i] );
}
for ( i = 1; i <= N; i++ )
{
scanf("%d",&A);
for ( j = 1; j <= A; j++ )
{
scanf("%d",&k);
key[i][k] = true;
add_edge ( k, i+M, house[k] );
}
for ( j = 1; j < i; j++ ) //枚举第i名顾客之前的顾客
{
for ( k = 1; k <= M; k++ )
if ( key[j][k] && key[i][k] ) //若j,i有相同的钥匙，则可以连接一条从j到i的边，容量为无穷
add_edge ( j+M, i+M, INF );
}
scanf("%d",&B);
add_edge ( i+M, dest, B );
}
printf("%d\n",Dinic());
return 0;
}
这篇关于POJ 1149 PIGS (最大流Dinic)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
