pku1370.cpp

这是ACM 方面的资料 是PKU的 北京大学的出来的

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef struct Line
{
	int cnt;
	int pos[50];
}Line;

typedef struct Driver
{
	int s_pos;
	int line;
}Driver;

Line line[20];
int ds[31];
Driver d[31];
int N, D, S;
int path[31][31];

void set(int t, int di)
{
	int l = d[di].line;
	ds[di] = line[l].pos[(d[di].s_pos + t) % line[l].cnt];
}

int Solve()
{
	char buffer[1000], *p;
	int i, j, si, di, t;
	memset(line, 0, sizeof(line));
	memset(d, 0, sizeof(d));
	memset(ds, 0, sizeof(ds));
	getchar();
	for (i = 0; i < N; i++)
	{
		gets(buffer);
		p = buffer;
		do
		{
			while (*p == ' ')
				p++;
			si = atoi(p);
			while (*p != ' ' && *p)
				p++;
			line[i].pos[line[i].cnt++] = si;
		}while (*p);
		gets(buffer);
		p = buffer;
		do
		{
			while (*p == ' ')
				p++;
			si = atoi(p);
			while (*p != ' ' && *p)
				p++;
			p++;
			di = atoi(p);
			while (*p != ' ' && *p)
				p++;
			d[di].line = i;
			for (j = 0; j < line[i].cnt; j++)
			{
				if (line[i].pos[j] == si)
				{
					d[di].s_pos = j;
					break;
				}
			}
		}while (*p);
	}
	memset(path, 0, sizeof(path));
	for (t = 0; t <= 2500; t++)
	{
		for (i = 1; i <= D; i++)
			set(t, i);
		for (i = 1; i <= D; i++)
		{
			for (j = 1; j <= D; j++)
			{
				if (ds[i] == ds[j])
					path[i][j] = 1;
			}
		}
	}
	for (t = 1; t <= D; t++)
	{
		for (i = 1; i <= D; i++)
		{
			for (j = 1; j <= D; j++)
			{
				if (path[i][t] && path[t][j])
					path[i][j] = 1;
			}
		}
	}
	for (i = 1; i <= D; i++)
	{
		for (j = 1; j <= D; j++)
			if (!path[i][j])
				return 0;
	}
	return 1;
}

int main()
{
	while (EOF != scanf("%d %d %d", &N, &D, &S) && (N || D || S))
		printf("%s\n", Solve() ? "Yes" : "No");
}