3618: 项链(第四轮04)
题目描述
某天坐在电脑前打比赛的你被 Monster 抓到了一颗星球，并被强迫给它打工。 这颗星球上一共有n个城市（编号1 − n），通过 m 条单向道路连接（`可能存在 重边,但保证不存在环`），在每个城市都有一颗宝石，第 i 个城市宝石的价值为 wi 。一条项链的价值定义为某条路径上所有的宝石价值和，也即如果存在一条
路径u → v，你可以利打造一条价值为∑u(v) wi 的项链。项链的价值可以为负，你
也可以打造不含宝石的项链（价值为 0）。
你可以选择从任意一个城市开始，并沿着道路走下去直到尽头（没有边为止）， 每到一个城市你都会获得一颗宝石（包括初始位置，相同城市无法重复获得）。 最终你可能会有很多条项链，但你只需要交给 Monster 价值最高的那条，且 Monster 要求该项链的价值在所有可能得到的项链中价值最大。
作为报酬， Monster 允许你在剩余的项链中最多选择一条作为回报，你想要知道 你和 Monster 的项链价值各是多少。
输入
共m + 2行：第一行两个整数n, m，表示有 n个城市,m条道路。
第二行有n个整数，第i个整数数wi 表示第i个路口中宝石的价值。 接下来m行每行两个整数u, v ,表示有一条u到v的单向路。
输出
共一行：两个整数ans1， ans2，分别表示 Monster 和你项链的价值（中间用空 格隔开）。
样例输入 复制
4 3
4 3 -2 1
1 2
2 3
3 4样例输出 复制
7 1提示
【样例 1 输入】
4 3
4 3 -2 1
1 2
2 3
3 4
【样例 1 输出】
7 1
【样例 1 说明】
第一组样例，最优路径为1 → 2 → 3 → 4,你交出由1， 2号点宝石组成的项链（价 值 7），得到 4 号点宝石组成的项链。
【样例 2 输入】
6 8
-1 2 3 4 -5 6
1 4
4 5
4 6
5 6
5 2
2 3
5 3
3 6
【样例 2 输出】
11 4
【样例 2 说明】
第二组样例，最优路径为4 → 5 → 2 → 3 → 6,交出项链2,3,6(价值 11)。收获 4。
【数据范围】
对于 10%的数据， n = 105，图呈现链状。 对于另外 20%的数据， n, m ≤ 200;
对于 100%的数据， 1 ≤ n, m ≤ 10^5 , ∣ wi ∣≤ 10^9 。