luoguP2747 [USACO5.4]周游加拿大Canada Tour

被STL卡半天

周游加拿大

1993IOI的题（感觉当年的题好水啊，现在越来越卷了），疑似是dp的起源

dp比较简单没什么好说的，重点在处理字符串，注意一下问题：

1. map中不能直接拿char*作为key
2. string不能用scanf输入
3. 别搞妖魔鬼怪，就用cin+string+map挺好的

#include <bits/stdc++.h>
using namespace std;
const int  N = 100 + 5;
int n, m;
map<string, int> ha;
int mp[N][N], f[N][N], ans;
int main()
{
	scanf("%d%d", &n, &m);
	string u, v;
	for (int i = 1; i <= n; ++i)
		cin >> u, ha[u] = i;
	for (int i = 1; i <= m; ++i)
		cin >> u >> v, mp[ha[u]][ha[v]] = mp[ha[v]][ha[u]] = 1;
	memset(f, -1, sizeof f);
	f[1][1] = 1;
	for (int i = 1; i < n; ++i)
		for (int j = i + 1; j <= n; ++j)
			for (int k = 1; k < j; ++k)
				if (mp[j][k] && f[i][k])
					f[i][j] = f[j][i] = max(f[i][j], f[i][k] + 1);
	ans = 1;
	for (int i = 1; i <= n; ++i)
		if (mp[i][n])
			ans = max(f[i][n], ans);
	printf("%d\n", ans);
	return 0;
}