【Trie】【费用流】管道监控（loj 3026）

本文主要是介绍【Trie】【费用流】管道监控（loj 3026），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

正题

loj 3026

题目大意

给你一棵树，和若干匹配串，如果一个节点向下的某条链构成了匹配串i，则可以花费这w_i匹配这条链，问你匹配完所有点的最小代价

解题思路

这题可以理解为树上树上的线性规划

先对于每个匹配串倒着建trie，然后每个点向父亲跑trie，当跑到一个匹配串时，就连接头和尾，费用为 $w_i$ ，流量inf

然后每个点向子节点连流量inf费用0的边

s向叶子节点连流量1费用0的边，如果一个点的子节点大于1就把多余的流到t，1要把所有流量流到t

就在树上找到匹配串，然后就是经典的线性规划

代码

#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define N 510
#define M 1000100
using namespace std;
ll n, m, T, x, s, t, w, tot, ans, sum, summ;
ll h[N], f[N], b[N], fr[N], fa[N], deg[N], v[M], wh[M], to[M][26];
char cl[N], st[M];
bool p[N];
queue<ll>d;
const ll inf = 1e15;
struct rec
{ll to, next, f, w, c;
}e[N*N<<2];
void add(ll x, ll y, ll f, ll c, ll w)
{e[++tot].to = y;e[tot].f = f;e[tot].w = w;//编号e[tot].c = c;e[tot].next = h[x];h[x] = tot;e[++tot].to = x;e[tot].f = 0;e[tot].w = 0;e[tot].c = -c;e[tot].next = h[y];h[y] = tot;return;
}
void insert(ll x, char* s, ll whi)
{ll now = 0, len = strlen(s+1);for (ll i = len; i > 0; --i){ll y = s[i] - 97;if (!to[now][y]) to[now][y] = ++w;now = to[now][y];}if (!v[now] || x < v[now]){v[now] = x;wh[now] = whi;}return;
}
void dfs(ll x)
{ll now = 0;for (ll i = x; i != 1; i = fa[i]){ll y = cl[i] - 97;if (!to[now][y]) break;now = to[now][y];if (v[now]) add(x, fa[i], inf, v[now], wh[now]);}return;
}
bool spfa()
{memset(b, 127/3, sizeof(b));memset(f, 0, sizeof(f));memset(p, 0, sizeof(p));while(!d.empty()) d.pop();d.push(s);p[s] = 1;b[s] = 0;f[s] = inf;while(!d.empty()){ll u = d.front();d.pop();for (ll i = h[u]; i; i = e[i].next){ll v = e[i].to;if (b[u] + e[i].c < b[v] && e[i].f){fr[v] = i;b[v] = b[u] + e[i].c;f[v] = min(f[u], e[i].f);if (!p[v]){p[v] = 1;d.push(v);}}}p[u] = 0;}return f[t];
}
void dfs()
{ll now = t;while(fr[now]){e[fr[now]].f -= f[t];e[fr[now]^1].f += f[t];now = e[fr[now]^1].to;}ans += f[t] * b[t];sum += f[t];return;
}
int main()
{scanf("%lld%lld%lld", &n, &m, &T);tot = 1;for (ll i = 2; i <= n; ++i){scanf("%lld", &x);fa[i] = x;add(x, i, inf, 0, 0);deg[x]++; cl[i] = getchar();while(cl[i] < 'a' || 'z' < cl[i]) cl[i] = getchar();}s = n + 1;t = n + 2;for (ll i = 1; i <= m; ++i){scanf("%lld%s", &x, st+1);insert(x, st, i);}for (ll i = 2; i <= n; ++i){dfs(i);if (!deg[i]) add(s, i, 1, 0, 0);else if (deg[i] > 1){add(i, t, deg[i] - 1, 0, 0);//多的流掉summ += deg[i] - 1;//计算理论总流量}}add(1, t, deg[1], 0, 0);summ += deg[1];while(spfa())dfs();if (sum < summ)//有的边到不了{puts("-1");return 0;}printf("%lld\n", ans);if (T){ans = 0;for (ll i = 2; i <= n; ++i)for (ll j = h[i]; j; j = e[j].next)if (e[j].w && e[j].f < inf)//输出方案ans++;printf("%lld\n", ans);for (ll i = 2; i <= n; ++i)for (ll j = h[i]; j; j = e[j].next)if (e[j].w && e[j].f < inf)printf("%lld %lld %lld\n", e[j].to, i, e[j].w);}return 0;
}