Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

KM增广路

Posted by liu_cheng_ao at 2016-10-29 14:44:30 on Problem 2112
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#define Inf 0x3f3f3f3f
using namespace std;
int k,C,m,mid;
int a[250][250];
int to[220],c[50],fm[50][20],e[250];
bool km(int x)
{
     e[k+x]=1;
     for(int i=1;i<=k;i++)
     {
             if(a[k+x][i]<=mid&&!e[i])
             {
                               e[i]=1;
                               if(c[i]<m)
                               {
                                         fm[i][++c[i]]=x;
                                         to[x]=i;
                                         return true;
                               }
                               else
                               {
                                   for(int j=1;j<=c[i];j++)
                                   {
                                           if(!e[k+fm[i][j]]&&km(fm[i][j]))
                                           {
                                                   fm[i][j]=x;
                                                   to[x]=i;    
                                                   return true;      
                                           }
                                   }
                               }
             }
     }
     return false;
}
bool Isok(int mxl)
{
     memset(to,0,sizeof(to));
     memset(c,0,sizeof(c));
     memset(fm,0,sizeof(fm));
     for(int i=1;i<=C;i++)
     {
             memset(e,0,sizeof(e));
             if(!km(i))return false;
     }
     return true;
}
int main()
{
    scanf("%d%d%d",&k,&C,&m);
    for(int i=1;i<=k+C;i++)
    for(int j=1;j<=k+C;j++)
    {
            scanf("%d",&a[i][j]);
            if(a[i][j]==0&&i!=j)a[i][j]=Inf;
    } 
    for(int p=1;p<=k+C;p++)
    for(int i=1;i<=k+C;i++)
    for(int j=i+1;j<=k+C;j++)
    if(i!=j&&j!=p&&p!=i)
    a[i][j]=a[j][i]=min(a[i][j],a[i][p]+a[p][j]);
    int l=0,r=0;
    for(int i=1;i<=k+C;i++)
    for(int j=i+1;j<=k+C;j++)
    r=max(r,a[i][j]);
    while(l!=r)
    {
               mid=(l+r)>>1;
               if(Isok(mid))r=mid;
               else l=mid+1;
    }
    printf("%d",l);
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator