Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
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: