【题意】 有M个猪圈，每个猪圈里初始时有若干头猪。一开始所有猪圈都是关闭的。依 次来了N个顾客，每个顾客分别会打开指定的几个猪圈，从中买若干头猪。每 个顾客分别都有他能够买的数量的上限。每个顾客走后，他打开的那些猪圈中的 猪，都可以被任意地调换到其它开着的猪圈里，然后所有猪圈重新关上。问总共 最多能卖出多少头猪。（1 <= N <= 100, 1 <= M <= 1000）
非常好的一道网络流建模题！最大的收获就是：
在面对网络流问题时，如果一时想不出很好的构图方法，不如先构造一个最
直观，或者说最“硬来”的模型，然后再用合并结点和边的方法来简化这个模
型。经过简化以后，好的构图思路自然就会涌现出来了。这是解决网络流问题
的一个好方法。
－－－以下思路来自于Edelweiss大牛的《网络流建模汇总》
【建模方法】 不难想象，这个问题的网络模型可以很直观地构造出来。就拿上面的例子来说， 可以构造出图1所示的模型（图中凡是没有标数字的边，容量都是∞）： • 三个顾客，就有三轮交易，每一轮分别都有3个猪圈和1个顾客的结点。 • 从源点到第一轮的各个猪圈各有一条边，容量就是各个猪圈里的猪的初始 数量。 • 从各个顾客到汇点各有一条边，容量就是各个顾客能买的数量上限。 • 在某一轮中，从该顾客打开的所有猪圈都有一条边连向该顾客，容量都是 ∞。 • 最后一轮除外，从每一轮的i 号猪圈都有一条边连向下一轮的i 号猪圈， 容量都是∞，表示这一轮剩下的猪可以留到下一轮。 • 最后一轮除外，从每一轮被打开的所有猪圈，到下一轮的同样这些猪圈， 两两之间都要连一条边，表示它们之间可以任意流通。
这个网络模型的最大流量就是最多能卖出的数量。图中最多有
2+N+M×N≈100,000个结点。这个模型虽然很直观，但是结点数太多了，计算速
度肯定会很慢。其实不用再想别的算法，就让我们继续上面的例子，用合并的方
法来简化这个网络模型。
首先，最后一轮中没有打开的猪圈就可以从图中删掉了，也就是图中红色
的部分，显然它们对整个网络的流量没有任何影响。
再根据下面网络流节点合并规律：
得到最终的图：
总结本题的构图规则就是：
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define MID(x,y) ((x+y)/2)
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
const int MAXV = 305;
const int MAXE = 10005;
struct node{
int u, v, flow;
int opp;
int next;
};
struct Dinic{
node arc[MAXE];
int vn, en, head[MAXV]; //vn点个数(包括源点汇点),en边个数
int cur[MAXV]; //当前弧
int q[MAXV]; //bfs建层次图时的队列
int path[MAXE], top; //存dfs当前最短路径的栈
int dep[MAXV]; //各节点层次
void init(int n){
vn = n;
en = 0;
mem(head, -1);
}
void insert_flow(int u, int v, int flow){
arc[en].u = u;
arc[en].v = v;
arc[en].flow = flow;
arc[en].opp = en + 1;
arc[en].next = head[u];
head[u] = en ++; arc[en].u = v;
arc[en].v = u;
arc[en].flow = 0; //反向弧
arc[en].opp = en - 1;
arc[en].next = head[v];
head[v] = en ++;
}
bool bfs(int s, int t){
mem(dep, -1);
int lq = 0, rq = 1;
dep[s] = 0;
q[lq] = s;
while(lq 0){
dep[v] = dep[u] + 1;
q[rq ++] = v;
}
}
}
return false;
}
int solve(int s, int t){
int maxflow = 0;
while(bfs(s, t)){
int i, j;
for (i = 1; i arc[path[k]].flow){
minflow = arc[path[k]].flow;
mink = k;
}
for (int k = 0; k outdeg[i]){
dinic.insert_flow(i, n+2, x/2);
sum += x/2;
}
else{
dinic.insert_flow(n+1, i, x/2);
}
}
if (!ok){
puts("impossible");
continue;
}
if (dinic.solve(n+1, n+2) == sum){
puts("possible");
}
else{
puts("impossible");
}
}
return 0;
}