关于divide and couquer分治法的一道题和关于max flow的一道题
1. Divide and Conquer
两个向量x(x1,x2)和y(y1,y2),当x1<y1,x2<y2时可以定义x<y。现有两个向量的集合A={a1,a2,a3,...an},B={b1,b2,b3,...bn}。要求用O(nlogn)的时间求出两个向量中所有x<y的数量。
比如说A={(1,1),(2,2)} B={(0,3),(3,3)}。在这两个集合中，x<y的数量就是2，x1<y2,x2<y2。
2. Max Flow
1)G是一个每条边的容量(capacity)都是整数的一个net flow.
(a)证明对于G中的每条边e，以下两个描述是相同的
1.存在一个包含e的最小割。
2.在所有最大流中，e都是饱和的。f(e) = Ce
2)证明G中存在一个最大流f，能使得带正数的流的边集合是不循环的（不知道怎么翻，原文是Prove that there exists a maximum flow f in G, such that the set of edges carrying positive flow is acyclic.）也就是说，f拥有如下特征：在G中所有由e1,e2,e3...ek组成的directed cycle中，f(e1),f(e2),...f(ek)这k个数中至少有一个等于0.
我实在想不出好的解法，，求助了。。谢谢
[解决办法]
