正題

題目鏈接:https://loj.ac/p/3026

---

題目大意

給出$n$個點的一棵外向樹，然后$m$個字符串和費用表示你每次可以花費這個費用覆蓋路徑字符串和給出字符串相等的路徑，求覆蓋所有邊的最小花費（可以重復覆蓋）

輸出方案

$1\le n\le 500,1\le m\le 10^5,\sum |S|\le 10^6$

---

解題思路

注意到$n$很小，可以考慮枚舉計算所有路徑的最小花費，先構一個$Trie$即可處理這部分。

然后考慮怎么覆蓋的問題，和[NOI2008] 志愿者招募類似的，我們可以通過邊調走流來實現覆蓋問題。

先原點向每一個葉子連流量為1的邊，設$si{z}_x$表示$x$的子樹中有多少個葉子那么$x$向$f{a}_x$連接流量為$si{z}_x?1$的邊，然后根向匯點連流量為$si{z}_1$的邊。

這樣就保證了每條邊都至少有一個流量被調走，但是需要考慮單鏈上的重復覆蓋所以還需要每個點向兒子連無向流量的邊。

---

code

#include<cstdio> #include<cstring> #include<algorithm> #include<queue> #define ll long long using namespace std; const ll N=510,M=1e6+10; 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]; queue<int> q;char s[M]; void addl(ll x,ll y,ll w){a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;a[tot].w=w;return; } void Insert(char *s,ll val,ll num){ll x=1,m=strlen(s);for(ll i=0;i<m;i++){ll c=s[i]-'a';if(!ch[x][c])ch[x][c]=++cnt;x=ch[x][c];}if(cost[x]>val)cost[x]=val,mark[x]=num;return; } void GetFail(){for(ll i=0;i<26;i++)q.push(ch[1][i]);while(!q.empty()){ll x=q.front();for(ll i=0;i<26;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 tot=1,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].to=y;a[tot].next=ls[x];ls[x]=tot;a[tot].w=w;a[tot].c=c;//a[tot].typ=mk;a[++tot].to=x;a[tot].next=ls[y];ls[y]=tot;a[tot].w=0;a[tot].c=-c;a[tot].typ=mk;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 x=q.front();v[x]=0;q.pop();for(ll i=ls[x];i;i=a[i].next){ll y=a[i].to;if(a[i].w&&f[x]+a[i].c<f[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 x=t;ans+=mf[t]*f[t];MF+=mf[t];while(x!=s){a[pre[x]].w-=mf[t];a[pre[x]^1].w+=mf[t];x=a[pre[x]^1].to;}return;}void GetAns(){while(SPFA())Updata();return;}void Print(){ll sum=0;for(ll i=2;i<=tot;i++)if(a[i].typ)sum+=a[i].w;printf("%lld\n",sum);for(ll i=2;i<=tot;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 i=ls[x];i;i=a[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 i=ls[x];i;i=a[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 i=2;i<=n;i++){ll x;char op[3];scanf("%lld%s",&fa[i],op);addl(fa[i],i,op[0]-'a');}cnt=1;for(ll i=1;i<=m;i++){ll c;scanf("%lld%s",&c,s);Insert(s,c,i);}NF::s=n+1;NF::t=n+2;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; }

總結

以上是生活随笔為你收集整理的Loj#3026-「ROIR 2018 Day1」管道监控【Trie,费用流】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。