我问了一下最小费用最大流量几个星期前。 Kraskevich的回答是辉煌，解决了我的问题。我实现了它和正常工作（仅适用于法国，抱歉）。 Additionaly，该算法可以处理的assignement的我的（我的> 1）项目，以每个学生。

I asked about the minimum cost maximum flow several weeks ago. Kraskevich's answer was brilliant and solved my problem. I've implemented it and it works fine (available only in French, sorry). Additionaly, the algorithm can handle the assignement of i (i > 1) projects to each student.

现在我想的东西比较困难。我想在选择添加约束。在这种情况下一个人想影响的我的（我的> 1）项目，以每一个学生，我希望能够指定哪些项目是兼容的（对方）。

Now I'm trying something more difficult. I'd like to add constraints on choices. In the case one wants to affect i (i > 1) projects to each student, I'd like to be able to specify which projects are compatible (each other).

在这种情况下有些项目是不兼容的，我想该算法返回全局最优，即影响的我的项目，以每个学生最大限度地发挥全球幸福和 repecting相容约束。

In the case some projects are not compatible, I'd like the algorithm to return the global optimum, i.e. affect i projects to each student maximizing global happiness and repecting compatibility constraints.

链接的我的（在每一个步骤和检查约束）倍，原来的方法也无济于事，因为它只会返回一个局部最优。

Chaining i times the original method (and checking constraints at each step) will not help, as it would only return a local optimum.

有关正确的图中的任何想法，一起工作？

Any idea about the correct graph to work with ?

推荐答案

不幸的是，它不是在多项式时间（除非 P = NP 或有额外的限制）

Unfortunately, it is not solvable in polynomial time(unless P = NP or there are additional constraints).

下面是从（其已知是NP完全）的最大独立集问题的多项式时间减少到这一个：

Here is a polynomial time reduction from the maximum independent set problem(which is known to be NP-complete) to this one:

给定图