2723.cpp

ACM北京赛区比赛的试题源码,在PKU在线评测可以通过.

#include <iostream.h>
#include <string.h>
#include <vector>
using namespace std;

vector<int> a[4096]; // (i,0) is i;(i,1) is i+2*N; i ranges from 0 to 2*N-1
vector<int> ca[4096];
int door[2048][2];
int key[1024][2];
int N,M;
char v[4096];
int ord[4096];
int t;
int r[4096];

void CreateMap(int D)
{
	int i;
	for(i=0;i<4*N;i++) a[i].clear();
	for(i=0;i<4*N;i++) ca[i].clear(); //bug 1,forget to clear
	for(i=0;i<N;i++) 
	{
		a[key[i][0]+2*N].push_back(key[i][1]); // (i,1) -> (j,0)
		a[key[i][1]+2*N].push_back(key[i][0]); // (j,1) -> (i,0)
		ca[key[i][1]].push_back(key[i][0]+2*N);
		ca[key[i][0]].push_back(key[i][1]+2*N);
	}
	for(i=0;i<D;i++) 
	{
		a[door[i][0]].push_back(door[i][1]+2*N);
		a[door[i][1]].push_back(door[i][0]+2*N);
		ca[door[i][1]+2*N].push_back(door[i][0]);
		ca[door[i][0]+2*N].push_back(door[i][1]);
	}
}

void GetOrder(int i)
{

	v[i] = 1;
	int l = a[i].size();
	for(int j=0;j<l;j++) if (!v[a[i][j]])
	{
		GetOrder(a[i][j]);
	}
	ord[t++] = i;
}

void Color(int i)
{
	v[i] = 1;
	int l = ca[i].size();
	for(int j=0;j<l;j++) if (!v[ca[i][j]])
	{
		Color(ca[i][j]);
	}
	r[i] = t;
}

int Reach(int D)
{
	if (D == 0) return 1;
	if (D == M+1) return 0;
	CreateMap(D);
	memset(v,0,sizeof v);
	t = 0;
	for(int i=0;i<4*N;i++) if (!v[i]) GetOrder(i); //bug 2 ,i<2*N
	memset(v,0,sizeof v);
	t = 0;
	for(i=4*N-1;i>=0;i--) if (!v[ord[i]]) //bug 3 i=2*N-1
	{
		Color(ord[i]);
		t++;
	}
	i = 0;
	for(;i<2*N;i++) if (r[i] == r[i+2*N]) return 0;
	return 1;
}

int main()
{
	int i;
	int l,right,m;
	
	cin>>N>>M;
	while (N)
	{
		for(i=0;i<N;i++) cin>>key[i][0]>>key[i][1];
		for(i=0;i<M;i++) cin>>door[i][0]>>door[i][1];
		l = 0;
		right = M+1;
		while (l<right-1)
		{
			m = (l+right)/2;
			if (Reach(m)) 
			{
				l = m;
			} else right = m;
		}
		cout<<l<<endl;
		cin>>N>>M;
	}
	return 0;
}