My accepted codes give the same result. Good Luck

Moderator: Board moderators
Code: Select all
#include <stdio.h>
#include <vector>
using namespace std;
typedef vector<int> vi;
#define maxn 105
#define fmin(x, y) ( (x) > (y) ? (y) : (x) )
const int inf = 2147483647;
int V, E, s, t, B, D;
int c[maxn][maxn]; // capacity
int f[maxn][maxn];
int vc[maxn]; // vertex capacity
int vf[maxn]; // vertex flow
vi neigh_list[maxn];
int que[maxn];
int par[maxn];
bool input_graph()
{
int i, x, y, z;
if( scanf("%d", &V) != 1)
return false;
for(i=1; i<=V; ++i)
scanf("%d", vc + i);
scanf("%d", &E);
for(i = 1; i <= V; ++ i)
neigh_list[i].clear();
for(i = 0; i < E; ++ i)
{
scanf("%d %d %d", &x, &y, &z);
c[x][y] = z;
neigh_list[x].push_back(y);
}
// source and sink
V += 2;
s = V-1; t = V;
vc[s] = vc[t] = inf;
neigh_list[s].clear();
neigh_list[t].clear();
// multisource, multisink
scanf("%d %d", &B, &D);
while(B--)
{
scanf("%d", &x);
c[s][x] = inf;
neigh_list[s].push_back(x);
}
while(D--)
{
scanf("%d", &y);
c[y][t] = inf;
neigh_list[y].push_back(t);
}
memset(vf, 0, sizeof(vf));
return true;
}
bool path()
{
int front, rear;
int u, v, i, l;
int dis[maxn] = {0,};
front = rear = 0;
for(i=1; i<=V; ++i)
dis[i] = inf;
que[++rear] = s;
dis[s] = 0;
par[s] = 0;
while(front != rear)
{
u = que[++front];
l = neigh_list[u].size();
for(i=0; i<l; ++i)
{
v = neigh_list[u][i];
if(vc[v] - vf[v] <= 0)
continue;
if(c[u][v] - f[u][v] <= 0)
continue;
if(dis[u] + 1 < dis[v])
{
dis[v] = dis[u] + 1;
par[v] = u;
que[++rear] = v;
}
}
}
if(dis[t] < inf)
return true;
return false;
}
void edmonds_karp()
{
int u, v;
int min;
while( path() )
{
min = vc[t] - vf[t];
for(u = par[t], v = t; v != s; u = par[u], v = par[v])
{
min = fmin(min, c[u][v] - f[u][v]);
min = fmin(min, vc[u] - vf[u]);
}
vf[t] += min;
for(u = par[t], v = t; v != s; u = par[u], v = par[v])
{
f[u][v] += min;
f[v][u] -= min;
vf[u] += min;
}
}
printf("%d\n", vf[t]);
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("a.in", "r", stdin);
#endif
while( input_graph() )
{
memset(f, 0, sizeof(f));
edmonds_karp();
memset(c, 0, sizeof(c));
}
return 0;
}
Code: Select all
Code: Select all
input:
1
10
0
1 1
1 1
Code: Select all
output:
10
Code: Select all
for(i=0;i<K;i++)
for(j=0;j<K;j++)
residual[i][j]=c[i][j];
Code: Select all
for(y=0;y<K;y++)
if(parents[y]==UNKNOWN && residual[x][y]>0){
enQueue(Q,y);
parents[y]=x;
}
Code: Select all
while(i!=(j=parents[i])){
f[j][i]+=m;
f[i][j]=-f[j][i];
residual[j][i]=(c[j][i]-f[j][i]);
residual[i][j]=(c[i][j]-f[i][j]);
i=j;
}
Code: Select all
//Cut after AC