cut.cpp

无向图的最大割:对于给定的无向图G

#include <fstream>
#include <vector>
#include <queue>
#include <math.h>
#include <algorithm>
using namespace std;

typedef struct _VINFO
{
	short *data;
	short index;  //还未确定的下标
	short up;
}VINFO,*PVINFO,*LPINFO;

int IsValid(short *v,short level/*现在是第几层,基于0*/,short n/*v数组的大小*/,short **w/*矩阵*/,short e/*共有几条边*/,short &better/*目前最好的*/,short *bn);

class T_less
{
public:
	bool operator () (const VINFO& x, const VINFO& y) const
	{
		return x.up<y.up;
	}
};

class T_greater
{
public:
	bool operator () (const VINFO& x, const VINFO& y) const
	{
		if(x.up>y.up)
			return true;
	}
};

void main()
{
	ifstream cin("input.txt", ios::in);
	ofstream cout("output.txt", ios::out);

	short n,e,i,j,x,y,k;
	cin >>n >>e;

	//动态分配N*N的空间
	short **w=new short*[n];
	for(i=0;i<n;i++)
		w[i]=new short[n];

	//空间清清零
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
			w[i][j]=0;

	//读入数据
	for(i=0;i<e;i++)
	{
		cin >>x >>y;
		w[x-1][y-1]=w[y-1][x-1]=1;
	}


	//下面用贪心算出一个预值
	vector<short> S1,S2,V;
	short cut;

	for(i=0;i<n;i++)
		V.push_back(i);

	bool iss=false;
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
		{
			if(w[i][j]>0)
			{
				x=i;
				y=j;
				iss=true;  //已经找到第一条边了,而且x一定小于y
				break;
			}
		}
		if(iss)
			break;
	}

	cut=1;
	S1.push_back(x);
	S2.push_back(y);
	short *p=find(V.begin(),V.end(),x);
	V.erase(p);
	p=find(V.begin(),V.end(),y);
	V.erase(p);

	short *w1=new short[n];
	short *w2=new short[n];
	short *score=new short[n];
	short *pmaxw1,*pmaxw2,maxnum;


	for(j=1;j<=n-2;j++)
	{
		for(k=0;k<n;k++)
			w1[k]=w2[k]=0;

		for(i=0;i<V.size();i++)
		{
			short index=V[i];
			for(k=0;k<n;k++)
			{
				if(w[index][k] && find(S1.begin(),S1.end(),k)!=S1.end())
					w1[index]++;
				if(w[index][k] && find(S2.begin(),S2.end(),k)!=S2.end())
					w2[index]++;
			}
		}

		pmaxw1=max_element(w1,w1+n);
		pmaxw2=max_element(w2,w2+n);
		maxnum=*pmaxw1>*pmaxw2?*pmaxw1:*pmaxw2;

		if(*pmaxw1 >= *pmaxw2)
		{
			short ii=pmaxw1-w1;
			if(w1[ii]>w2[ii])
				S2.push_back(ii);
			else
				S1.push_back(ii);
			p=find(V.begin(),V.end(),ii);
			V.erase(p);
			cut+=maxnum;

		}
		else
		{
			short ii=pmaxw2-w2;
			if(w1[ii]>w2[ii])
				S2.push_back(ii);
			else
				S1.push_back(ii);
			p=find(V.begin(),V.end(),ii);
			V.erase(p);
			cut+=maxnum;
		}
	}

	//下面开始真正的算
	short *vn=new short[n];
	short *bn=new short[n];
	for(i=0;i<n;i++)
	{
		vn[i]=-1;     //还没有确定
		bn[i]=-1;
	}

	vector<VINFO> maxheap;    //极大堆
	vector<VINFO> minheap;    //极小堆
	VINFO info;
	info.data=vn;
	info.index=0;
	info.up=cut;
	//maxheap.push_back(info);
	minheap.push_back(info);

	//while(maxheap.size()>0)
	while(minheap.size()>0)
	{
		/*short *v=maxheap[0].data;
		short ii=maxheap[0].index;
		pop_heap(maxheap.begin(), maxheap.end(), T_less());
		maxheap.pop_back();*/
		short *v=minheap[0].data;
		short ii=minheap[0].index;
		pop_heap(minheap.begin(), minheap.end(), T_greater());
		minheap.pop_back();

		v[ii]=1;
		short ret=IsValid(v,ii,n,w,e,cut,bn);
		if(ret>=cut && ii<n-1) //可以
		{
			short *tmp=new short[n];
			for(i=0;i<n;i++)
				tmp[i]=v[i];
			VINFO info;
			info.data=tmp;
			info.index=ii+1;
			info.up=ret;
			minheap.push_back(info);
		}

		v[ii]=0;
		ret=IsValid(v,ii,n,w,e,cut,bn);
		if(ret>=cut && ii<n-1) //可以
		{
			short *tmp=new short[n];
			for(i=0;i<n;i++)
				tmp[i]=v[i];
			VINFO info;
			info.data=tmp;
			info.index=ii+1;
			info.up=ret;
			minheap.push_back(info);
		}

		make_heap(minheap.begin(), minheap.end(), T_greater());		//极大堆

		delete []v;
	}



	if(bn[0]==0) //第一位是0的话，转为1
		for(i=0;i<n;i++)
			bn[i]=1-bn[i];

	cout <<cut <<endl;
	for(i=0;i<n;i++)
		cout <<bn[i] <<" ";

	for(i=0;i<n;i++)
		delete []w[i];
	delete []w;
	delete []w1;
	delete []w2;
	delete []score;
	delete []bn;
}

int IsValid(short *v,short level/*现在是第几层,基于0*/,short n/*v数组的大小*/,short **w/*矩阵*/,short e/*共有几条边*/,short &better/*目前最好的*/,short *bn)
{
	if(level==0)
		return better;
	short sum=0,s1,s2;
	short i,j;
	short zero=0;
	for(i=0;i<=level;i++)
		for(j=0;j<=level;j++)
			if(v[i]==v[j] && w[i][j])
				sum++;

	sum=sum/2; //多算了一倍

	for(i=level+1;i<n;i++)
	{
		s1=0;
		s2=0;
		for(j=0;j<=level;j++)
		{
			if(w[i][j])
			{
				if(v[j]==1)
					s1++;
				else
					s2++;
			}
		}
		if(s1>s2)
			sum+=s2;
		else
			sum+=s1;
	}

	for(i=level+1;i<n;i++)
		for(j=level+1;j<n;j++)
			if(w[i][j]==0)
				zero++;
	short tmp=(n-level-1)*(n-level-1)/2-zero;
	sum+=tmp/2;
	

	if(e-sum<better)
		return 0;       //0表示必须淘汰
	else if(level==n-1) //最后一层
	{
		if(better==e-sum)
		{
			for(i=0;i<n;i++)
				if(v[i]!=bn[i])
					break;
			if(bn[i]==0 || bn[0]==-1) 
			{
				for(i=0;i<n;i++)
					bn[i]=v[i];
			}
		}
		else
		{
			better=e-sum;
			for(i=0;i<n;i++)
				bn[i]=v[i];
		}
		return better;
	}
	else
		return e-sum;
}