JZOJ 1243. TreeCount

题目

Description

给出一个有N(2<=N<=1000)个顶点M(N-1<=M<=N*(N-1)/2)条边的无向连通图。设dist1[i]表示在这个无向连通图中，顶点i到顶点1的最短距离。
现在要求你在这个图中删除M-(N-1)条边，使得这个图变成一棵树。设dist2[i]表示在这棵树中，顶点i到顶点1的距离。
你的任务是求出有多少种删除方案，使得对于任意的i，满足dist1[i]=dist2[i]。

Input

第一行，两个整数，N，M，表示有N个顶点和M条边。
接下来有M行，每行有3个整数，表示顶点x和顶点y有一条长度为len的边。数据保证不出现自环、重边。

Output

输出一个整数，表示满足条件的方案数 mod 2147483647的答案。

Sample Input

Sample Output

Data Constraint

Hint

【样例解释】删除第一条边或者第三条边都能满足条件，所以方案数为2。
【数据规模】对于30%的数据,2<=N<=5,M<=10
对于50%的数据，满足条件的方案数不超过10000
对于100%的数据，2<=N<=1000

分析

首先考虑离0点最近的那个点，一定和0点只连着一条边，则这条边是必选的；然后考察第二近的点，一种可能是和0点直接连的边比较近，一种可能是经过刚才最近的那个点再到0点的路比较近，不管是哪一种，选择都是唯一的，而剩下第三种可能是两者距离相同，这样的话两者选且只能选一个。以此类推，假设现在已经构造好了前k个点的一棵子树，看剩余点中到0点最近的点，这个点到0点有k种方法（分别是和那k个点连边），其中有m个是可以保持最短距离的，则这一步可选的边数就是m。一直构造，把方法数累乘，就能得到最后的结果。整个过程可以很好的符合dijkstra的过程，而生成树的步骤和prim如出一辙。

代码

 1 //#pragma GCC optimize(2)
 2 #include<iostream>
 3 #include<queue>
 4 #include<cstdio>
 5 #include<cstring>
 6 using namespace std;
 7 struct sb
 8 {
 9     int to,nx,w;
10 }g[1001000];
11 int cnt,list[1001];
12 void add(int x,int y,int w)
13 {
14     g[++cnt].to=y; g[cnt].nx=list[x]; g[cnt].w=w; list[x]=cnt;
15     g[++cnt].to=x; g[cnt].nx=list[y]; g[cnt].w=w; list[y]=cnt;
16 }
17 int dis[1001],vis[1001],d[1001];
18 queue<int> q;
19 void spfa()
20 {
21     dis[1]=0; vis[1]=1;
22     q.push(1);
23     while (!q.empty())
24     {
25         int x=q.front(); q.pop(); vis[x]=0;
26         for (int i=list[x];i;i=g[i].nx)
27         {
28              int y=g[i].to;
29              if (dis[x]+g[i].w<dis[y])
30              {
31                 dis[y]=dis[x]+g[i].w;
32                 d[y]=1;
33                 if (!vis[y])
34                 {
35                    vis[y]=1;
36                    q.push(y);
37                 }
38              }
39              else if (dis[x]+g[i].w==dis[y]) d[y]++;
40         }
41     }
42 }
43 int main ()
44 {
45     int n,m;
46     cin>>n>>m;
47     for (int i=1,x,y,z;i<=m;i++)
48     {
49         scanf("%d%d%d",&x,&y,&z);
50         add(x,y,z);
51     }
52     for(int i=1;i<=n;i++) dis[i]=1000000000;
53     spfa();
54     long long ans=1;
55     for (int i=2;i<=n;i++)
56        ans=(ans*d[i])%2147483647;
57       cout<<ans; 
58 }

为何要逼自己长大，去闯不该闯的荒唐