Nu aveti permisiuni pentru a descarca fisierul grader_test18.in
Diferente pentru flux-si-cuplaj intre reviziile #31 si #35
Nu exista diferente intre titluri.
Diferente intre continut:
int t[N]; int n, m;
int bfs(int source, int sink)
int bfs (int source, int sink)
{
int Q[N+1], p=0,q=0;
int Q[N + 1], p = 0, q = 0;
bool use[N];
memset(use, 0, sizeof(use)); memset(t, 0, sizeof(t)); Q[0]=source; use[source]=1;
memset (use, 0, sizeof (use)); memset (t, 0, sizeof (t)); Q[0] = source; use[source] = 1;
while(p<=q)
while (p <= q)
{
int u=Q[p++];//scoatem primul element din coada
int u = Q[p++]; //scoatem primul element din coada
for(int i=source;i<=sink;++i) // pt fiecare nod ( adiacent ) if(!use[i]) // nu am folosit nodul if(cap[u][i] - flux[u][i] > 0) // mai putem pompa?
for (int i = source;i <= sink;++i) // pt fiecare nod ( adiacent ) if (!use[i]) // nu am folosit nodul if (cap[u][i] - flux[u][i] > 0) // mai putem pompa?
{
Q[++q]=i; // inseram nodul i in coada t[i]=u; use[i]=1;
Q[++q] = i; // inseram nodul i in coada t[i] = u; use[i] = 1;
} }
if(t[sink]) return 1;
if (t[sink]) return 1;
return 0; }
int edmond-karp(int source, int sink)
int edmond-karp (int source, int sink)
{
int flow=0; //fluxul
int flow = 0; //fluxul
int i, min;
while(bfs(source, sink)) // cat timp mai exista un drum de ameliorare
while (bfs (source, sink)) // cat timp mai exista un drum de ameliorare
{
min=oo; for(i=sink; i; i=t[i]) if(cap[t[i]][i]-flux[t[i]][i] < min) min=cap[t[i]][i]-flux[t[i]][i]; //calculam minimul dintre capacitatile ramase de pe drum for(i=sink ; i; i=t[i]) flux[t[i]][i]+=min, //adaugam minimul la fluxul de pe arcele de pe drum flux[i][t[i]]-=min; //scadem minimul de pe arcele inverse
min = oo; for (i = sink; i; i = t[i]) if (cap[ t[i] ][i] - flux[ t[i] ][i] < min) min = cap[ t[i] ][i] - flux[ t[i] ][i]; //calculam minimul dintre capacitatile ramase de pe drum for (i = sink ; i; i = t[i]) flux[ t[i] ][i] += min, //adaugam minimul la fluxul de pe arcele de pe drum flux[i][ t[i] ] -= min; //scadem minimul de pe arcele inverse
flow+=min; // adaugam minimul la flux
flow += min; // adaugam minimul la flux
} return flow; }
== code(c) |
inlinevoid support(int n)
void support(int n)
{ vector<int>::iterator it;