pipei.cpp

最优网络01匹配算法。

//////////////////////////////////////////////////
///
///               求解最佳匹配的原始-对偶算法
//
//                               WSR 030427
//////////////////////////////////////////////////


#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <fstream.h>
#include  <iomanip.h>

#define M  5
#define N  6

int B[M][N]={-1};/////0----无边 1----自由边 //2----匹配边
int A[M][M]={-1};//////辅助图
int mate1[M]={-1};////匹配结果1
int mate2[N]={-1};///匹配结果2
int exposed[M]={-1};////
int Q[M]={-1};         /////////1,0
int label[M]={-1};


void augment(int v)
{ 
	if(label[v]==-1)
	{
		mate1[v]=exposed[v];
		mate2[exposed[v]]=v;
		return;
	}
	else
	{
		exposed[label[v]]=mate1[v];
		mate1[v]=exposed[v];
		mate2[exposed[v]]=v;
		augment(label[v]);
	}		  
}

void main()
{
	int i,j;
	int temp=0;
	ifstream inputdata("data.txt",ios::in);
    ofstream outputdata("result.txt",ios::out);
	
	for(i=0;i<M;i++)
		for(j=0;j<N;j++)
		{
			inputdata>>B[i][j];
			if(B[i][j]==0) B[i][j]=-1;
		}
	inputdata.close();
    
	 for(i=0;i<M;i++)
	 {
		 mate1[i]=-1;
		 Q[i]=-1;     
		 label[i]=-1;
	 }
	 for(i=0;i<N;i++)
	 {
		 mate2[i]=-1;
	 }

        
stage:
		/////////未覆盖
		for(i=0;i<M;i++)
		   exposed[i]=-1;

		/////辅助图A    ----空
		for(i=0;i<M;i++)
			for(j=0;j<M;j++)
			   A[i][j]=-1;

		for(j=0;j<N;j++)
			for(i=0;i<M;i++)
			{
				if(B[i][j] == 1)//////// do when  (v,u) is  in  set B
				{
					if(mate2[j]==-1)
					{
						exposed[i]=j;
					}
					else
					{
						if(mate2[j]!=i)
						{
							//A=A _U_ (v,mate[u]);
							if(A[i][mate2[j]]!=1)
								A[i][mate2[j]]=1;
						}
					}
				}
			}
            
			////Q为空
			for(i=0;i<M;i++)  
			{
				Q[i]=-1;
			} 

			for(i=0;i<M;i++)
			{
				if(mate1[i]==-1)  
				{
					if(Q[i]!=1) Q[i]=1; //Q = Q  _U_  v;
				    label[i]=-1;
				}
			}
           
			/////////Q是否为空
			temp=0;
           for(i=0;i<M;i++)
		   {
			   if(Q[i]==1)
			   {
				   temp=1;
				   break;
			   }
		   }
           
		   while(temp)
		   {
			   for(i=0;i<M;i++)/////// are you sure for?
			   {
				   if(Q[i]==1)  ////v in set Q
				   {
					   Q[i]=-1;
					   if(exposed[i]!=-1)
					   {
						   augment(i);
						   goto stage;
					   }
					   else
					   {
						   for(j=0;j<M;j++)
						   {
							   if(label[j]!=-1 && A[i][j]==1) ////i---v,j----v'
							   {
								   label[j]=i;
								   if(Q[j]!=1) Q[j]=1;///Q=Q _U_ v'
							   }
						   }
					   }
				  //i=1000;//break;  //for Q[i]==1
				   }
			   }///////end of for(i)

				/////////Q是否为空
			   temp=0;
			   for(i=0;i<M;i++)
			   {
				   if(Q[i]==1)
				   {
					   temp=1;
					   break;
				   }
			   }

		   }/////end of while 
///////end of stage

		   for(i=0;i<M;i++)
		   outputdata<<setw(4)<<i<<"-->"<<setw(4)<<mate1[i]<<endl;
		   outputdata.close();
}