2077_AL082无向图的最大割问题

给定一个无向图G=(V，E)，设U V是G 的顶点集。对任意(u，v)∈E，若有u∈U 且v∈V-U，就称(u，v)为关于顶点集U的一条割边。顶点集U的所有割边构成图G 的一个割。G 的最大割是指G 中所含边数最多的割。

对于给定的无向图G，设计一个优先队列式分支限界法，计算G的最大割。

输入第一行有两个正整数n 和m，表示给定的图G 有n 个顶点和m条边，顶点编号为1，2，…，n。接下来的m行中，每行有两个正整数u,v，表示图G 的一条边(u,v)。

输出最大割的边数和顶点集U。第一行是最大割的边数；第二行是表示顶点集U的向量，x_i ，1 ≤ i ≤ n ， x_i=0表示顶点i不在顶点集U中，x_i=1 表示顶点i在顶点集U中。

7 18
1 4
1 5
1 6
1 7
2 3
2 4
2 5
2 6
2 7
3 4
3 5
3 6
3 7
4 5
4 6
5 6
5 7
6 7

12
1 1 1 0 1 0 0

要求：采用 优先队列式分支限界法