3260532_ac_266ms_6472k.cc

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

#include <string>
#include <algorithm>
#define maxn 6000
#define INIT (node *)malloc(sizeof(node));
using namespace std;

struct point
{
	char x[251], y[251];

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

struct segment
{
	point st, ed;
};

struct node
{
	int v;
	node *next;
};
struct vnode
{
	node *head;
};

vnode map[maxn];


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

void dfs(int v)
{
	node *s;

	visited[v] = -1;
	cnt++;
	s = map[v].head;
	while(s)
	{
		if(visited[s->v]!=-1)
		{
			dfs(s->v);
		}
		s = s->next;
	}
}

void modify(char str[])
{
	int i, len;

	len = strlen(str);
	for(i = 0; i < len-1; i++)
	{
		if(str[i]!='0')
		{
			break;
		}
	}
	strcpy(str,&str[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;
	}
	return -1;
}

int main()
{
	int i, m;

	scanf("%d",&k);
	for(i = 0; i < k; i++)
	{
		scanf("%s%s%s%s",p[i*2].x,p[i*2].y,p[i*2+1].x,p[i*2+1].y);
		modify(p[i*2].x);
		modify(p[i*2].y);
		modify(p[i*2+1].x);
		modify(p[i*2+1].y);
		s[i].st = p[i*2];
		s[i].ed = p[i*2+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++)
	{
		d[i] = 0;
		map[i].head = NULL;
	}
	for(i = 0; i < k; i++)
	{
		int ii, jj;

		ii = getId(s[i].st);
		jj = getId(s[i].ed);
		d[ii]++;d[jj]++;
		
		node *s;
		s = INIT;
		s->v = jj;
		s->next = map[ii].head;
		map[ii].head = s;
		s = INIT;
		s->v = ii;
		s->next = map[jj].head;
		map[jj].head = s;
	}
	cnt = 0;
	dfs(0);
	if(cnt!=n)
	{
		puts("0");
		return 0;
	}
	for(i = 0; i < n; i++)
	{
		if(d[i]%2==1)
		{
			puts("0");
			return 0;
		}
	}
	puts("1");
	return 0;
}