Preparing NOJ

无向图的最大割问题

1000ms 65536K

Description:

 给定一个无向图G=(VE),设UÍVG 的顶点集。对任意(uv)E,若有uU vV-U,就称(uv)为关于顶点集U的一条割边。顶点集U的所有割边构成图G 的一个割。G 的最大割是指G 中所含边数最多的割。对于给定的无向图G,设计一个优先队列式分支限界法,计算G的最大割。

Input:

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

Output:

 程序运行结束时,将计算出的最大割的边数和顶点集U输出。第1 行是最大割的边数;文件的第2 行是表示顶点集U的向量,xi,1 £ i £ n   x i =0 表示顶点i不在顶点集U, x i =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

Note:

 

本题由旧版NOJ导入,来源:算法设计与实验题解

Info

NOJ

Provider NOJ

Code NOJ1316

Tags

Submitted 54

Passed 0

AC Rate 0%

Date 04/20/2019 10:03:10

Related

Nothing Yet