我用网络流做的超时，觉得应该是模型建得太麻烦了。

先建一个m*n的网格g，如果第i个顾客可以打开d1..dk，就分别在g[i-1][d1..dk]到g[i][d1..dk]做有向边
然后加n个顶点v，如果第i个顾客可以打开d1..dk，就在g[i-1][d1..dk]到v[i-1]做有向边
从源点到g[0][0..m-1]做有向边，权为pig的个数
从v[0..n-1]到漏点做有向边，权为customer的要求

这样最多可能有1000102个顶点，可怜我只好用邻接表来保存图……
因为用了大量指针不敢在Judge上跑，就先找来数据测了一下
顶点不超过5000的时候还比较快啦，但上万的顶点就会歇掉……

我以前没做过最大流的题，请教各位这道题应该如何建立模型呢？

• Re:请教网络流的做法 (228) rruucc 2003-06-06 14:06:29
  • 我明白啦！感激ing... (43) alcyone 2003-06-06 17:19:30
  • 要是所有的顾客拥有的钥匙不能保证打开所有的猪圈,那这样做应该有问题 (29) huicpc21 2006-08-14 10:35:08
  • 这样节点岂不是有 1000 * 100 个，不会超时吗？ (68) ImLazy 2008-05-22 15:12:37
    • 明白了，你所说的 Pi(1) 到 Pi(J) 都是包含在 N 个顾客的节点中的。总共就是 N + 2 个节点对吗。 (2) ImLazy 2008-05-22 15:32:52
  • Re:请教网络流的做法 (246) Sempr 2008-07-26 18:52:07
  • Re:请教网络流的做法 (257) xiamaomi 2009-08-18 09:53:47
    • Re:请教网络流的做法 (22) leon_L 2009-08-18 10:08:59