// 724K 32MS

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;

const int N = 30 + 5;
const int M = N * N;
int n, m;
char name[N][100];
struct Edge { int from, to; double rate; } edge[M];
int first[N], next[M], tot;
int queue[N], cnt[N], l, r;
double gain[N];
bool pd[N];

inline void addEdge(int from, int to, double rate)
{
	Edge &e = edge[++tot];
	e.from = from, e.to = to, e.rate = rate;
	next[tot] = first[from], first[from] = tot;
}

inline bool relax(int e)
{
	double tmp = gain[edge[e].from] * edge[e].rate;
	if (tmp > gain[edge[e].to]) { gain[edge[e].to] = tmp; return true; }
	return false;
}

bool spfa()
{
	l = r = 0;
	memset(pd, false, sizeof(pd));
	memset(cnt, 0, sizeof(cnt));
	memset(gain, 0, sizeof(gain)); gain[1] = 1.0;
	queue[r++] = 1; pd[1] = true; cnt[1]++;
	while (l != r)
	{
		int p = queue[l];
		l = (l + 1) % N; pd[p] = false;
		for (int e = first[p]; e; e = next[e]) if (relax(e))
		{
			int v = edge[e].to;
			if (!pd[v]) 
				queue[r] = v, r = (r + 1) % N, pd[v] = true, cnt[v]++;
			if (cnt[v] > n) return true;
		}
	}
	return false;
}

int main()
{
	char name1[100], name2[100];
	int kase = 0;
	while (scanf("%d\n", &n) == 1 && n)
	{
		tot = 0;
		memset(first, 0, sizeof(first));
		memset(next, 0, sizeof(next));		
		for (int i = 1; i <= n; i++) gets(name[i]);
		
		scanf("%d", &m);
		for (int i = 1; i <= m; i++)
		{
			double rate; int v1, v2;
			scanf("%s %lf %s", name1, &rate, name2);
			for (int j = 1; j <= n; j++) if (strcmp(name1, name[j]) == 0) { v1 = j; break; }
			for (int j = 1; j <= n; j++) if (strcmp(name2, name[j]) == 0) { v2 = j; break; }
			addEdge(v1, v2, rate);
		}
		printf("Case %d: ", ++kase);
		spfa() ? printf("Yes\n") : printf("No\n");
	}
	return 0;
}

• 好帅的代码！ (6) imcaffrey 2017-08-17 09:55:33