Poj Solution 2112

http://poj.org/problem?id=2112

#include<iostream> 
using namespace std;
#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;

}