当前位置: 首页 > news >正文

建个企业网站静态网站首页更新

建个企业网站,静态网站首页更新,海口网站建设发布,国产做爰全免费的视频网站正题 题目链接: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; }
http://www.huolong8.cn/news/307479/

相关文章:

  • 网站建站要多少钱邯郸人才网官网
  • 免费网站制作教程上海未成年人思想道德建设网站
  • 免费婚纱网站模板无锡网站排名推广
  • 网站建设拟解决问题天津关键词排名推广
  • 如何知道网站什么时候做的建设银行浙江网站
  • 做网站网络合同郑州发布评论
  • 团购机票网站建设网站建设项目付款方式
  • 网站检测报告哪里做网页登录
  • 一个人的网站建设制作网页的基本技术标准
  • 怎样克隆别人的网站网站推广服务网
  • 网站开发的检索速度在啥范围之内wordpress如何网址大全
  • 北京 网站制作wordpress经典编辑器
  • 济南做网站网站模板下载好之后如何安装
  • wordpress怎么加js文件赤城seo网站优化排名
  • 网站改版准备哈尔滨app开发
  • 常德地区网站建设百度提交入口怎么用
  • 一个网站同时做百度和360 百度商桥都可以接收客户信息吗个人网站设计实验原理
  • 网站文件命名规则荥阳市建设局网站
  • 笔记本做网站服务器无忧网站优化
  • 网站必须做百度推广才能被别人搜到吗顺义企业建站费用
  • 做影视网站的软件网站设计师待遇
  • 高端网站设计 新鸿儒自己做的网站怎么上传到网络
  • 个人网站主题深圳市做网站
  • c asp.net网站开发书企业管理软件下载
  • 网站建设需要注意什么 知乎滑县网站建设服务
  • 移动版wordpress优化方案英语答案
  • 网站开发为什么需要团队完成增加网站关键词库
  • 源码 网站建设教程湖北十堰了不得科技网络公司
  • 酒店网站开发使用h5做的学习网站源码
  • 呼和浩特整站优化网站关键词优化系统