1895.cpp

来自「哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码」· C++ 代码 · 共 67 行

/* This Code is Submitted by wywcgs for Problem 1895 on 2006-09-17 at 20:12:00 */
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const int N = 1024;
const int INF = 1 << 28;

vector<int> g[N];
int n, m, lmth[N], rmth[N][N], rn[N], check[N];

bool organize(int);
bool dfs(int, int, int);

int main()
{
	while(scanf("%d %d", &n, &m) != EOF && n != 0) {
		for(int i = 0; i < n; i++) {
			scanf("%*s"); g[i].clear();
			while(true) {
				char c;
				while((c = getchar()) == ' ');
				if(c == '\n') break;
				else ungetc(c, stdin);
				int a; scanf("%d", &a);
				g[i].push_back(a);
			}
		}
		int l = 0, h = n;
		while(l != h) {
			int mid = (l+h)/2;
			if(organize(mid)) h = mid;
			else l = mid+1;
		}
		printf("%d\n", h);
	}
	
	return 0;
}

bool organize(int lmt)
{
	memset(check, -1, sizeof(check));
	memset(rn, 0, sizeof(rn)); memset(lmth, -1, sizeof(lmth));
	for(int i = 0; i < n; i++)
		if(!dfs(i, lmt, i)) return false;
	return true;
}
bool dfs(int p, int lmt, int k)
{
	for(int i = g[p].size()-1; i >= 0; i--) {
		int no = g[p][i], t = lmth[p];
		if(check[no] == k) continue;
		check[no] = k; lmth[p] = no;
		if(rn[no] < lmt) { rmth[no][rn[no]++] = p; return true; }
		for(int j = 0; j < lmt; j++) {
			int lo = rmth[no][j];
			rmth[no][j] = p;
			if(dfs(lo, lmt, k)) return true;
			rmth[no][j] = lo;
		}
		lmth[p] = t;
	}
	return false;
}