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 的同学请注意~~~ 数组要开到1000

Posted by count_if at 2015-01-31 17:50:56 on Problem 2112
```虽然题目中说的是200 但是可能数据更新了？

#include<iostream>
#include<stdio.h>
#include<vector>
#include<math.h>
#include<deque>
#include<memory.h>
#include<queue>
#define inf 150000
using namespace std;
int K,C,M;
int G[500][500];
bool visit[1000];
int layer[1000];
bool bfs(int num){
memset(layer,-1,sizeof(visit));
queue<int> q;
q.push(0);
layer[0] = 0;
while (!q.empty()){
int cur = q.front();
q.pop();
for (int i = 1;i<=num+1;++i){
if (layer[i] == -1 && G[cur][i]>0){
layer[i] = layer[cur]+1;
q.push(i);
if (i == num+1)
return true;
}
}
}
return false;
}

int dfs(int num){
memset(visit,0,sizeof(visit));
deque<int> q;
int i;
int res = 0;
q.push_back(0);
visit[0] = true;
while (!q.empty())
{
int cur = q.back();
if (cur == num+1)
{           	//找到了 回去寻找最小的点
int size = q.size();
int nMin = inf;
int nindex = 0;
for (int j = 0;j<size-1;++j)
{
int u = q[j];
int v = q[j+1];
if (G[u][v] < nMin)
{
nindex = u;
nMin = G[u][v];
}
}
res += nMin;
for (int j = 0;j<size-1;++j)
{
int u = q[j];
int v = q[j+1];
G[u][v] -= nMin;
G[v][u] += nMin;
}
while (!q.empty()&&q.back()!=nindex)
{
visit[q.back()] = false;
q.pop_back();
}
}
else
{
for ( i = 1;i<=num+1;++i)
{
if (!visit[i] && layer[i] == layer[cur]+1 && G[cur][i] > 0){
q.push_back(i);
visit[i] =true;
break;
}
}
if ( i == num+2)
q.pop_back();
}

}
return res;
}
int map[500][500];//前 K为机器 后c为奶牛
void floyd(int n){
for (int k  = 1;k<=n;++k)
for (int i = 1;i<=n;++i)
for (int j = 1;j<=n;++j)
if (map[i][j] > map[i][k] + map[k][j])
map[i][j] = map[i][k] + map[k][j];
}

bool check(int dist,int C,int K,int M){
int res  = 0;
memset(G,0,sizeof(G));
//建图
//source
for (int i = K+1;i<=C+K;++i){
G[0][i]= 1;
}

for (int i = K+1;i<=C+ K;++i){
for (int j = 1;j<=K;++j){
if (map[i][j]<=dist)
G[i][j] = 1;
}
}
//for t
for (int i = 1;i<=K;++i){
G[i][C+K+1] = M;
}

while (bfs(C+K)){
res += dfs(C+K);
}
if (res == C)
return true;
else
return false;
}
int main(){
while (scanf("%d %d %d",&K,&C,&M) !=EOF){
memset(G,0,sizeof(G));
memset(map,0,sizeof(map));
//k 机器数 c奶牛数　　ｍ　每台机器能容纳最多奶牛数
int num = K+C;
int dist ;
int 	 maxdist = 0;
for (int i = 1;i<=num;++i){
for (int j = 1;j<=num;++j){
scanf("%d",&dist);
if (dist ==0 && i != j )
map[i][j] = inf;
else
map[i][j] = dist;
}
}
maxdist = 100000;
floyd(num);
int RES = maxdist;
int l = 0,r = maxdist;
while (l<r){
int mid = (l+r)/2;
if (check(mid,C,K,M)){
r = mid;
RES = mid;
}
else
l = mid +1;
}
printf("%d\n",RES);
}
return 0;
}```

Followed by: