poj1087 A Plug for UNIX & poj1459 Power Network (最大流)

读题比做题难系列……

poj1087

输入n，代表插座个数，接下来分别输入n个插座，字母表示。把插座看做最大流源点，连接到一个点做最大源点，流量为1。

输入m，代表电器个数，接下来分别输入m个电器，字符串表示。把电器看做最大流终点，连接到一个点做最大汇点，流量为1。

输入k，代表转换器个数，接下来分别输入k个转换器，每个插座输入两个字母a,b表示a可以连在b上。把转换器看做流，b->a，因为转换器无限提供，流量为无限大

代码：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <queue>

#include <map>

#include <algorithm>

#include <string>

using namespace std;

const int N = 505;

const int INF = 0x7fffffff;

map<string, int>mymap;

int cap[N][N];

string str[N];

int flow[N];

int pre[N];

queue<int> q;

int BFS(int src, int des)

{

    int i;

    while (!q.empty()) q.pop();

    for (i = 1; i <= des; ++i) pre[i] = -1;

    pre[src] = 0;

    q.push(src);

    flow[src] = INF;

    while (!q.empty()) {

        int index = q.front();

        q.pop();

        if (index == des) break;

        for (i = 1; i <= des; ++i) {

            if (pre[i] == -1 && cap[index][i] > 0) {

                pre[i] = index;

                flow[i] = min(flow[index], cap[index][i]);

                q.push(i);

            }

        }

    }

    if (pre[des] == -1) return -1;

    return flow[des];

}

int maxFlow(int src, int des)

{

    int ans = 0;

    int in = 0;

    while ((in = BFS(src, des)) != -1) {

        int k = des;

        while (k != src) {

            int last = pre[k];

            cap[last][k] -= in;

            cap[k][last] += in;

            k = last;

        }

        ans += in;

    }

    return ans;

}

int main()

{

    int n, m, k, i;

    int cnt = 1;

    string str1,str2;

    cin >> n;

    for (i = 1; i <= n; ++i) {

        cin >> str1;

        mymap[str1] = ++cnt;

        cap[1][cnt] = 1;

    }

    cin >> m;

    for (i = 1; i <= m; ++i) {

        cin >> str[i] >> str2;

        if (!mymap[str[i]]) mymap[str[i]] = ++cnt;

        if (!mymap[str2]) mymap[str2] = ++cnt;

        cap[mymap[str2]][mymap[str[i]]] = 1;

    }

    cin >> k;

    for (i = 1; i <= k; ++i) {

        cin >> str1 >> str2;

        if (!mymap[str1]) mymap[str1] = ++cnt;

        if (!mymap[str2]) mymap[str2] = ++cnt;

        cap[mymap[str2]][mymap[str1]] = INF;

    }

    ++cnt;

    for (i = 1; i <= m; ++i) {

        cap[mymap[str[i]]][cnt] = 1;

    }

    cout << m - maxFlow(1, cnt);

    return 0;

}

poj 1459

配个良心的地址，读起题来容易些：http://www.2cto.com/kf/201502/377406.html

方法和上题相同，最大源点连到发电站，流量就是发电站的最大电量，用户同理。

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <queue>

using namespace std;

const int N = 105;

const int INF = 0x7fffffff;

int n, np, nc, m;

int flow[N];

int cap[N][N];

int pre[N];

queue<int>q;

int BFS(int src, int des)

{

        while (!q.empty()) {

                q.pop();

        }

        for (int i = 0; i <= des; ++i) {

                pre[i] = -1;

        }

        flow[src] = INF;

        pre[src] = 0;

        q.push(src);

        while (!q.empty()) {

                int index = q.front();

                q.pop();

                if (index == des) {

                        break;

                }

                for (int i = 1; i <= des; ++i) {

                        if (pre[i] == -1 && cap[index][i] > 0) {

                                pre[i] = index;

                                flow[i] = min(cap[index][i], flow[index]);

                                q.push(i);  //<---经常忘记这句！

                        }

                }

        }

        if (pre[des] == -1) {

                return -1;

        }

        return flow[des];

}

int maxFlow(int src, int des)

{

        int ans = 0;

        int in = 0;

        while ((in = BFS(src, des)) != -1) {

                int k = des;

                while (k != src) {

                        int last = pre[k];

                        cap[last][k] -= in;

                        cap[k][last] += in;

                        k = last;

                }

                ans += in;

        }

        return ans;

}

int main()

{

        int i;

        while (scanf("%d%d%d%d", &n, &np, &nc, &m) != EOF) {

                memset(cap, 0, sizeof cap);

                memset(flow, 0, sizeof flow);

                int u, v, z;

                for (i = 0; i < m; ++i) {

                        scanf(" (%d,%d)%d", &u, &v, &z);

                        cap[u + 1][v + 1] += z;

                }

                for (i = 0; i < np; ++i) { // power station

                        scanf(" (%d)%d", &u, &z);

                        cap[0][u + 1] = z;

                }

                for (i = 0; i < nc; ++i) { // consumer

                        scanf(" (%d)%d", &u, &z);

                        cap[u + 1][n + 1] = z;

                }

                printf("%d\n", maxFlow(0, n + 1));

        }

        return 0;

}

不明白为什么scanf的格式匹配会死循环，大概是回车的问题= =，加个空格就好了。

巴特西

poj1087 A Plug for UNIX & poj1459 Power Network (最大流)

最新文章

热门文章