做这道题感觉异常激动，因为在下第一次接触拓扑排序啊= =，而且看了看解释，猛然发现此题可以用DP优化，然后一次A掉所有样例，整个人激动坏了，哇咔咔咔咔咔咔咔~ 咔咔~哎呀，笑岔了- -||
旅行商(TSP)
描述
Shrek是一个大山里的邮递员，每天负责给所在地区的n个村庄派发信件。但杯具的是，由于道路狭窄，年久失修，村庄间的道路都只能单向通过，甚至有些村庄无法从任意一个村庄到达。这样我们只能希望尽可能多的村庄可以收到投递的信件。
Shrek希望知道如何选定一个村庄A作为起点（我们将他空投到该村庄），依次经过尽可能多的村庄，路途中的每个村庄都经过仅一次，最终到达终点村庄B，完成整个送信过程。这个任务交给你来完成。
输入
第一行包括两个整数n，m，分别表示村庄的个数以及可以通行的道路的数目。
以下共m行，每行用两个整数v1和v2表示一条道路，两个整数分别为道路连接的村庄号，道路的方向为从v1至v2，n个村庄编号为[1, n]。
输出
输出一个数字，表示符合条件的最长道路经过的村庄数。
Input
4 3
1 4
2 4
4 3
Output
3
限制
1 ≤ n ≤ 1,000,000
0 ≤ m ≤ 1,000,000
输入保证道路之间没有形成环
时间：2 sec
空间：256 MB
提示
拓扑排序
手记部分：
刚开始做这道题的时候，我不知道有拓扑排序，一直在想结点10^6的图该怎么操作，所以第一个想法就是邻接表，用一个Vetor和一个数组模拟邻接表，之后考虑到在单向寻找最长路的时候应该怎样做优化。最开始的想法是深度优先搜索(DFS)，甚至考虑了广度优先搜索(BFS),但是无论怎样都需要O(n^2)的时间度，无疑要么考虑优化，要么改变算法，然后猛然间发现题目下面的提示-拓扑排序- -||，博主顿时觉得脑残了~
然后博主开始找拓扑排序相关资料，还好有本学长借我的一本图论书，看完概念后理解了AOV和AOE网络以及拓扑排序的基本概念，但对这道题我还是有点迷糊，因为直接排序无疑会破坏邻接表，后来才想到用数组存放拓扑排序后的下标，后来发现这个数组其实就是一种队列，这样就不会破坏编号顺序和邻接表。之后准备开始写主算法的时候原来考虑的是用DFS+优化，后来突然发现每座城市经拓扑排序后，有一种状态满足无后效性——从起始城市到此城市所经过的最大城市数。
有了这个想法之后就在拓扑排序的基础上(具体算法写在了拓扑排序函数内)，完成了DP算法。
因此这道题目，我的方法就是邻接表(图的保存和查找)+队列(保存拓扑排序)+DP(时间优化)+拓扑排序(完成AOV网络的结点排序)
以上为博主胡言乱语= =||，直接看懂代码比较容易懂。
//TshingHua OJ 旅行商(TSP)
//邻接表+DP+队列+拓扑排序
//Memory:66304KB Time:1101Ms(No.17)
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std; #define MAX 1000005
#define Max(x,y) ((x)>(y)?(x):(y)) int n, m; //村庄个数-道路数
int topology[MAX],lt; //拓扑数组-长度
int mark[MAX]; //入度标记
int maxCity = ; //答案 //从City通向的村庄
struct Node{
int num; //村庄编号
Node *next;
Node(){ next = NULL; }
Node(int x,Node *n) :num(x),next(n){}
}; struct City{
Node *nc; //next-city
int dp; //至此可通过的最大城市数
City(){ nc = NULL; dp = ; }
void insert(int nc);
}city[MAX]; void City::insert(int nc)
{
mark[nc]++; //直接后继城市入度+1
if (this->nc == NULL)
this->nc = new Node(nc,NULL);
else{
Node *node = new Node(nc,this->nc);
this->nc = node;
}
return;
} /*拓扑排序*/
void Topology()
{
for (int i = ; i <= n; i++)
if (!mark[i]) topology[++lt] = i; //入度为0的city
//Main Content
for (int i = ; topology[i];i++)
{
int cur = topology[i]; //该city-number
//遍历该city所有直接后继
for (Node *tmp = city[cur].nc; tmp != NULL; tmp = tmp->next)
{
//此处满足无后效性-DP
city[tmp->num].dp = Max(city[cur].dp + , city[tmp->num].dp);
maxCity = Max(city[tmp->num].dp, maxCity);
//处理后继
int num = tmp->num;
mark[num]--; //后继入度-1
if (!mark[num]) topology[++lt] = num; //若后继入度为0
}
}
} int main()
{
scanf("%d%d", &n, &m);
for (int i = ; i < m; i++)
{
int x, y; //x->y
scanf("%d%d", &x, &y);
city[x].insert(y);
}
/*拓扑排序*/
Topology();
printf("%d\n", maxCity); return ;
}
小墨 - - 原创