> задача Е: здесь вроде как надо ориент. граф так чтобы не было циклов, только вот как это делается???
> заранее спасибо.
More exactly: we should receive such an oriented graph in which the maximal chain is minimized.
How to do it? We are given non-oriented graph consists of at most N=15 vertices (resources) and 100 edges (processes).
Consider the following dynamic programming. The state is fixed set of vertices (also called "mask").
The main idea is to choose some subset S of vertices form the mask M and call it "upper layer", then work with mask M \ S.
Of course, subgraph S must be "correct" in sence that it does not contain edges at all, and the value
d[M] = d[M\S] + 1
should be minimized.
After that all edges from the "upper" layers will be directed to the "lower" layers. Thus we will obtain the requested graph.
The check of "correctness" for all subsets should be preprocessed (it is easy to do in O(2^N * <edges>)).
The main solution has O(3^N) complexity... of course, if you know some special technique 