由于Acb0y的rp很低，导致每次都被mm拒之门外，因此今天他想先涨涨rp再行动。于是他挑了n家店，例如理发店、美容店、礼品店等，编号为1-n，每当他经过一家店的时候就能增加一定的rp值，且每家店最多只能经过一次。此外他还挑选了m条可供行走的路线(单向的)。起始时Acb0y在校门口(编号为0)，他的目的地是ACM实验室(编号为n+1)，你能帮我们的老队长算一下他今天rp最大可以涨到多少么(起始rp为0)？
图

Input

  每个输入文件的第一行有两个整数n和m(0< n<= 30,0< m<= 100)，第二行里有n个整数di(1 <= i<= n)表示经过店i可以涨di点的rp值(0<= di<= 100)。再接下来有m行，每行有两个整数a b表示从a可以走到b(0<=a,b<=n+1)。

Output

  对于每个输入文件，输出Acb0y能够涨到的最大rp值。

Sample Input


3 5
5 2 2
0 1
0 2
1 4
2 3
3 4


Sample Output


5

Hint

两点之间可能有多条边，且中可能存在环。

每个输入文件的第一行有两个整数n和m(0< n<= 。。。。
从这边开始就看不明白了

哪里的ACM ？

#include <stdio.h>

#define MAX_NODES    30

int n;
int max_rp;
int RP[MAX_NODES + 1];
char MAP[MAX_NODES + 2][MAX_NODES + 2];

void Calculate(int node, int rp)
{
    static char path[MAX_NODES + 2];
    int i;
    if(node == n + 1)
    {
        if(max_rp < rp) max_rp = rp;
    }
    for(i = 0; i <= n + 1; i++)
    {
        if(MAP[node][i] == 1 && path[i] == 0)
        {
            path[i] = 1;
            Calculate(i, rp + RP[i]);
            path[i] = 0;
        }
    }
}

int main()
{
    int i, m, f, t;
    scanf("%d%d", &n, &m);
    for(i = 0; i < n; i++)
        scanf("%d", RP + i + 1);
    for(i = 0; i < m; i++)
    {
        scanf("%d%d", &f, &t);
        MAP[f][t] = 1;
    }
    Calculate(0, 0);
    printf("%d\n", max_rp);
    return 0;
}

请问path[i]数组的作用是什么？

不行啊，当测试数据变为
4 6
5 2 2 2
0 1
0 2
1 4
1 3
2 3
3 4
结果就会变成0啊

结果是正确的。是你的数据有问题。
你将中间结点变成了4个，那起始结点标号为0， 终点标号为5。而你给的边里没有能到达终点的边，也就是从起点到终点没有通路。所以结果为0。

请问path[i]数组的作用是什么？ 没看明白呢~~~~

path用于记录已经经过的结点，保证每个结点只经过一次，防止陷入环中。

我中间节点没有变啊，我只是增加了一条从三到四的路，这样最大就会变成5+2等于七了啊

你再仔细阅读一下你题中关于输入数据格式的描述。
你增加的是从一到三的边，不是从三到四的。正确的格式应该是这样：
3 6
5 2 2
0 1
0 2
1 4
1 3
2 3
3 4