问题 : 无向图的最大割问题

时间限制: 1 Sec 内存限制: 128 MB

题目描述
给定一个无向图G=(V,E)，设U包含于V是G的顶点集。对任意（u，v）∈E，若有u∈U且v∈V-U，就称（u，v）为关于顶点集U的一条割边。顶点集U的所有割边构成图G的一个割。G的最大割是指G中所含边数最多的割。对于给定的无向图G，设计一个优先队列式分支限界法，计算G的最大割。

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

输出
将计算的最大割的边数和顶点集U输出，第一行是边数，第二行是表示顶点集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

代码实现：

#include <bits/stdc++.h>
using namespace std;

const int MAX = 1000;
int G[MAX][MAX];
int bestx[MAX];
int w[MAX];     //顶点的权
int n, e; //电路板数，连接块数

class Node
{
public:
    int dep;  //当前层
    int cut;  //割边数量
    int e;    //剩余边的数量
    int *x;   //解向量

    Node(int d, int c, int ee)
    {
        x = new int[n+1];
        dep = d;
        cut = c;
        e = ee;
    }

    //割边数大的先出队列
    bool operator < (const Node &node) const
    {
        return cut < node.cut;
    }
};

priority_queue<Node> q;

//添加结点
void addNode(Node enode, bool isLeft)
{
    Node now(enode.dep+1, enode.cut, enode.e);
    copy(enode.x, enode.x+n+1, now.x);
    if(isLeft)
    {
        now.x[now.dep] = 1;
        for(int j=1; j<=n; j++)
            if(G[now.dep][j])
                if(now.x[j] == 0) //如果当前顶点在割集中，但边的另一个顶点不在割集
                {
                    now.cut++;  //割边的数量增加
                    now.e--;    //剩余边的数量减少
                }
                else
                    now.cut--;
    }
    else
    {
        now.x[now.dep] = 0;
        now.e--;
    }
    q.push(now);
}

int search()
{
    Node enode(0, 0, e);
    for(int j=1; j<=n; j++)
        enode.x[j] = 0;
    int best = 0;
    while(true)
    {
        if(enode.dep>n)
        {
            if(enode.cut > best)
            {
                best = enode.cut;
                copy(enode.x, enode.x+n+1, bestx);
                break;
            }
        }
        else
        {

            addNode(enode, true);
            if(enode.cut + enode.e > best)
                addNode(enode, false);
        }
        if(q.empty())
            break;
        else
        {
            enode = q.top();
            q.pop(); 
        }
    }
    return best;
}

int main()
{
	int a, b, i;
    cin>>n>>e;    
    memset(G, 0, sizeof(G));
    for(i=1; i<=e; i++)
    {
        cin >> a >> b;
        G[a][b] = G[b][a] = 1;
    }
    cout << search()<<endl;
    for(i=1; i<=n; i++){
    	cout << bestx[i];
    	if(i!=n) cout<<" ";
	}
    cout<<endl;   
    return 0;
}