首页 > 试题广场 >

右图中标出了每条有向公路上最大的流量,请问从S点到T点最大的

[单选题]
右图中标出了每条有向公路上最大的流量,请问从S点到T点最大的流量是________。
  • 46
  • 47
  • 54
  • 77
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

#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
发表于 2015-07-22 15:40:40 回复(1)
46 仔细观察可知
发表于 2016-08-18 13:52:35 回复(0)