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

## （附AC代码）EK算法，数组开小了，没看清，要大于230贡献一发wa

Posted by h123120 at 2015-07-20 00:58:11 on Problem 2112
```#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
const int maxn=250;
const int INF=99999999;
int n,m,sum,s1,t1;//s,t为始点和终点
int flow[maxn][maxn],cap[maxn][maxn],a[maxn],p[maxn],d[maxn][maxn],k,c,milks;
//分别为：flow[u][v]为<u,v>流量、cap[u][v]为<u,v>容量、a[i]表示源点s到节点i的路径上的最小残留量、p[i]记录i的前驱
void Edmonds_Karp(int s,int t)
{
int i,u,v;
queue<int>q;//队列，用bfs找增广路
while(1)
{
memset(a,0,sizeof(a));//每找一次，初始化一次
a[s]=INF;
q.push(s);//源点入队
while(!q.empty())
{
u=q.front();
q.pop();
for(v=1; v<=m; v++)
{
if(!a[v]&&flow[u][v]<cap[u][v])
{
p[v]=u;
q.push(v);
a[v]=min(a[u],cap[u][v]-flow[u][v]);//s-v路径上的最小残量
}
}
}
if(a[t]==0)//找不到增广路,则当前流已经是最大流
break;
sum+=a[t];//流加上
for(i=t; i!=s; i=p[i]) // //从汇点顺着这条增广路往回走
{
//      cout<<i<<" ";
flow[p[i]][i]+=a[t];//更新正向流量
flow[i][p[i]]-=a[t];//更新反向流量
}
// cout<<endl;
}
}
int main()
{
int v,u,w;
while(scanf("%d%d%d",&k,&c,&milks)!=EOF)//n是边数，m是点数
{
int up=-1;
int down=INF;
for(int i=1; i<=c+k; i++)
for(int j=1; j<=c+k; j++)
scanf("%d",&d[i][j]);
for(int k1 = 1; k1 <= c+k; k1++)
for(int i = 1; i <= c+k; i++)
for(int j = 1; j <= c+k; j++)
if(d[i][k1]&&d[k1][j]&&(d[i][j]==0||d[i][j]>d[i][k1] + d[k1][j]))
{
d[i][j]=d[i][k1] + d[k1][j];
up=max(up,d[i][j]);
down=min(down,d[i][j]);
}

m=c+k+2;
t1=c+k+2;
s1=c+k+1;
int ans=up;

while(down<=up)
{
int mid=(down+up)/2;
sum=0;//记录最大流量
memset(flow,0,sizeof(flow));//初始化
memset(cap,0,sizeof(cap));
for(int i=1; i<=k; i++) //源点到挤奶机
cap[s1][i]=milks;
for(int i=k+1; i<=k+c; i++) //奶牛到汇点
cap[i][t1]=1;
for(int i = 1; i <= k; i++)
for(int j = k + 1; j <=k+ c; j++)
cap[i][j] = (d[i][j] != 0 && d[i][j] <= mid);
Edmonds_Karp(s1,t1);

if (sum == c)
{
if(mid < ans) ans = mid;
up = mid - 1;
}
else down = mid + 1;
}
printf("%d\n",ans);
}
return 0;
}

```

Followed by: