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

## 哪位好心人帮我看一下，检查了很长时间都还是wa！！天理啊。。。。

Posted by zhoubizhang at 2010-04-25 15:29:23 on Problem 2112
```#include<stdio.h>
#include<string.h>
#define MM 250
const int inf = 1 << 30;
int K,C,M,z;
int cur[MM],pre[MM],dis[MM][MM],Dis[MM],gap[MM];
int maze[MM][MM];
int min(int a,int b)
{
return a==-1||b>a?b:a;
}
void Froyd()
{
int u,w,v,n=z;
for(u=1;u<=n;u++)
for(v=1;v<=n;v++)
if(dis[v][u]!=inf)
{
for(w=1;w<=n;w++)
if(dis[v][u]+dis[u][w]<dis[v][w])
dis[v][w]=dis[v][u]+dis[u][w];
}
return ;
}
void build_graph(int max)
{
int n=z+1,i,j;
memset(maze,0,sizeof(maze));
for(i=1;i<=K;i++)
{
maze[i][n]=M;
}
for(i=K+1;i<=z;i++)
{
maze[0][i]=1;
}
for(i=K + 1; i <= z; i ++)
for(j = 1; j <= K; j ++)
if(dis[i][j] <= max)//注意现在的dis已不是先前的dis现在以为最短路径
maze[i][j] = 1;
return ;
}
int sap(int s,int t,int nodenum)
{
memset(cur,0,sizeof(cur));
memset(pre,0,sizeof(pre));
memset(Dis,0,sizeof(Dis));
memset(gap,0,sizeof(gap));
int u=pre[s]=s,maxflow=0,aug=-1;
int v;
gap[0]=nodenum;
while(Dis[s]<nodenum)
{
loop:
for(v=cur[u];v<nodenum;v++)
{
if(maze[u][v]&&Dis[u]==Dis[v]+1)
{
aug=min(aug,maze[u][v]);
pre[v]=u;
u=cur[u]=v;
if(v==t)
{
maxflow+=aug;
for(u=pre[v];v!=s;v=u,u=pre[u])
{
maze[u][v]-=aug;
maze[v][u]+=aug;
}
aug=-1;
}
goto loop;
}
}

int mindis=nodenum-1;
for(v=0;v<nodenum;v++)
{
if(maze[u][v]&&mindis>Dis[v])
{
cur[u]=v;
mindis=Dis[v];
}
}

if((--gap[Dis[u]])==0)
break;
gap[Dis[u]=mindis+1]++;
u=pre[u];
}
return maxflow;
}
int main()
{
int i,j,left,right;
scanf("%d%d%d",&K,&C,&M);
z=K+C;
for(i=1;i<=z;i++)
{
for(j=1;j<=z;j++)
{
scanf("%d",&dis[i][j]);
if(dis[i][j]==0)
dis[i][j]=inf;
}
}
Froyd();
left=0,right=10000;
while(left<right)
{
int mid=(left+right)>>1;
build_graph(mid);
int temp=sap(0,z+1,z+2);
if(temp>=C)right=mid;
else left=mid+1;
}
printf("%d\n",right);
return 0;
}```

Followed by: