HDU – 4280 Island Transport（ISAP）
分类：ACM-图论ACM-图论-网络流
题目大意：要求你将游客从最东边送到最西边，反正边是双向的，，没有差别了
解题思路：裸流
ISAP 8080MS
;Edge {int from, to, cap, flow;Edge() {}Edge(int from, int to, int cap, int flow): from(from), to(to), cap(cap), flow(flow) {}};struct ISAP {int p[N], num[N], cur[N], d[N];int t, s, n, m;bool vis[N];vector<int> G[N];vector<Edge> edges;void init(int n) {this->n = n;for (int i = 0; i <= n; i++) {G[i].clear();d[i] = INF;}edges.clear();}void AddEdge(int from, int to, int cap) {edges.push_back(Edge(from, to, cap, 0));edges.push_back(Edge(to, from, 0, 0));m = edges.size();G[from].push_back(m – 2);G[to].push_back(m – 1);}bool BFS() {memset(vis, 0, sizeof(vis));queue<int> Q;d[t] = 0;vis[t] = 1;Q.push(t);while (!Q.empty()) {int u = Q.front();Q.pop();for (int i = 0; i < G[u].size(); i++) {Edge &e = edges[G[u][i] ^ 1];if (!vis[e.from] && e.cap > e.flow) {vis[e.from] = true;d[e.from] = d[u] + 1;Q.push(e.from);}}}return vis[s];}int Augment() {int u = t, flow = INF;while (u != s) {Edge &e = edges[p[u]];flow = min(flow, e.cap – e.flow);u = edges[p[u]].from;}u = t;while (u != s) {edges[p[u]].flow += flow;edges[p[u] ^ 1].flow -= flow;u = edges[p[u]].from;}return flow;}int Maxflow(int s, int t) {this->s = s; this->t = t;int flow = 0;BFS();if (d[s] >= n)return 0;memset(num, 0, sizeof(num));memset(cur, 0, sizeof(cur));for (int i = 0; i < n; i++)if (d[i] < INF)num[d[i]]++;int u = s;while (d[s] < n) {if (u == t) {flow += Augment();u = s;}bool ok = false;for (int i = cur[u]; i < G[u].size(); i++) {Edge &e = edges[G[u][i]];if (e.cap > e.flow && d[u] == d[e.to] + 1) {ok = true;p[e.to] = G[u][i];cur[u] = i;u = e.to;break;}}if (!ok) {int Min = n – 1;for (int i = 0; i < G[u].size(); i++) {Edge &e = edges[G[u][i]];if (e.cap > e.flow)Min = min(Min, d[e.to]);}if (–num[d[u]] == 0)break;num[d[u] = Min + 1]++;cur[u] = 0;if (u != s)u = edges[p[u]].from;}}return flow;}};ISAP isap;int n, m;void init() {scanf(“%d%d”, &n, &m);isap.init(n);int x, y;int Min = INF, Max = -INF;int s, t;for (int i = 1; i <= n; i++) {scanf(“%d%d”, &x, &y);if (x <= Min) {s = i;Min = x;}if (x >= Max) {t = i;Max = x;}}int u, v, c;for (int i = 0; i < m; i++) {scanf(“%d%d%d”, &u, &v, &c);isap.AddEdge(u, v, c);isap.AddEdge(v, u, c);}int ans = isap.Maxflow(s, t);printf(“%d\n”, ans);}int main() {int test;scanf(“%d”, &test);while (test–) {init();}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
上一篇POJ – 3281 Dining （ISAP EK Dinic）下一篇最小费用最大流—MCMF模版
顶0踩0
就是去旅行。牵着彼此的手，
