题目描述
给定一个无向图 G = (V,E),设 V 包含 U,V 是G 的顶点集。对任意(u,v)∈E,若有 u∈U 且v ∈ V – U,就称 (u,v) 为关于顶点集 U 的一条割边。顶点集U的所有割边构成图 G 的一个割。G 的最大割是指 G 中所含边数最多的割。
对于给定的无向图G,设计一个优先队列式分支限界法,计算G的最大割。
输入
输入数据的第1 行有2 个正整数n 和m(n<25,m<200),表示给定的图G 有n 个顶点和m条边,顶点编号为1,2,…,n。接下来的m行中,每行有2 个正整数u,v,表示图G 的一条边(u,v)。
输出
将计算出的最大割的边数和顶点集U输出。第1 行是最大割的边数;第2行是表示顶点集U的向量,xi ,1≤i≤n , xi =0表示顶点i 不在顶点集U中, xi =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
参考代码
暂无
解析
暂无