题目描述

       在A，B两个城市之间蛇油N个路站（如图中的S1，且N≤10），城市与路站之间、路站和路站之间各有若干条路段（各路段数≤10，且每条路段上的距离均为一个整数）。A，B的一条通路是指：从A出发，可经过任一路段到达S1，再从S1出发经过任一路段......最后到达B。通路上路段距离之和称为通路距离（最大距离≤1000）。当所有的路段距离给出之后，求出所有不同距离的通路个数。（相同距离仅记一次）。例如，图中所示是当N=1时的情况。

        从A到B的通路条数为6，但因其中通路5+5=4+6，所以满足条件的不同距离的通路条数为5。

 

输入输出格式

输入格式

        第一行一个整数n，代表从A到第一个路站；第二行为到第一个路站的通路条数r；

        随后的r行代表从A到第一个路站，每一条通路的通路距离；

        如此类推。详情参考输入样例。

 

输出格式

        一行，为满足条件的不同距离的通路条数。

 

输入输出样例

输入样例

1

3 //从A到第一个路站有3条通路

5

7

4

2 //第一个路站到B有2条通路

6

5

 

输出样例

5

 

题解

         暴力枚举每两个车站之间的通道，去重即可。（话说这种枚举方式好像叫二进制枚举）

#include <iostream>

using namespace std;

int n;
int tmp;
int road[15][15];
int stop[15];
int snum[15] = {1};
int differ[1005];
int ans;

int main()
{
    cin >> n;
    ++n;
    for(register int i = 1; i <=n; ++i)
    {
        cin >> snum[i];
        for(register int j = 1; j <= snum[i]; ++j)
        {
            cin >> road[i][j];
        }
    }
    for(register int i = 1; i <= n; ++i)
    {
        tmp += road[i][1];
        stop[i] = 1;
    }
    
    while(!stop[0])
    {
        if(!differ[tmp])
        {
            ++ans;
            differ[tmp]=1;
        }
        tmp -= road[n][stop[n]];
        tmp += road[n][++stop[n]];
        for(register int i = n; i; --i)
        {
            if(stop[i] > snum[i])
            {
                stop[i] = 1;
                tmp += road[i][stop[i]];
                tmp -= road[i - 1][stop[i - 1]];
                tmp += road[i - 1][++stop[i - 1]];
            }
            else break;
        }
    }
    cout << ans;
    return 0;
}

参考程序