1723: 无向图的最大割问题
内存限制：128 MB
时间限制：10.000 S
评测方式：文本比较
命题人：
提交：3
解决：1
题目描述
给定一个无向图 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，表示给定的图 G 有 n 个顶点和 m 条边，顶点编号为 1，2，…，n。接下来的 m 行中，每行有 2 个正整数 u, v，表示图G 的一条边(u,v)。
输出
输出的第 1 行是最大割的边数；
输出的第 2 行是表示顶点集 U 的向量，xi(1 ≤ i ≤ n < 25)，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