UVa 988 - Many Paths, One Destination

称号：生命是非常多的选择。现在给你一些选择（0~n-1），和其他选项后，分支数每一次选择，选择共求。

分析：dp，图论。假设一个状态也许是选择的数量0一个是，代表死亡，计数的路径数将达到所有死亡可以去除。

用一个状态数组记录到达每一个选择的路径数，它等于能到达它的前驱节点的路径加和。

稀疏图，使用邻接表储存。初始是节点0的路径条数为1。代表出生。

说明：没有给数据范围略坑啊，RE一次。WA一次。╮(╯▽╰)╭。

#include <iostream>

#include <cstdlib>

#include <cstring>

#include <cstdio>

using namespace std;

int sums[15000];

int deat[15000];

typedef struct tnode

{

	int    point;

	tnode *next;

}node;

node* H[15000];

node  E[150000];

int   e_size = 0;

void initial()

{

	memset( H, 0, sizeof(H) );

	memset( E, 0, sizeof(E) );

	e_size = 0;

}

void addedge( int a, int b )

{

	E[e_size].point = b;

	E[e_size].next = H[a];

	H[a] = &E[e_size ++];

}

int main()

{

	int n,m,c,t = 1;

	while ( ~scanf("%d",&n) ) {

		if ( t ++ > 1 ) printf("\n");

		initial();

		memset( sums, 0, sizeof(sums) );

		for ( int i = 0 ; i < n ; ++ i ) {

			scanf("%d",&m);

			for ( int j = 0 ; j < m ; ++ j ) {

				scanf("%d",&c);

				addedge( i, c );

			}

			if ( !m ) deat[i] = 1;

			else deat[i] = 0;

		}

		sums[0] = 1;

		for ( int i = 0 ; i < n ; ++ i )

		for ( node* p = H[i] ; p ; p = p->next )

			sums[p->point] += sums[i];

		int sum = 0;

		for ( int i = 1 ; i < n ; ++ i )

			if ( deat[i] )

				sum += sums[i];

		printf("%d\n",sum);

	}

	return 0;

}