1.2 讨厌的新系统（难度：★★☆☆☆）_国际大学生程序设计竞赛例题解（八）-QQ阅读男生都市网

上QQ阅读APP看本书，新人免费读10天

设备和账号都新为新人

1.2 讨厌的新系统（难度：★★☆☆☆）

1.2.1 试题

题目描述

前几天，“较硬”公司推出了新的操作系统Swodniw vista。于是，小恒便高高兴兴地将它买了回来，并给自己的计算机装上了。结果他却发现许多软件和程序的运行速度都慢了很多，和以前的操作系统相比，简直就是天壤之别。后来小恒发现，原来是新系统的UAC保护模式在作怪。

UAC保护模式其实是一个用户权限检测系统。每当用户执行一条操作，UAC都会花上若干时间来检测合法性。UAC将检测分成了N个模块，每个模块的执行顺序严格按照一个有向树拓扑有序，如图1.2.1所示。

图1.2.1 UAC模块的执行顺序拓扑关系

一个模块包含两个属性，匹配串S和检测时间C。现在，对一个操作串T，当一个模块的S包含了T中的若干个字符，则必须执行该模块。要注意，各个模块是可以同时执行的。

比如，对操作序列“BE”，则执行了A、B、C、D、E五个模块，最少花费时间为6（1+3+2）。

现在给出M个操作串，那么UAC完成每个串的检测最少需要多少时间呢？

输入格式

第1行为两个整数N和M（N≤2007, M≤100000），N表示检测个数，M表示操作串个数。

接下来N行，每行包含非负整数F，C（C≤1000）和一个字符串S（长度≤100），分别表示前继模块的序号，检测时间和匹配串。模块由1到N编号，根的前继为0。

再下来M行，每行只有一个字符串（长度≤100），表示需要检测的操作串。

字符串中不包括空格、换行符和所有的控制字符。

输出格式

有M行，每行包含一个整数，表示最少检测时间。

输入样例1

6 2

0 1 ABCDEF

1 3 ABC

2 2 BC

1 1 DEF

4 1 D

1 4 AEF

输出样例1

输入样例2

3 2

0 0 0

1 1 1

2 2 0

输出样例2

1.2.2 题目分析和算法实现

本题是一道简单的图论题。题目意思就是给出一棵有向树，求出一条符合条件的最长路。

实际上可以非常容易地发现，只要由根节点出发的一条最长路的尾节点包含给出的操作串中的某个字符，就符合条件了。于是顺着思路想下去，一个节点能不能达到，只和里面的字符有关，所以可以立刻想到预处理每一个字符所能使操作串达到的最远距离。通过预处理后，就可以扫描每一个操作串，求出其中每个字符能达到最远距离的最大值，从而在O（m*len）复杂度下解决这个问题。

预处理实际上很简单。从根节点开始遍历这棵树，求出由根节点到达每一个节点v的距离W（v）。检索所有节点的所有字符，假设节点v包含字符c，则更新字符c的最远距离cost（c）=max{cost（c）,W（v）}。预处理最好在O（n*len）下完成。

数据上并没有过多的“陷阱”，可能会有空串。对于Pascal的编程者而言不会有大问题，直接readln（f, c, s）就可以了。

1.2.3 参考程序及程序分析

#include ＜stdio.h＞
#include ＜string.h＞
const int maxn=2010,maxlen=110;         //最大顶点数，最大字符串长度
int f[maxn],c[maxn],root,cpc[260],n,m;
//前继序号，检测时间，根节点，字符在串中的最远距离，顶点数，询问数
char s[maxn][maxlen],ss[maxlen];        //原匹配串，要检测的操作串
void search(int w)                      //递归算出到达每个顶点所需的检测时间
{
    int i;
    for (i=1;i＜=n;++i)
        if (f[i]==w)                    //该点前继为w
        {
            c[i]+=c[w];                 //累加检测时间
            search(i);                  //递归计算
        }
}
void init()                             //预处理每一个字符所能使操作串达到的最远距离
{
    int i,j;
    memset(cpc,0,sizeof(cpc));          //清零
    search(root);                       //递归算出root到达每个顶点所需的检测时间
    for (i=1;i＜=n;++i)
        for (j=1;s[i][j];++j)
            if (cpc[s[i][j]]＜c[i])     //取最远距离
                cpc[s[i][j]]=c[i];
}
int main()
{
    freopen("vista.in","r",stdin);      //输入文件
    freopen("vista.out","w",stdout);    //输出文件
    int i,j,ans;
    scanf("%d%d",&n,&m);                //输入顶点数，询问操作串数
    for (i=1;i＜=n;++i)
    {
        scanf("%d%d",&f[i],&c[i]);      //读入前继模块序号，检测时间
        if (f[i]==0) root=i;            //根前继为0
        gets(s[i]);                     //读入匹配串
    }
    init();                             //预处理for (i=0;i＜m;++i)
    {
        gets(ss);                       //读入待检测的操作串
        ans=0;
        for (j=0;ss[j];++j)             //对于每个字符查找最远的距离
            if (cpc[ss[j]]＞ans) ans=cpc[ss[j]];
        printf("%d\n",ans);             //输出答案
    }
    return 0;
}

1.2.4 部分测试数据和输出结果

测试数据

10 10

0 10 /N5c7\/V;0

1 23 C

1 1 {fdcgyv+1X∶PVc?Xft=

2 25 vUom＊

1 20 C

5 4 \872+s4YIai

1 30 air3D@oF

6 43 zH;

2 23 ＜

5 20 {#

\$&`#vH;#,!E-1oGd?avaPnJ?C+Osf))＜4＜k/

aK+

[o%Q;1uN4

ERc&∧&t_np＜(yP]pI5Z$9rH∧?2,zcy;v

1|q76＜uP8r5bKEP{Wn1e\Ke[Yoc')PZ87H`!mrU[PU}9[O

∧gSCM;/1Jj/fl$5＊R＊{bQp∶0Hf$oz%z1Oh.-

t@7b?|#,C-;-#P(}mqDsDlwO26e"Px∧x"U&k,M

0(?;J∶＊#8＜aHlG!&-te}01k."r

Vwx∧6B8|'A]C

jS6".htG.L]O#vI

输出结果