Deleting Edges

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)

Total Submission(s): 263    Accepted Submission(s): 85

Problem Description

Little Q is crazy about graph theory, and now he creates a game about graphs and trees.

There is a bi-directional graph with 

n nodes, labeled from 0 to 

n−1. Every edge has its length, which is a positive integer ranged from 1 to 9.

Now, Little Q wants to delete some edges (or delete nothing) in the graph to get a new graph, which satisfies the following requirements:

(1) The new graph is a tree with 

n−1 edges.

(2) For every vertice 

v(0<v<n), the distance between 0 and 

v on the tree is equal to the length of shortest path from 0 to 

v in the original graph.

Little Q wonders the number of ways to delete edges to get such a satisfied graph. If there exists an edge between two nodes 

i and 

j, while in another graph there isn't such edge, then we regard the two graphs different.

Since the answer may be very large, please print the answer modulo 

109+7.

 

Input

The input contains several test cases, no more than 10 test cases.

In each test case, the first line contains an integer 

n(1≤n≤50), denoting the number of nodes in the graph.

In the following 

n lines, every line contains a string with 

n characters. These strings describes the adjacency matrix of the graph. Suppose the 

j-th number of the 

i-th line is 

c(0≤c≤9), if 

c is a positive integer, there is an edge between 

i and 

j with length of 

c, if 

c=0, then there isn't any edge between 

i and 

j.

The input data ensure that the 

i-th number of the 

i-th line is always 0, and the 

j-th number of the 

i-th line is always equal to the 

i-th number of the 

j-th line.

 

Output

For each test case, print a single line containing a single integer, denoting the answer modulo 

109+7.

 

Sample Input

2 01 10 4 0123 1012 2101 3210

 

Sample Output

1 6

 

Source

 

题意：

n个点，n*2-n条边，删除掉只剩下n-1条边，满住剩下的每个点在原图中都是最短路的存在。

分析：

dij队列优化需要vis，可以避免重复入队的情况，但是不加vis也不会无尽循环下去。

来自某个博客其他人的解法，其实也不需要跑完全图。

说入度乘积我更倾向于说成每个点走法的乘积。（5.15重温这句话发现这句话还是有问题的，到三点的还有一种画法）

dij算法就是求原点到各个点的最短路，也很贴合这道题的性质。那么不同走法之间会有影响吗？只有两个独立事件同时发生没有影响才能相乘。（有问题）

结果是没有影响。原题中说只要存在任意一条不同的边就是不同的图。

dij最短路的原理就是通过不同路来松弛。每种走法的组合一定可以存在一条异边。第三个点也是建立在前面点基础上通过扩展而来。

因为n为50，所以随便哪个最短路算法都能过吧：

正插邻接表加队列的确比反插好写多了。。。

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #define mod 1000000007using namespace std;typedef long long ll;const int maxn = 100+10;const int INF = 0x3f3f3f3f;char ch[60][60];int cnt[maxn];struct node{    int x,d;    node(){}    node(int a,int b){x=a;d=b;}    bool operator < (const node & a) const    {        return d > a.d;    }};vector
         
           eg[maxn];int dis[maxn];void Dijkstra(int s){ dis[s]=0; //用优先队列优化 priority_queue
          
            q; q.push(node(s,dis[s])); while(!q.empty()) { node x=q.top();q.pop(); //最后一个点就可以跳出了 if(x.x==n-1) break; for(int i=0;i
           
            x.d+y.d) { cnt[y.x] = 1; dis[y.x]=x.d+y.d; q.push(node(y.x,dis[y.x])); } else if(dis[y.x]==x.d+y.d) { cnt[y.x]++; } } }}int main(){// freopen("in.txt","r",stdin); int n; while(~scanf("%d",&n)) { for(int i=0;i<=n;i++) dis[i]=INF; memset(cnt,0,sizeof(cnt)); cnt[0]=1; for(int i=0;i<=n;i++) eg[i].clear(); for(int i=0;i
           
          
         
        
       
      
     
    

一开始超时的，不知道在哪里：

反正以后就用vector写了。。。。

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include