很明显的最大流题目，通过不断寻找增广路，每找到一条就做相应的修改，直到找不到为止
#include
#include
#define max 100000000
#define num 205
using namespace std; int n, m, f;
//map[][]记录权值，mark[]标记是否访问过，pre[]记录增广路 int map[num][num], mark[num], pre[num]; void init()
{ int a, b, c; memset(map, 0, sizeof(map)); f = 0; for (int i = 0; i < m; ++ i) { cin >> a >> b >> c; map[a][b] = c; } } void max_flow()
{ //不断寻找增广路，知道找不到为止，找不到的标志为 mark[n]==0 while (1) { queue q; memset(mark, 0, sizeof(mark)); memset(pre, 0, sizeof(pre)); mark[1] = 1; q.push(1); while (!q.empty()) { int cur = q.front(); q.pop(); //找到了增广路，跳出 if (cur == n) break; for (int i = 1; i <= n; ++ i) { if (mark[i] == 0 && map[cur][i] > 0) { mark[i] = 1; q.push(i); pre[i] = cur; } } } //如果没找到可增广的路，直接跳出 if (mark[n] == 0) break; int min = max; //计算该增广路最大可增加的流量 for (int i = n; i != 1; i = pre[i]) { if (min > map[pre[i]][i]) { min = map[pre[i]][i]; } } //原路返回，修改路劲上边的权值 for (int i = n; i != 1; i = pre[i]) { map[pre[i]][i] -= min; map[i][pre[i]] += min; } //总流量增加 f += min; } } int main()
{ while (cin >> m >> n) { init(); max_flow(); cout << f << endl; } return 0;
}
延伸阅读
最新评论