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

哪位好心大牛帮忙看一下啊~~EK能过。。isap就是过不了。。。哎。。。。

Posted by 671superone at 2012-08-13 14:40:58 on Problem 2112
```#include <cstdio>
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

#define maxn	300
#define inf		1000000

int s, t;
int k, c, m, n;
int map[maxn][maxn], dist[maxn], num[maxn], pre[maxn], now[maxn];
int dis[maxn][maxn];

void initialize()
{
s = 0;
n = k + c;
t = n + 1;
memset(dis, 0, sizeof(dis));
}

void floyd()
{
int i, j, v;
for (i=1; i<=n; i++)
{
for (j=1; j<=n; j++)
{
for (v=1; v<=n; v++)
{
if (dis[j][v] > dis[j][i] + dis[i][v])
{
dis[j][v] = dis[j][i] + dis[i][v];
}
}
}
}
}

void init(int mid)
{
int i, j;
memset(map, 0, sizeof(map));
memset(num, 0, sizeof(num));
memset(now, 0, sizeof(now));
memset(pre, 0, sizeof(pre));
for (i=k+1; i<=n; i++)
{
map[s][i] = 1;
}
for (i=1; i<=k; i++)
{
map[i][t] = m;
}
for (i=k+1; i<=n; i++)
{
for (j=1; j<=k; j++)
{
if (mid >= dis[i][j])
{
map[i][j] = 1;
}
}
}
}

void bfs()
{
int i;
for (i=s; i<=t; i++)
{
dist[i] = t+1;
}
dist[t] = 0;
num[0]++;

queue<int> q;
q.push(t);
while (!q.empty())
{
int u = q.front();
q.pop();

for (i=s; i<=t; i++)
{
if (dist[i] > t && map[i][u])
{
dist[i] = dist[u] + 1;
num[dist[i]]++;
q.push(i);
}
}
}
}

int augment()
{
int tmp, width = (0x7ffffff);
int i;
for (i=t; i != s; i=pre[i])
{
tmp = map[pre[i]][i];
if (tmp < width)
{
width = tmp;
}
}
for (i=t; i != s; i=pre[i])
{
map[i][pre[i]] += width;
map[pre[i]][i] -= width;
}
return width;
}

int retreat(int &i)
{
int tmp, j;
int mind = t;
for (j=s; j<=t; j++)
{
if (map[i][j] && dist[j] < mind)
{
mind = dist[j];
}
}
tmp = dist[i];
num[tmp]--;
dist[i] = mind + 1;
num[dist[i]]++;
if (i != s)
{
i = pre[i];
}
return num[tmp];
}

int isap()
{
int f = 0;
int i, j;
bfs();
/*
for (i=s; i<=t; i++)
{
now[i] = s;
}
*/
i = s;
while (dist[s] < t+1)
{
for (j = now[i]; j<=t; j++)
{
if (map[i][j] && dist[i] == dist[j]+1)
{
break;
}
}
if (j <= t)
{
now[i] = j;
pre[j] = i;
i = j;
if (i == t)
{
f += augment();
i = s;
}
}
else
{
now[i] = s;
if (retreat(i) == 0)
{
break;
}
}
}
return f;
}

int main()
{
while (scanf("%d %d %d", &k, &c, &m) != EOF)
{
int i, j;
initialize();
for (i=1; i<=n; i++)
{
for (j=1; j<=n; j++)
{
scanf("%d", &dis[i][j]);
if (!dis[i][j])
{
dis[i][j] = inf;
}
}
}
floyd();
int low = 0, high = 20000, mid;
mid = (low + high) / 2;
while (low < high)
{
init(mid);
if (isap() >= c)
{
high = mid - 1;
}
else
{
low = mid + 1;
}
mid = (low + high)/2;
}
printf("%d\n", mid);
}
return 0;
}```

Followed by: