1550: Simple String 最大流解法

http://acm.csu.edu.cn/csuoj/problemset/problem?pid=1550

很久以前做的一题，当时队友用最大流做，现在我也是

这个转化为二分图多重匹配，就是一样的意思了。

设出一个原点S，两个人1,和2，S-->1的流量是n表明只能流出n个字母，s-->2的流量是n，一样含义。

然后再设一个汇点T，表明需要有多少流进来，跑一发就好。

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;
const int maxn = 100000 * 2;
struct Edge {
    int u, v, w, tonext;
    int id;
}e[maxn * 2];
int first[maxn], num;
void addEdge(int u, int v, int w) {
    e[num].u = u, e[num].v = v, e[num].w = w, e[num].tonext = first[u], e[num].id = num;
    first[u] = num++;
}
int flow[maxn], pre[maxn];
int bfs(int be, int en) { //O(n * E * E)
    queue<int> que;
    memset(flow, false, sizeof flow);
    pre[be] = -1, flow[be] = inf;
    que.push(be);
    while (!que.empty()) {
        int cur = que.front();
        que.pop();
        for (int i = first[cur]; ~i; i = e[i].tonext) {
            int v = e[i].v;
            if (flow[v] == 0 && e[i].w > 0) {
                pre[v] = e[i].id;
                flow[v] = min(flow[cur], e[i].w);
                que.push(v);
            }
        }
        if (flow[en]) break; //找到了增广路
    }
    if (flow[en] == 0) return -1;
    else return flow[en];
}

int maxFlow(int be, int en) {
    int sumFlow = 0;
    while (true) {
        int res = bfs(be, en);
        if (res == -1) { //找不到增广路
            break;
        }
        int edgeID = pre[en];
        while (edgeID != -1) {
            e[edgeID].w -= res;
            e[edgeID ^ 1].w += res;
            edgeID = pre[e[edgeID].u];
        }
        sumFlow += res;
    }
    return sumFlow;
}
char s1[maxn], s2[maxn], s3[maxn];
int cnt1[222], cnt2[222], cnt3[222];
void work() {
    memset(cnt1, 0, sizeof cnt1);
    memset(cnt2, 0, sizeof cnt2);
    memset(cnt3, 0, sizeof cnt3);
    memset(first, -1, sizeof first);
    num = 0;
    int lenstr = strlen(s1 + 1);
    addEdge(0, 1, lenstr / 2);
    addEdge(1, 0, 0);
    addEdge(0, 2, lenstr / 2);
    addEdge(2, 0, 0);
    for (int i = 1; i <= lenstr; ++i) {
        cnt1[s1[i]]++;
        cnt2[s2[i]]++;
        cnt3[s3[i]]++;
    }
    for (int i = 'A'; i <= 'Z'; ++i) {
        addEdge(1, i - 'A' + 3, cnt1[i]);
        addEdge(i - 'A' + 3, 1, 0);
        addEdge(2, i - 'A' + 3, cnt2[i]);
        addEdge(i - 'A' + 3, 2, cnt2[i]);
    }
    for (int i = 'A'; i <= 'Z'; ++i) {
        addEdge(i - 'A' + 3, 29, cnt3[i]);
        addEdge(29, i - 'A' + 3, 0);
    }
    int res = maxFlow(0, 29);
    if (res == lenstr) {
        printf("YES
");
    } else printf("NO
");
}

int main() {
#ifdef local
    freopen("data.txt", "r", stdin);
//    freopen("data.txt", "w", stdout);
#endif
    while (scanf("%s%s%s", s1 + 1, s2 + 1, s3 + 1) > 0) work();
    return 0;
}

View Code

1550: Simple String 最大流解法

相关推荐