【最大流+Dinic+Edmonds_Karp+二分匹配】北大 poj 1698 Alice's Chance
Dinic 算法
?
/* THE PROGRAM IS MADE BY PYY *//*----------------------------------------// Copyright (c) 2011 panyanyany All rights reserved. URL : http://poj.org/problem?id=1698 Name : 1698 Alice's Chance Date : Wednesday, February 01, 2012 Time Stage : many hours Result: 9763175panyanyany1698Accepted404K16MSC++4085B2012-02-01 19:22:35Test Data :Review :传说是最快的最大流算法，果然名不虚传啊！如果看不懂的，建议先看看这篇文章：王欣上《浅谈基于分层思想的网络流算法》.doc然后，一开始看的大牛的解题报告：http://www.cnblogs.com/littlex/archive/2011/08/17/2142766.html没有注释很伤心啊，于是我的这个注了很多释，希望以后的同学能看明白～～//----------------------------------------*/#include <cstdio>#include <CSTRING>using namespace std ;#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 MAXN401#define MAXE16000struct EDGE {int u, v, c, n ;};intn, m, eCnt ;intmap[MAXN][MAXN], dist[MAXN], vertex[MAXN], q[MAXN] ;EDGEedge[MAXE] ;void init (){eCnt = 0 ;MEM (vertex, -1) ;}void insert (int u, int v, 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 ;// 一开始这里是赋值的 c ，结果很悲剧～～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){//printf("--- 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 ;//printf ("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 ;}}//printf ("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 vertex//printf ("e == -1 ----- v:%d, tail:%d\n", v, tail) ;}else// put the edge in queue{// 发现一条边可用，于是加入到增广路径队列中q[tail++] = e ;// 将新边的目的顶点设为增广路径的先头顶点v = edge[e].v ;}//puts ("") ;}}return ans ;}int main (){int i, j, k ;int tcase, D, W, days[8], maxW, des, sum ;while (scanf ("%d", &tcase) != EOF){while (tcase--){init () ;maxW = sum = 0 ;scanf ("%d", &n) ;for (i = 1 ; i <= n ; ++i){for (j = 1 ; j <= 7 ; ++j)scanf ("%d", &days[j]) ;scanf ("%d%d", &D, &W) ;maxW = max(maxW, W) ;sum += D ;insert (0, i, D) ;// edges for each films// edges from film to daysfor (j = 0 ; j < W ; ++j)for (k = 1 ; k <= 7 ; ++k){if (days[k]){insert(i, j*7+k+n, 1) ;}}}// edges from every day to destinationdes = maxW*7+n+1 ;for (i = n + 1 ; i < des ; ++i)insert(i, des, 1) ;int ans = dinic (0, des) ;puts (ans == sum ? "Yes" : "No") ;}}return 0 ;}?Edmonds_Karp 解法/* THE PROGRAM IS MADE BY PYY *//*----------------------------------------// Copyright (c) 2011 panyanyany All rights reserved. URL : http://poj.org/problem?id=1698 Name : 1698 Alice's Chance Date : Saturday, January 28, 2012 Time Stage : Many hours Result:9749311panyanyany1698Accepted804K860MSC++2637B2012-01-28 13:52:50 Test Data : Review :一开始 end 是400，cnt是401，直接TLE。//----------------------------------------*/ #include <cstdio>#include <CSTRING> #include <queue>#include <algorithm>#include <vector> using namespace std ; #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 401 #define D 8#define W 9 int n, m ;int flow[MAXN], map[MAXN][MAXN], pre[MAXN] ; int Mark_Point (int beg, int end, int cnt){ int i, t ; queue<int> q ; MEM (pre, -1) ; flow[beg] = INF ; pre[beg] = 0 ; q.push (beg) ; while (!q.empty ()) { t = q.front () ; q.pop () ; if (t == end) break ; for (i = 0 ; i < cnt ; ++i) { if (pre[i] == -1 && map[t][i]) {// printf ("%d-->%d ", t, i) ; pre[i] = t ; flow[i] = min (flow[t], map[t][i]) ; q.push (i) ; } } } if (pre[end] == -1) return -1 ; return flow[end] ;} int Edmonds_Karp (int beg, int end, int cnt){ int incr, step, curr, prev ; incr = 0 ; while ((step = Mark_Point (beg, end, cnt)) != -1) { incr += step ; curr = end ; while (curr != beg) { prev = pre[curr] ; map[prev][curr] -= step ; map[curr][prev] += step ; curr = prev ; } } return incr ;} int main (){ int i, j, k ; int tcase, sum, maxday ; int w[10] ; while (scanf ("%d", &tcase) != EOF) { while (tcase--) { scanf ("%d", &n) ; MEM (map, 0) ; sum = maxday = 0 ; for (i = 1 ; i <= n ; ++i) {// MEM (w, 0) ; for (j = 1 ; j <= 9 ; ++j) scanf ("%d", &w[j]) ; sum += w[D] ; map[0][i] = w[D] ; maxday = max (maxday, w[W]) ; for (j = 0 ; j < w[W] ; ++j) { for (k = 1 ; k <= 7 ; ++k) { map[i][k+j*7+n] = w[k] ;// printf ("%d-->%d == %d , ", i, k+j*7+20, w[k]) ;// map[k+j*7+20][400] |= w[k] ;// maxd = max (maxd, k+j*7+20) ; } } } maxday *= 7 ; for (i = n + 1 ; i <= maxday + n ; ++i) map[i][maxday+1+n] = 1 ; // printf ("\n----%d \n", Edmonds_Karp (0, maxday+1+n, maxday+2+n)) ; if (Edmonds_Karp (0, maxday+1+n, maxday+2+n) == sum) puts ("Yes") ; else puts ("No") ; } } return 0 ;}?二分图解法
?
/* THE PROGRAM IS MADE BY PYY *//*----------------------------------------// Copyright (c) 2011 panyanyany All rights reserved. URL : http://poj.org/problem?id=1698 Name : 1698 Alice's Chance Date : Saturday, January 28, 2012 Time Stage : Many hours Result:9748843panyanyany1698Accepted1892K266MSC++1798B2012-01-28 10:43:31 Test Data : Review :网络流 dinic 算法还不会，先用二分图来做……参考了一下解题报告：http://blog.csdn.net/zxy_snow/article/details/6242668//----------------------------------------*/ #include <cstdio>#include <CSTRING> #include <queue>#include <algorithm>#include <vector> using namespace std ; #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 401 bool cover[MAXN] ; int n, m, film_day ;int map[1100][MAXN], w[10], link[MAXN] ; int find (int cur){ int i ; for (i = 1 ; i <= m ; ++i) { if (cover[i] == false && map[cur][i]) { cover[i] = true ; if (!link[i] || find (link[i])) { link[i] = cur ; return true ; } } } return false ;} int main (){ int i, j, k, l ; int tcase, sum ; scanf ("%d", &tcase) ; while (tcase--) { MEM (map, 0) ; m = 0 ; scanf ("%d", &n) ; film_day = 0 ; for (i = 1 ; i <= n ; ++i) { for (j = 1 ; j <= 9 ; ++j) { scanf ("%d", &w[j]) ; } for (l = film_day + 1 ; l <= film_day + w[8] ; ++l) { for (j = 0 ; j < w[9] ; ++j) { for (k = 1 ; k <= 7 ; ++k) { map[l][k+j*7] = w[k] ; m = max (m, k+j*7) ; } } } film_day += w[8] ; } sum = 0 ; MEM (link, 0) ; for (i = 1 ; i <= film_day ; ++i) { MEM (cover, 0) ; sum += find (i) ; } printf ("%s\n", sum == film_day ? "Yes" : "No") ; } return 0 ;}?