3260518_tle.cc

北大大牛代码 1240道题的原代码 超级权威

#include <iostream>
#include <string>
#include <algorithm>
#define maxn 10000

using namespace std;

struct point
{
	string x, y;

	bool operator < (const point &that)	const
	{
		if(that.x.compare(x)==0)
			return that.y.compare(y) > 0;
		else
			return that.x.compare(x) > 0;
	}
	bool operator == (const point &that)	const
	{
		return that.x.compare(x)==0&&that.y.compare(y)==0;
	}
};

struct segment
{
	point st, ed;
};

int k, n, f[maxn], d[maxn];
point p[maxn];
segment s[maxn];

int find(int p)
{
	if(f[p]!=p)
		return f[p]=find(f[p]);
	else
		return f[p];
}

string modify(string str)
{
	int i, len;

	len = str.length();
	for(i = 0; i < len-1; i++)
	{
		if(str.at(i)!='0')
		{
			break;
		}
	}
	return str.substr(i);
}

int getId(point t)
{
	int min, max, mid;

	min = 0;max = n-1;
	while(min <= max)
	{
		mid = (min+max)>>1;
		if(t==p[mid])
			return mid;
		if(t<p[mid])
			max = mid-1;
		else
			min = mid+1;
	}
//	while(1);
	return -1;
}

int main()
{
	int i, m;
	string s1, s2, s3, s4;

	scanf("%d",&k);
	for(i = 0; i < k; i++)
	{
		cin >> s1 >> s2 >> s3 >> s4;
		p[i*2].x = modify(s1);
		p[i*2].y = modify(s2);
		p[i*2+1].x = modify(s3);
		p[i*2+1].y = modify(s4);
		s[i].st = p[i*2];
		s[i].ed = p[i*2+1];
	}
	//char tmp[300];
	//if(scanf("%s",tmp)==1)
	//	while(1);
	sort(p,p+2*k);
	for(i = 0, n = 0; i < 2*k; i++,n++)
	{
		p[n] = p[i];
		m = i;
		while(m<2*k&&p[m]==p[n])
			m++;
		i = m-1;
	}
	for(i = 0; i < n; i++)
	{
		f[i] = i;
		d[i] = 0;
	}
	for(i = 0; i < k; i++)
	{
		int ii, jj;

		ii = getId(s[i].st);
		jj = getId(s[i].ed);
		d[ii]++;d[jj]++;
		
		int s1, s2;

		s1 = f[ii];
		s2 = f[jj];
		for(int mm = 0; mm < n; mm++)
		{
			if(f[mm]==s1)
				f[mm] = s2;
		}
	/*	s1 = find(ii);
		s2 = find(jj);
		f[s1] = s2;*/
	}
	for(i = 0; i < n; i++)
	{
		if(d[i]%2==1||f[i]!=f[0])
		{
			puts("0");
			return 0;
		}
	}
	puts("1");
	return 0;
}