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

1A,贼开心！

Posted by phython at 2017-03-18 12:34:04 on Problem 2112
```网络流模板略去
int K,C,M;
const int MAX = 300;
const int INF = 1e8;
int G[MAX][MAX];
void floyd()
{
for(int k = 1;k <= K+C;k++)
for(int i = 1;i <= K+C;i++)
for(int j = 1;j <= K+C;j++)
G[i][j] = min(G[i][j],G[i][k] + G[k][j]);
}
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++)
{
int t;scanf("%d",&t);
if(!t) t = INF;
G[i][j] = t;
}
}
floyd();
int l = 1,r = 1;
for(int i = 1;i <= K;i++)
for(int j = K + 1;j <= K + C;j++)
r = max(r,G[i][j]);
r++;
while(r > l)
{
int mid = (l+r)/2;
prepare(K+C+2,0,K+C+1);
for(int i = 1;i <= K;i++)//构图
for(int j = K+1;j<=K+C;j++)
if(G[i][j] <= mid)
for(int i = 1;i <= K;i++)
for(int i = K+1;i <= K+C;i++)
int f = Dinic_flow();
if(f < C) l = mid + 1;
else r = mid;
}
cout<<l<<endl;
}```

Followed by: