2112.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include"iostream.h" 
#define null 0

const int size=1010;

long dis[size][size],k,m,c,up,w[size][size];

int maxmatch(int n,int m,long w[][size],int *p)

{
       int p_n[size];
       int p_m[size];
       bool sign[size];
       int q[size],from[size],s,t;


       int i,j,link,now,h;

       for(i=0;i<n;i++)p_n[i]=-1;
       for(j=0;j<m;j++)p_m[j]=-1;

       for(i=0;i<n;i++)
       if(p_n[i]==-1)
       {
              for(j=0;j<m;j++)sign[j]=0;
                 

              s=1;link=-1;


              from[0]=-1;
              q[0]=size-1;
              p_m[size-1]=i;
              

              for(t=0;t<s;t++)
              {
                     now=q[t];
                     for(j=0;j<m;j++)
                     {
                            if(w[p_m[now]][j]<=up&&sign[j]==0)
                            {
                                   sign[j]=1;
                                   q[s]=j;
                                   from[s++]=t;
                                   

                                   if(p_m[j]==-1)
                                   {
                                          link=s-1;
                                          break;
                                   }
                            }
                     }

                     if(j<m)break;
              }

              if(t<s)
              {
                     while(from[link]!=-1)
                     {
                            h=from[link];
                            p_m[q[link]]=p_m[q[h]];

                            p_n[p_m[q[h]]]=q[link];
                            link=h;
                     }
              }
       }

       int an;
       for(i=0,an=0;i<n;i++)
       {
              if(p)p[i]=p_n[i];
              if(p_n[i]>=0)an++;
       }

       return an;

}

void init()
{
	int i,j,s,l;
	cin>>k>>c>>m;
	s=k+c;
	for(i=0;i<s;i++)
	for(j=0;j<s;j++)
	{
		cin>>dis[i][j];
		if(i!=j&&dis[i][j]==0)dis[i][j]=9999999;
	}
	
	for(l=0;l<s;l++)
	for(i=0;i<s;i++)
	for(j=0;j<s;j++)
	{
		if(dis[i][l]+dis[l][j]<dis[i][j])
		dis[i][j]=dis[i][l]+dis[l][j];
	}
	
   for(i=0;i<k;i++)
   for(j=0;j<m;j++)
   for(l=k;l<s;l++)
   w[l-k][i*m+j]=dis[l][i];
   	
}

int main()
{
	long s,a,b,i,j;
	init();
		
	k*=m;
	a=0;b=200*250;
	while(a<b-1)
	{
		up=(a+b)/2;
		if(maxmatch(c,k,w,0)==c)b=up;
		else a=up;
	}
	cout<<b<<endl;
	
	return 0;

}