bfs

#include <iostream>

using namespace std;

#include <iostream>

#include <fstream>

using namespace std;

int v, e;

struct Link

{

Link(int u, int capacity)

{

this->u = u;

this->flow = 0;

this->capacity = capacity;

this->cosine = NULL;

next = NULL;

}

int u;

int capacity;

int flow;

Link *cosine;

Link *next;

};

struct Item

{

int u;

int localResidue;

};

struct ansLink

{

ansLink(int v, int u) {this->v = v; this->u = u; next = NULL;}

int u, v;

ansLink *next;

};

ansLink* store = NULL;

Link* graph[500];

int seen[500];

Item queue[500];

int parent[500];

int front;

int back;

int min(int a, int b)

{

return (a<b) ? a : b;

}

void push(Item val)

{

queue[back] = val;

back = (back + 1) % 500;

}

Item pop()

{

Item ret = queue[front];

front = (front + 1) % 500;

return ret;

}

bool queueEmpty()

{

return back == front;

}

void doFlow(int head, int flow)

{

for(Link* temp = graph[parent[head]]; temp != NULL; temp = temp->next)

{

if(temp->u == head)

{

temp->flow += flow;

temp->cosine->flow -= flow;

}

}

}

int run = 1;

void bfs(int n)

{

Item item;

item.u = n;

item.localResidue = 987654321;

push(item);

Item nextItem;

nextItem.u = 0;

nextItem.localResidue = 987654321;

while(!queueEmpty())

{

Item i = pop();

seen[i.u] = 2;

//cout << i << endl;

for(Link *temp = graph[i.u]; temp != NULL; temp = temp->next)

{

if(seen[temp->u] == 0 && temp->capacity > temp->flow)

{

parent[temp->u] = i.u;

if(store == NULL)

{

store = new ansLink(i.u);

}

else

{

ansLink *ansHead = NULL;

for(ansHead = store; ansHead->next != NULL; ansHead = ansHead->next)

{

store->next = new ansLink(i.u);

}

}

nextItem.u = temp->u;

nextItem.localResidue = min(i.localResidue, temp->capacity - temp->flow);

push(nextItem);

seen[temp->u] = 1;

if(nextItem.u == v + 1)

{

int head = v+1;

while(head != 0)

{

doFlow(head, nextItem.localResidue);

head = parent[head];

}

run = 1;

return;

}

}

}

}

if(nextItem.u != v + 1)

{

run = 0;

}

}

void bfs_all()

{

for(int i = 1; i <= v; i ++)

if(seen[i] == 0)

bfs(i);

}

int main()

{

fstream fin("input.txt");

fin >> v >> e;

for(int i = 0; i < e; i ++)

{

int a, b, c;

fin >> a >> b >> c;

Link *aLink = NULL;

Link *bLink = NULL;

bool isExist = false;

if(graph[a] == NULL)

{

graph[a] = new Link(b, c);

aLink = graph[a];

}

else

{

Link *temp = NULL;

for(temp = graph[a]; temp->next != NULL; temp = temp->next)

{

if(temp->next->u == b)

{

isExist = true;

temp->next->capacity = c;

}

}

if(!isExist)

{

temp->next = new Link(b, c);

aLink = temp->next;

}

}

isExist = false;

if(graph[b] == NULL)

{

graph[b] = new Link(a, 0);

bLink = graph[b];

}

else

{

Link *temp = NULL;

for(temp = graph[b]; temp->next != NULL; temp = temp->next)

{

if(temp->next->u == a)

{

isExist = true;

break;

}

}

if(!isExist)

{

temp->next = new Link(a, 0);

bLink = temp->next;

}

}

if(aLink && bLink)

{

aLink->cosine = bLink;

bLink->cosine = aLink;

}

}

while(run)

{

back = 0;

front = 0;

memset(parent, -1, sizeof(parent));

memset(seen, 0, sizeof(seen));

bfs(0);

}

for(int i = 1; i <= v; i ++)

{

cout << parent[i] << endl;

}

int result = 0;

for(Link *temp = graph[0]; temp != NULL; temp = temp->next)

{

result += temp->flow;

}

cout << result << endl;

}