挑战图灵奖

以防你产生误解：如果有人认为这个文章的内容是真的从而导致一些后果，作者概不负责。

P=NP 问题是一个著名的问题，如果你解决了这个问题，那么你就可以拿到图灵奖。

接下来，我要对这个问题发起冲锋。

一些显然的转化是我们只要在多项式时间复杂度内做出来一道 NPC 问题就行了，这里我选择了最大割问题，也即切割最多的边使得一张图恰好被二分。

我们这里有两个做法。

第一个做法，考虑被二分意味着什么，意味着将无向边看成两条有向边后，缩点之后有两个点。

那么我们考虑将原图的无向边视作两条有向边然后缩点。如果缩点之后超过两个点，你显然不能通过切割将其变成两个点，所以不可行。

如果有两个点，那么怎么切边都符合要求了，所以答案是 $m$。

如果有一个点，那么肯定我们是先要切掉所有边，因为造成不了任何影响，发现这时候只有一个点没有两个，我们考虑在这个点中间切一刀就好了，答案是 $m+1$。

缩点使用 Kosaraju 和 Tarjan 都跑的很快，但是我测试了一下没有通过样例，也许是我写错了。

第二个做法，我们先别管最大割是什么，最大割，故名思意，和最小割是对应的。考虑令所有边边权为 $-1$ 之后跑最小割，最小割等于最大流，于是转化成最大流。

最大流使用 EK、Dinic、ISAP、HLPP 都跑的很快，但是我测试了一下还是没有通过样例，也许是我又写错了，但是我对自己的代码水平极为自信，所以应该是样例错了。