数据结构作业要跪啊。。。

(心照不宣)

不会的发上来大家一起讨论..

电脑没电了，手打一个…………第一题：一堆ppt胶片摞在一起有重叠，每张上面教授都贴了一个播放序号，从1到n，需要你进行整理，你对胶片进行了编号，如果一个序号仅落在一张胶片内，那么可以知道该序号对应的编号并将其抽出，如此反复即可完成整理。输入：第一行是一个整数n，以下n行每行四个实数代表编号1到n的胶片的范围：x1 x2 y1 y2，下面n行给出了序号的坐标：x y。输出n行，按编号顺序输出对应的序号。提示说用拓扑排序……但是我感觉没有办法定义一个序关系啊

n张胶片和n个序号构成无向图G, 第i个序号在第j个胶片上 <=> 序号i和胶片j连一条边。每次取度=1的序号输出连接胶片的编号， 把这个胶片所有临边删除， 直到G为空。

诶，有了u哥的提示却无时间来码代码。。还有21天，还有四个题。。。

第二题又来了···
这次是旅行商问题的变种：
shrek骑着小驴donkey到N个村庄去卖货，这N个村庄通过n-1条路径连接。
shrek早上从家出发一路不走回头路，即每个村庄和每条路径都只能通过一次。
当他到达一个村庄后卖一会货再任选一个可达村庄前进，若已无路可走就停止，次日重新开始。
问题：donkey的胃口比较大，每次赶路都要吃若干干草，shrek想知道需要准备一个多大的背包，才能保证在有路可走时不会因为donkey停下。
输入：
第一行：N，表示村庄总数1<=N<=100,000
后面N-1行每行三个整数，分别是路径连接的两个村庄编号，和走这段路所需草料
输出：背包最小体积。
解的范围[1,2^31)
时间限制：2s...因此复杂度要低于n^2
也就是要找最长路径吧····我怎么记得TSP问题是NPC问题呢···

学长们好啊，我也要跪了