[최대 흐름+dinic+2 분 매 거 진]북 대 poj 3189 Steady Cow 할당

/* 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:
9802586	panyanyany
3189
Accepted	948K	329MS	C++
4870B	2012-02-13 21:00:17

Test 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 ;
};

int		n, b, eCnt, s, t ;
int		dist[MAXN], q[MAXN], vertex[MAXN], barn[MAXN][22], cap[22] ;
EDGE	edge[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)
		{
DB			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 ;
DB				printf ("end --- v:%d ebreak:%d, ans:%d
", 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
", 
//						edge[e].u, edge[e].v, dist[edge[e].u], dist[edge[e].v]) ;
					break ;
				}
			}
DB			printf ("v:%d, e:%d, edge[%d]: u:%d, v:%d, c:%d, n:%d
", \
				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
DB				printf ("e == -1 ----- v:%d, tail:%d
", v, tail) ;
			}
			else			// put the edge in queue
			{
				//        ，            
				q[tail++] = e ;
				//                    
				v = edge[e].v ;
			}
DB			puts ("") ;
		}
	}
	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 ;
			}
			else
				low = mid + 1 ;
		}
		printf ("%d
", ans) ;
	}
	return 0 ;
}