#include

#include

#include

#include

#define min(a, b) ((a) < (b) ? (a) : (b))

int graph[7][7] = {

{0, 28, 7, 0, 19, 0, 0 },

{0, 0, 6, 15, 0, 0, 0 },

{0, 0, 0, 0, 12, 0, 0 },

{0, 0, 0, 0, 0, 7, 23},

{0, 7, 0, 14, 0, 0, 36},

{0, 0, 10, 0, 0, 18, 0 },

{0, 0, 0, 0, 0, 0, 0 }

};

#define vnum 7

const int vs = 0, vt = 6;

int parent[vnum];

int visited[vnum];

int queue[vnum];

void bfs(int s) {

int v;

for(v = 0; v < vnum; v++) { visited[v] = 0; parent[v] = v; }

int qhead = 0, qtail = 0;

queue[qtail++] = s;

visited[s] = 1;

while(qtail != qhead) {

int u = queue[qhead++];

for(v = 0; v < vnum; v++) {

if(!visited[v] && graph[u][v]) {

visited[v] = 1;

parent[v] = u;

queue[qtail++] = v;

}

}

}

}

int main(void) {

int sum = 0;

while(1) {

bfs(vs);

int flow = INT_MAX;

int t = vt;

while(parent[t] != t) {

int p = parent[t];

flow = min(flow, graph[p][t]);

t = p;

}

if(t != vs || flow == 0) break;

t = vt;

while(parent[t] != t) {

int p = parent[t];

graph[p][t] -= flow;

graph[t][p] += flow;

t = p;

}

sum += flow;

}

printf("%d\n", sum);

return 0;

}

答案是46