【最大流+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: 
9763175	panyanyany
1698
Accepted	404K	16MS	C++
4085B	2012-02-01 19:22:35

Test 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 MAXN	401
#define MAXE	16000

struct EDGE {
	int u, v, c, n ;
};

int		n, m, eCnt ;
int		map[MAXN][MAXN], dist[MAXN], vertex[MAXN], q[MAXN] ;

EDGE	edge[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 queue
					break ;
				// 既然 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 days
				for (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 destination
			des = 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:
9749311
panyanyany
1698
Accepted
804K
860MS
C++
2637B
2012-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:
9748843
panyanyany
1698
Accepted
1892K
266MS
C++
1798B
2012-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 ;
}