无向图的最大割问题

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description



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

Input

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

Output

将计算出的最大割的边数和顶点集U输出。第1 行是最大割的边数;第2行是表示顶点集U的向量,xi ,1≤i≤n , xi =0表示顶点i 不在顶点集U中, xi =1 表示顶点i在顶点集U中。

Sample Input

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

Sample Output

12
1 1 1 0 1 0 0

Hint

请按照题目要求用优先队列式分支限界法解题。

Source