F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Notice:1:注册本OJ方式请见https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671 2:请不要在讨论区中发空白主题帖。
Problem 5056. -- OI游戏

5056: OI游戏

Time Limit: 1 Sec  Memory Limit: 64 MB
Submit: 369  Solved: 222
[Submit][Status][Discuss]

Description

小Van的CP最喜欢玩与OI有关的游戏啦~小Van为了讨好她,于是冥思苦想,终于创造了一个新游戏。
下面是小Van的OI游戏规则:
给定一个无向连通图,有N个节点,编号为0~N-1。图里的每一条边都有一个正整数权值,边权在1~9之间。
要求从图里删掉某些边(有可能0条),使得剩下的图满足以下两个条件:
1) 剩下的图是一棵树,有N-1条边。
2) 对于所有v (0 < v < N),0到v的最短路(也就是树中唯一路径长度)和原图中的最短路长度相同。
最终要报出有多少种不同的删法可以满足上述条件。(两种删法不同当且仅当存在两个点,
一种删法删完之后这两个点之间存在边而另外一种删法不存在。)
由于答案有可能非常大,良心的小Van只需要答案膜1,000,000,007的结果。
后记: 然而这游戏太高难度了,小Van的CP做不出来因此很不开心!
她认为小Van在故意刁难她,于是她与小Van分手了。。。
不过对于精通OI的你来说,这不过是小菜一碟啦!

Input

第一行一个整数N,代表原图结点。
接下来N行,每行N个字符,描绘了一个邻接矩阵。邻接矩阵中,
如果某一个元素为0,代表这两个点之间不存在边,
并且保证第i行第i列的元素为0,第i行第j列的元素(i≠j)等于第j行第i列的元素。
2≤N≤50

Output

一行一个整数,代表删法总方案数膜1,000,000,007的结果。

Sample Input

Input1
2
01
10


Input2
4
0123
1012
2101
3210

Sample Output

Output1
1
Output2
6

HINT

Source

By 佚名上传

[Submit][Status][Discuss]

HOME Back