首页 > 代码库 > 1550: Simple String 最大流解法
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\n"); } else printf("NO\n"); } 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; }
1550: Simple String 最大流解法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。