題目連接：http://poj.org/problem?

id=1087

題意：
n種插座 ，m個(gè)電器，f組（x，y）表示插座x能夠替換插座y，問你最多能給幾個(gè)電器充電。

解法：起點(diǎn)向插座建邊，容量１，電器向匯點(diǎn)建邊。容量１，插座向電器建邊。容量１，能夠替換的插座間建邊。容量無窮大。然后套板子。

。。求最大流。

代碼：

#include <stdio.h> #include <ctime> #include <math.h> #include <limits.h> #include <complex> #include <string> #include <functional> #include <iterator> #include <algorithm> #include <vector> #include <stack> #include <queue> #include <set> #include <map> #include <list> #include <bitset> #include <sstream> #include <iomanip> #include <fstream> #include <iostream> #include <ctime> #include <cmath> #include <cstring> #include <cstdio> #include <time.h> #include <ctype.h> #include <string.h> #include <assert.h> using namespace std;const int MAXN = 1010;//點(diǎn)數(shù)的最大值 const int MAXM = 400010;//邊數(shù)的最大值 const int INF = 0x3f3f3f3f; struct Edge {int to, next, cap, flow; }edge[MAXM];//注意是MAXM int tol; int head[MAXN]; int gap[MAXN], dep[MAXN], pre[MAXN], cur[MAXN];void init() {tol = 0;memset(head, -1, sizeof(head)); } //加邊。單向圖三個(gè)參數(shù)，雙向圖四個(gè)參數(shù) void addedge(int u, int v, int w, int rw = 0) {edge[tol].to = v; edge[tol].cap = w; edge[tol].next = head[u];edge[tol].flow = 0; head[u] = tol++;edge[tol].to = u; edge[tol].cap = rw; edge[tol].next = head[v];edge[tol].flow = 0; head[v] = tol++; }//輸入?yún)?shù)：起點(diǎn)、終點(diǎn)、點(diǎn)的總數(shù) //點(diǎn)的編號沒有影響，僅僅要輸入點(diǎn)的總數(shù)int sap(int start, int end, int N) {memset(gap, 0, sizeof(gap));memset(dep, 0, sizeof(dep));memcpy(cur, head, sizeof(head));int u = start;pre[u] = -1;gap[0] = N;int ans = 0;while (dep[start] < N){if (u == end){int Min = INF;for (int i = pre[u]; i != -1; i = pre[edge[i ^ 1].to])if (Min > edge[i].cap - edge[i].flow)Min = edge[i].cap - edge[i].flow;for (int i = pre[u]; i != -1; i = pre[edge[i ^ 1].to]){edge[i].flow += Min;edge[i ^ 1].flow -= Min;}u = start;ans += Min;continue;}bool flag = false;int v;for (int i = cur[u]; i != -1; i = edge[i].next){v = edge[i].to;if (edge[i].cap - edge[i].flow && dep[v] + 1 == dep[u]){flag = true;cur[u] = pre[v] = i;break;}}if (flag){u = v;continue;}int Min = N;for (int i = head[u]; i != -1; i = edge[i].next)if (edge[i].cap - edge[i].flow && dep[edge[i].to] < Min){Min = dep[edge[i].to];cur[u] = i;}gap[dep[u]]--;if (!gap[dep[u]])return ans;dep[u] = Min + 1;gap[dep[u]]++;if (u != start) u = edge[pre[u] ^ 1].to;}return ans; }int m, n, f; map<string, int> Hash; string x, y;int main() {while (cin >> n){init();Hash.clear();int num1 = 2;int from = 0;int end = 1;for (int i = 1; i <= n; i++){cin >> x;Hash[x] = num1;addedge(0, num1, 1);num1++;}cin >> m;for (int i = 1; i <= m; i++){cin >> x >> y;if (Hash[x] == 0) Hash[x] = num1++;if (Hash[y] == 0) Hash[y] = num1++;addedge(Hash[x], end, 1);addedge(Hash[y], Hash[x], 1);}cin >> f;for (int i = 1; i <= f; i++){cin >> x >> y;if (Hash[x] == 0) Hash[x] = num1++;if (Hash[y] == 0) Hash[y] = num1++;addedge(Hash[y], Hash[x], 10000000);}int ans = sap(from, end, num1);printf("%d\n", m - ans);}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/zsychanpin/p/7090694.html

與50位技術(shù)專家面對面20年技術(shù)見證，附贈技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的poj 1087 A Plug for UNIX 【最大流】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。