最大流算法.cpp

计算机算法试题库问题

#include"stdio.h"
#define max  100

int max_flow(int c[max][max],int n,int sta,int end,int z,int m);

void main()
{
	int i,j;
	int sta=0,end,n,flux,k,l,x,m=0;
	int c[max][max];
	for(i=0;i<max;i++)
		for(j=0;j<max;j++)
			c[i][j]=0;//初始化
	FILE *fp;
	fp=fopen("input1.txt","r");
	if(fp==NULL)
		printf("error!");
	else
	{
        fscanf(fp,"%d %d",&k,&n);//读题类型和题数
		end=k+n+2;
		for(i=1;i<=k;i++)
		{
			fscanf(fp,"%d",&c[0][i]);//读每种类型的题数
			c[i][0]=-c[0][i];
			m+=c[0][i];//计算总题数
		}
		int y=i;
		while(!feof(fp))
		{			
			fscanf(fp,"%d ",&l);//读取每个题属于的类型总数
			for(j=1;j<=l;j++)
			{
				fscanf(fp,"%d ",&x);
				c[x][y]=1;
				c[y][x]=-1;
			}
			y++;
		}
		for(j=0;j<end;j++)
		{
			c[i][end-1]=1;
			c[end-1][i]=-1;
			i++;
		}//每个题目到汇点的容量为1
	}
	fclose(fp);
for(i=0;i<end;i++)
	{
		printf("\n");
		for(j=0;j<end;j++)
			printf("%2d",c[i][j]);
	}
  printf("\n");

	flux = max_flow(c,end,sta,end-1,k,m);
	
	if(flux==m)
	    printf("\nzui da liu:%d\n",flux);
	else
		printf("无解！");
}

int max_flow(int c[max][max],int n,int sta,int end,int z,int m)
{
	int i,j,k;
	int pred[max],val[max],flu[max][max],used[max],temp1,temp2,flux=0,w[max];
	FILE *fp;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			flu[i-1][j-1]=0;

	while(1)
	{
		for(i=0;i<n;i++)
		{
			if(i==sta)
			{
				used[sta]=1;
				val[sta]=-1;
			}
			else
			{
			    pred[i]=0;
			    val[i]=0;
			    used[i]=0;
			}
		}

		while(val[end]==0)
		{
			k=0;
			for(i=0;i<n;i++)
			{
				if(used[i]==1)
				{
					used[i]=0;
					temp1=i;
					temp2=val[i];
					k=1;
					break;
				}
			}

			if(k==0)
			{   for(i=0;i<=end;i++)
			{ for(j=0;j<=end;j++)
					 printf("%d ",flu[i][j]);
			printf("\n");
			}



				for(i=0;i<n;i++)
				{
					if(flu[end][i]>0) 
					{
						
						flux += flu[end][i];
						
					}
					if(flu[end][i]<0)
						flux -= flu[end][i];
				}
			if(flux==m)
			{
		    	fp=fopen("output.txt","w+");
			    if(fp==NULL)
				   printf("errors!");
		    	else
				{
                   for(i=1;i<=z;i++)
				   {
				      fprintf(fp,"%d:",i);
	            	  for(j=0;j<end;j++)
					  {
						if(flu[i][j]==1)
		            	fprintf(fp,"%d ",j-3);
					  }	
					 fprintf(fp,"\n");
				   }
				}
		    	fclose(fp);
				
				for(i=1;i<=z;i++)
				{
				  printf("%d:",i);
	            	for(j=0;j<end;j++)
					{
						if(flu[i][j]==1)
		            	printf("%d ",j-3);
					}	
					printf("\n");
				}
			}
			else
			{
				fp=fopen("output.txt","w+");
			    if(fp==NULL)
				   printf("errors!");
		    	else
					fprintf(fp,"无解！");
			}
				return flux;
			}
			for(i=0;i<n;i++)
			{
				if(val[i]==0&&c[temp1][i]!=0&&flu[temp1][i]<c[temp1][i])
				{
					pred[i]=temp1;
					if(temp2<0)
						val[i]=c[temp1][i]-flu[temp1][i];
					else
						val[i]=(temp2<c[temp1][i]-flu[temp1][i])?temp2:c[temp1][i]-flu[temp1][i];
					used[i]=1;
				}
				if(val[i]==0 && c[temp1][i]!=0 && flu[i][temp1]>0)
				{
					pred[i]=temp1;
					val[i]=temp2<flu[i][temp1]?temp2:flu[i][temp1];
					used[i]=1;
				}
			}
		}
		w[0]=end;
		k=0;
		while(w[k]!=sta)
		{
			w[k+1]=pred[w[k]];
			k++;
		}
		temp2=val[end];
		for(i=1;i<k+1;i++)
		{
			if(c[w[i]][w[i-1]]>0)
			{
				flu[w[i]][w[i-1]]+=temp2;
				flu[w[i-1]][w[i]]-=temp2;

			}
			else
			{
				flu[w[i]][w[i-1]]-=temp2;
				flu[w[i-1]][w[i]]+=temp2;
			}
		}	
	}  
}