建个企业网站,静态网站首页更新,海口网站建设发布,国产做爰全免费的视频网站正题
题目链接:https://loj.ac/p/3026 题目大意
给出nnn个点的一棵外向树#xff0c;然后mmm个字符串和费用表示你每次可以花费这个费用覆盖路径字符串和给出字符串相等的路径#xff0c;求覆盖所有边的最小花费#xff08;可以重复覆盖#xff09;
输出方案 1≤n≤500,…正题
题目链接:https://loj.ac/p/3026 题目大意
给出nnn个点的一棵外向树然后mmm个字符串和费用表示你每次可以花费这个费用覆盖路径字符串和给出字符串相等的路径求覆盖所有边的最小花费可以重复覆盖
输出方案
1≤n≤500,1≤m≤105,∑∣S∣≤1061\leq n\leq 500,1\leq m\leq10^5,\sum |S|\leq 10^61≤n≤500,1≤m≤105,∑∣S∣≤106 解题思路
注意到nnn很小可以考虑枚举计算所有路径的最小花费先构一个TrieTrieTrie即可处理这部分。
然后考虑怎么覆盖的问题和[NOI2008] 志愿者招募类似的我们可以通过边调走流来实现覆盖问题。
先原点向每一个叶子连流量为1的边设sizxsiz_xsizx表示xxx的子树中有多少个叶子那么xxx向faxfa_xfax连接流量为sizx−1siz_x-1sizx−1的边然后根向汇点连流量为siz1siz_1siz1的边。
这样就保证了每条边都至少有一个流量被调走但是需要考虑单链上的重复覆盖所以还需要每个点向儿子连无向流量的边。 code
#includecstdio
#includecstring
#includealgorithm
#includequeue
#define ll long long
using namespace std;
const ll N510,M1e610;
struct node{ll to,next,w;
}a[N];
ll n,m,t,tot,ans,MF,ls[N],siz[N],fa[N];
ll cnt,ch[M][26],cost[M],fail[M],mark[M];
queueint q;char s[M];
void addl(ll x,ll y,ll w){a[tot].toy;a[tot].nextls[x];ls[x]tot;a[tot].ww;return;
}
void Insert(char *s,ll val,ll num){ll x1,mstrlen(s);for(ll i0;im;i){ll cs[i]-a;if(!ch[x][c])ch[x][c]cnt;xch[x][c];}if(cost[x]val)cost[x]val,mark[x]num;return;
}
void GetFail(){for(ll i0;i26;i)q.push(ch[1][i]);while(!q.empty()){ll xq.front();for(ll i0;i26;i){if(!ch[x][i])ch[x][i]ch[fail[x]][i];else{fail[ch[x][i]]ch[fail[x]][i];q.push(ch[x][i]);}}}return;
}
namespace NF{struct node{ll to,next,w,c,typ;}a[N*N];ll tot1,s,t,ls[N],f[N],mf[N],pre[N];bool v[N];void addl(ll x,ll y,ll w,ll c,ll mk){a[tot].toy;a[tot].nextls[x];ls[x]tot;a[tot].ww;a[tot].cc;//a[tot].typmk;a[tot].tox;a[tot].nextls[y];ls[y]tot;a[tot].w0;a[tot].c-c;a[tot].typmk;return;}bool SPFA(){memset(f,0x3f,sizeof(f));q.push(s);v[s]1;f[s]0;mf[s]f[0];mf[t]0;while(!q.empty()){ll xq.front();v[x]0;q.pop();for(ll ils[x];i;ia[i].next){ll ya[i].to;if(a[i].wf[x]a[i].cf[y]){f[y]f[x]a[i].c;pre[y]i;mf[y]min(mf[x],a[i].w);if(!v[y])v[y]1,q.push(y);}}}return mf[t];}void Updata(){ll xt;ansmf[t]*f[t];MFmf[t];while(x!s){a[pre[x]].w-mf[t];a[pre[x]^1].wmf[t];xa[pre[x]^1].to;}return;}void GetAns(){while(SPFA())Updata();return;}void Print(){ll sum0;for(ll i2;itot;i)if(a[i].typ)suma[i].w;printf(%lld\n,sum);for(ll i2;itot;i)if(a[i].typ){while(a[i].w)printf(%lld %lld %lld\n,a[i^1].to,a[i].to,a[i].typ),a[i].w--;}}
}
void calc(ll x,ll p,ll s){if(!p)return;if(cost[p]1e9)NF::addl(x,s,n,cost[p],mark[p]);for(ll ils[x];i;ia[i].next)calc(a[i].to,ch[p][a[i].w],s);return;
}
void solve(ll x){siz[x](!ls[x]);if(!ls[x])NF::addl(NF::s,x,1,0,0);calc(x,1,x);for(ll ils[x];i;ia[i].next){NF::addl(x,a[i].to,n,0,0);solve(a[i].to),siz[x]siz[a[i].to];}if(fa[x]siz[x]1)NF::addl(x,fa[x],siz[x]-1,0,0);return;
}
signed main()
{memset(cost,0x3f,sizeof(cost));scanf(%lld%lld%lld,n,m,t);for(ll i2;in;i){ll x;char op[3];scanf(%lld%s,fa[i],op);addl(fa[i],i,op[0]-a);}cnt1;for(ll i1;im;i){ll c;scanf(%lld%s,c,s);Insert(s,c,i);}NF::sn1;NF::tn2;solve(1);NF::addl(1,NF::t,siz[1],0,0);NF::GetAns();if(MF!siz[1])return puts(-1)0;printf(%lld\n,ans);if(t)NF::Print();return 0;
}