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！

Posted by yc5_yc at 2012-08-23 22:18:12 on Problem 2112
```感谢以下网站:http://blog.sina.com.cn/s/blog_64675f540100k7q0.html
AC code:

#include <cstdio>
#include <string.h>
using namespace std;
const int KMax=50,NMax=250,PMax=125000;
struct edge {
int num,len;
edge *next,*rev;
}*S[NMax],pool[PMax];
int N,L,K,C,M,A[NMax][NMax],D[KMax][NMax];
void Build(int a,int b,int c) {
edge *p=&pool[L++],*q=&pool[L++];
p->num=b;p->len=c;p->next=S[a];S[a]=p;p->rev=q;
q->num=a;q->len=0;q->next=S[b];S[b]=q;q->rev=p;
}
int q[NMax],level[NMax];
bool makelevel() {
for(int i=1;i<=N;i++) level[i]=-1;
q[0]=0;level[0]=0;
for(int i=0,bot=1;i<bot;i++) {
int tmp=q[i];
for(edge *p=S[tmp];p;p=p->next) if(p->len && level[p->num]==-1)
level[q[bot++]=p->num]=level[tmp]+1;
}
return level[N]!=-1;
}
inline int min(int a,int b) {return a<b?a:b;}
int find(int a,int alpha) {
if(a==N) return alpha;
int tot=0,tmp;
for(edge *p=S[a];p && tot<alpha;p=p->next) {
if(p->len && level[p->num]==level[a]+1)
if(tmp=find(p->num,min(p->len,alpha-tot))) {
tot+=tmp;
p->len-=tmp;
p->rev->len+=tmp;
}
}
if(!tot) level[a]=-1;
}
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]);
for(int k=1;k<=K+C;k++)
for(int i=1;i<=K+C;i++)
for(int j=1;j<=K+C;j++)
if((A[i][j]==0 || A[i][k]+A[k][j]<A[i][j]) && A[i][k] && A[k][j])
A[i][j]=A[i][k]+A[k][j];
int Maxn=0;
for(int i=1;i<=K;i++)
for(int j=K+1;j<=K+C;j++) {
D[i][j-K]=A[i][j];
if(D[i][j-K]>Maxn) Maxn=D[i][j-K];
}
int x=0,y=200*(K+C);
N=K+C+1;
while(x<y) {
if(x+1==y) break;
int mid=(x+y)>>1;
L=0;memset(S,0,sizeof(S));
for(int i=1;i<=K;i++)
for(int j=1;j<=C;j++)
if(D[i][j]<=mid && D[i][j]!=0) Build(i,K+j,1);
for(int i=1;i<=K;i++) Build(0,i,M);
for(int i=1;i<=C;i++) Build(K+i,N,1);
int ret=0,tmp;
while(makelevel())
while(tmp=find(0,100000000)) ret+=tmp;
if(ret==C) y=mid;
else x=mid;
}
printf("%d\n",y);
return 0;
}
```

Followed by: