基础型网站套餐,网站建设南京公司,wordpress js跳转,开发一个软件需要多久正题
loj 3026 题目大意
给你一棵树#xff0c;和若干匹配串#xff0c;如果一个节点向下的某条链构成了匹配串i#xff0c;则可以花费这w_i匹配这条链#xff0c;问你匹配完所有点的最小代价 解题思路
这题可以理解为树上树上的线性规划
先对于每个匹配串倒着建trie和若干匹配串如果一个节点向下的某条链构成了匹配串i则可以花费这w_i匹配这条链问你匹配完所有点的最小代价 解题思路
这题可以理解为树上树上的线性规划
先对于每个匹配串倒着建trie然后每个点向父亲跑trie当跑到一个匹配串时就连接头和尾费用为wiw_iwi流量inf
然后每个点向子节点连流量inf费用0的边
s向叶子节点连流量1费用0的边如果一个点的子节点大于1就把多余的流到t1要把所有流量流到t
就在树上找到匹配串然后就是经典的线性规划 代码
#includequeue
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#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];
queuelld;
const ll inf 1e15;
struct rec
{ll to, next, f, w, c;
}e[N*N2];
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(s1);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, st1);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;
}
