【最大流+dinic+二分枚举】北大 poj 3189 Steady Cow Assignment

/* THE PROGRAM IS MADE BY PYY *//*----------------------------------------//    Copyright (c) 2012 panyanyany All rights reserved.    URL   : http://poj.org/problem?id=3189    Name  : 3189 Steady Cow Assignment    Date  : Monday, February 13, 2012    Time Stage : 5 hours    Result:9802586panyanyany3189Accepted948K329MSC++4870B2012-02-13 21:00:17Test Data :Review :题意理解不到位，wa无数次，数组开错，继续WA……发现每次做网络流都要3个小时以上……好悲剧……以后最多做两个小时，不行就先放下，花太多时间效果又不好，太不值得了……这题不是单纯的二分枚举，思维定势了，老是理解不了，看了答案也不明白。想了很久，才终于想到，二分枚举的只是区间长度，还要在每次二分枚举的时候向右移动那个定区间。如题目中的例子一样，可以看作是x轴上有四个单位，假如某次枚举的时候，枚举到2个单位，也就是说，可能是[1,2]，[2,3]，[3,4]。也就是说，2个单位的时候，要做三次图，第一次是每个牛只能选择自己第1喜欢和第2喜欢的棚，第二次是每个牛只能选择自己第2喜欢和第3喜欢的棚……//----------------------------------------*/#include <stdio.h>#include <stdlib.h>#include <string.h>#include <math.h>#define MEM(a, v)memset (a, v, sizeof (a))// a for address, v for value#define max(x, y)((x) > (y) ? (x) : (y))#define min(x, y)((x) < (y) ? (x) : (y))#define INF(0x3f3f3f3f)#define MAXN(1002*2)#define MAXE(MAXN*22*4)#define DB/##/struct EDGE {int u, v, c, n ;};intn, b, eCnt, s, t ;intdist[MAXN], q[MAXN], vertex[MAXN], barn[MAXN][22], cap[22] ;EDGEedge[MAXE] ;inline void init(){eCnt = 0 ;MEM (vertex, -1) ;}inline void insert (const int u, const int v, const int c){edge[eCnt].u = u ;edge[eCnt].v = v ;edge[eCnt].c = c ;edge[eCnt].n = vertex[u] ;vertex[u] = eCnt++ ;edge[eCnt].u = v ;edge[eCnt].v = u ;edge[eCnt].c = 0 ;edge[eCnt].n = vertex[v] ;vertex[v] = eCnt++ ;}int dinic (int beg, int end){int ans = 0 ;while (true){int head, tail, u, v, e ;MEM(dist, -1) ;head = tail = 0 ;q[tail++] = beg ;dist[beg] = 0 ;// 广搜，构建层次图while (head < tail){v = q[head++] ;for (e = vertex[v] ; e != -1 ; e = edge[e].n){u = edge[e].u ;int to = edge[e].v ;int cost = edge[e].c ;if (cost > 0 && dist[to] == -1){dist[to] = dist[u] + 1 ;q[tail++] = to ;if (to == end){head = tail ;break ;}}}}if (dist[end] == -1)break ;// v 表示增广路径的先头顶点v = beg ;tail = 0 ;while (true){DBprintf("--- tail:%d ", tail) ;if (v == end){int i, flow = INF, ebreak ;// 寻找此路径可增加的最大流量for (i = 0 ; i < tail ; ++i)if (flow > edge[q[i]].c){flow = edge[q[i]].c ;ebreak = i ;}ans += flow ;// 根据刚才找到的最大流，更新此路径上的所有边for (i = 0 ; i < tail ; ++i){edge[q[i]].c -= flow ;// 正向边减流edge[q[i]^1].c += flow ;// 反向边加流}// 增广路径的先头顶点退至0流量的正向边的起始顶点v = edge[q[ebreak]].u ;tail = ebreak ;DBprintf ("end --- v:%d ebreak:%d, ans:%d\n", v, ebreak, ans) ;}// 寻找有无可以继续增广的边// 即，测试所有从顶点 v 起始的边中，是否有可以增广的边// find a way from e to any vertex in "layers"for (e = vertex[v] ; e != -1 ; e = edge[e].n){// 为了避免 -1 + 1 == 0 的情况，需要测试 dist[edge[e].u] > -1// 其实这一步貌似可以省略，因为既然能够作为增广路径的先头顶点，// 其必然就在层次图中，因此 dist[u] 也就一定会 大于 -1 if (edge[e].c > 0 && //dist[edge[e].u] > -1 &&dist[edge[e].u]+1 == dist[edge[e].v]){//printf ("dist[%d]+1 == dist[%d]: %d+1 == %d\n", //edge[e].u, edge[e].v, dist[edge[e].u], dist[edge[e].v]) ;break ;}}DBprintf ("v:%d, e:%d, edge[%d]: u:%d, v:%d, c:%d, n:%d\n", \v, e, e, edge[e].u, edge[e].v, edge[e].c, edge[e].n) ;//system ("pause 1>>nul 2>>nul") ;// 不能从 vertex[v] 所指向的边找到增广路if (e == -1)// no way from current edge's next vertex{// 路径队列中已经没有边了if (tail == 0)// no edges in queuebreak ;// 既然 vertex[v] 所指向的边已经无路可通了// 那么就应该把该边的目的顶点从层次图中删除// 一开始写成了 dist[edge[q[--tail]].u] = -1// 结果一直死循环……本程序所有的注释代码，都是为此错误服务的……dist[edge[q[--tail]].v] = -1 ;// 增广路径退一条边，回到 vertex[v] 所在边的前一个顶点v = edge[q[tail]].u ;// backward to previous vertexDBprintf ("e == -1 ----- v:%d, tail:%d\n", v, tail) ;}else// put the edge in queue{// 发现一条边可用，于是加入到增广路径队列中q[tail++] = e ;// 将新边的目的顶点设为增广路径的先头顶点v = edge[e].v ;}DBputs ("") ;}}return ans ;}int makegraph (const int lim){int i, j, low ;for (low = 1 ; low <= b - (lim - 1) ; ++low){init();for (i = 1 ; i <= n ; ++i){insert (s, i, 1) ;for (j = low ; j <= low + (lim-1) ; ++j)insert (i, barn[i][j]+n, 1) ;}for (i = 1 ; i <= b ; ++i)insert (i+n, t, cap[i]) ;if (dinic(s, t) == n)return true ;}return false ;}int main(){int i, j ;int ans, low, hig, mid ;while (scanf("%d%d", &n, &b) != EOF){for (i = 1 ; i <= n ; ++i){for (j = 1 ; j <= b ; ++j){scanf ("%d", &barn[i][j]) ;}}for (i = 1 ; i <= b ; ++i)scanf ("%d", &cap[i]) ;s = 0 ;t = n+b+1 ;low = 1 ;hig = b ;ans = -1 ;while (low <= hig){mid = (low + hig) / 2 ;if (makegraph (mid)){ans = mid ;hig = mid - 1 ;}elselow = mid + 1 ;}printf ("%d\n", ans) ;}return 0 ;}