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

## 求纠错

Posted by CrazyMichael at 2015-03-31 16:19:03 on Problem 2112
```#include "stdio.h"
#define inf 1000000
#define maxk 32
#define maxc 202
int dist[maxk+maxc][maxk+maxc];
struct hp
{
int c,f,to,next;
}edge[(maxk+maxc+2)*(maxk+maxc+2)];
int bfs()
{
int i,front,rear,u,v,queue[maxk+maxc];
memset(flag,0,sizeof(flag));
flag[vs]=1;
level[vs]=0;
front=-1;
rear=0;
queue[rear]=vs;
while(front<rear)
{
front++;
u=queue[front];
if(u==vt) return 1;
{
v=edge[i].to;
if(flag[v]==0 && edge[i].c>edge[i].f)
{
flag[v]=1;
level[v]=level[u]+1;
rear++;
queue[rear]=v;
}
}
}
return 0;
}
int min(int a,int b)
{
if(a>b) return b;
return a;
}
int dfs(int u,int a)
{
int i,v,flow,sum=a;
if(u==vt) return a;
{
v=edge[i].to;
if(level[v]==level[u]+1 && edge[i].f<edge[i].c)
{
flow=dfs(v,min(a,edge[i].c-edge[i].f));
edge[i].f+=flow;
edge[i-1].f-=flow;
a-=flow;
}
}
return sum-a;
}
void dinic()
{
while(bfs())
dfs(vs,inf);
}
void floyd()
{
int i,j,t;
for(t=1;t<=k+c;t++)
for(i=1;i<=k+c;i++)
for(j=1;j<=k+c;j++)
if(t!=i && t!=j && dist[i][t]!=inf && dist[t][j]!=inf && dist[i][j]-dist[t][j]>dist[i][t])
dist[i][j]=dist[t][j]+dist[i][t];
}
void init()
{
int i,j,dis;
memset(edge,0,sizeof(edge));
scanf("%d%d%d",&k,&c,&m);
for(i=0;i<=(k+c+2)*(k+c+2)-1;i++)
edge[i].next=-1;
vs=0;
vt=k+c+1;
for(i=1;i<=k+c;i++)
for(j=1;j<=k+c;j++)
{
scanf("%d",&dis);
if(dis==0) dist[i][j]=inf;
else dist[i][j]=dis;
}
floyd();
n=k+c;
}
void build(int x)
{
int m1=0,i,j;
memset(edge,0,sizeof(edge));
for(i=1;i<=k;i++)
{
edge[m1].c=m;
edge[m1].to=i;
m1++;
edge[m1].c=0;
edge[m1].to=vs;
m1++;
}
for(i=k+1;i<=k+c;i++)
{
edge[m1].c=1;
edge[m1].to=vt;
m1++;
edge[m1].c=0;
edge[m1].to=i;
m1++;
}
for(i=1;i<=k;i++)
for(j=k+1;j<=k+c;j++)
{
if(dist[i][j]<=x)
{
edge[m1].c=inf;
edge[m1].to=j;
m1++;
edge[m1].c=0;
edge[m1].to=i;
m1++;
}
}
}
void work()
{
int t,sign=0,i,j,max=0,min=inf,w,maxflow=0,x;
for(i=1;i<=n;i++)
for(j=i+1;j<=n;j++)
{
if(dist[i][j]>max && dist[i][j]<inf) max=dist[i][j];
if(dist[i][j]<min) min=dist[i][j];
}
t=m1;
while(1)
{
m1=t;
x=(max+min)/2;
build(x);
dinic();
maxflow=0;
maxflow+=edge[w].f;
if(maxflow==c) max=x;
else  min=x+1;
if(max==min) break;
}
printf("%d",min);
}
int main()
{
init();
work();
return 0;
}
```

Followed by: