题目链接:
https://vjudge.net/problem/POJ-1149
题目大意:
M个猪圈,N个顾客,每个顾客有一些的猪圈的钥匙,只能购买这些有钥匙的猪圈里的猪,而且要买一定数量的猪,每个猪圈有已知数量的猪,
但是猪圈可以重新打开,将猪的个数,重新分配,以达到卖出的猪的数量最多。
思路:
难点在于如何构造容量网络
(1)将顾客看做出源点和汇点之外的结点,另外增加源点s和汇点t
(2)源点和每个猪圈的第一个用户连边,边权是猪圈中猪的数目
(3)若有重边,将权合并
(4)顾客j紧跟在顾客i之后打开某个猪圈,则边<i, j>是正无穷,因为如果顾客j紧跟在i之后,那么流到i的猪可以自由分配该j,所以设置为INF。
(5)每个顾客可汇点之间的连边,边权就是自己希望,买到的猪的数目
构建好容量网络之后,就用模板就OK啦
#include<iostream>
#include<vector>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = + ;//顾客的数目
const int maxm = + ;//猪圈的数目 struct edge
{
int u, v, c, f;
edge(int u, int v, int c, int f):u(u), v(v), c(c), f(f){}
};
vector<edge>e;
vector<int>G[maxn];
int a[maxn], p[maxn];
int m;
void init(int n)
{
for(int i = ; i <= n; i++)
G[i].clear();
e.clear();
}
void addedge(int u, int v, int c)
{
e.push_back(edge(u, v, c, ));
e.push_back(edge(v, u, , ));//反向边
m = e.size();
G[u].push_back(m - );
G[v].push_back(m - );
}
int Maxflow(int s, int t)
{
int flow = ;
for(;;)
{
memset(a, , sizeof(a));//每次找增广路的每个点的流量
queue<int>q;
q.push(s);
a[s] = INF;
while(!q.empty())
{
int u = q.front();
q.pop();
for(int i = ; i < G[u].size(); i++)
{
edge& now = e[G[u][i]];
int v = now.v;
if(!a[v] && now.c > now.f)//v点还没有流到并且这条边还没满
{
p[v] = G[u][i];//反向记录边
a[v] = min(a[u], now.c - now.f);//到达v点的水量取决于边剩余的容量和u点的水量
q.push(v);
}
}
if(a[t])break;//已到达终点
}
if(!a[t])break;//已经找不到增广路
for(int u = t; u != s; u = e[p[u]].u)
{
e[p[u]].f += a[t];
e[p[u]^].f -= a[t];
}
flow += a[t];
}
return flow;
}
int pig[maxm];//每个猪圈猪的数目
int last[maxm];//每个猪圈的前一个顾客的序号
int Map[maxn][maxn];//顾客顾客之间的边,有重边,先用数组记录
int main()
{
int n, m;
cin >> m >> n;
for(int i = ; i <= m; i++)cin >> pig[i];
int s = , t = n + ;//设置源点和汇点
int d, x;
for(int i = ; i <= n; i++)//顾客编号
{
cin >> d;
for(int j = ; j < d; j++)
{
cin >> x;//猪圈编号
if(last[x] == )//猪圈的第一个顾客
addedge(s, i, pig[x]);
else addedge(last[x], i, INF);//顾客i紧接着顾客last[x]后面打开猪圈x
last[x] = i;
}
cin >> x;//到汇点的边的权值
addedge(i, t, x);
}
cout<<Maxflow(s, t)<<endl;
return ;
}