P6413 [COCI2008-2009#3] NAJKRACI 题解
hellhell
·
·
题解
题目大意
题面已经很简洁了，这里不再赘述。
思路分析
定理1：对于一条最短路 u -> v，它的任意一个子路径 u_1 -> v_1 都是一条最短路。
证明：假设 u_1 -> v_1 不是最短路，那么一定可以找到一条路径 u_2 -> v_2 使得 u -> v 更短，与 u -> v 是最短路矛盾。
根据定理1，一张图 G，在固定源点 S 时，可以得到一张子图 G_1 使得 G_1 上任意一条边都在 S 到至少一个点的最短路径上，且不再 G_1 上的边都不在 S 到任意一个点的最短路上。我们称图 G_1 为最短路图。
判断一条边是否在最短路图上，只需判断 dis[u]+val[v] == dis[v] 是否成立。
求最短路图可以用 SPFA 来解决。
```cpp
void spfa(int s){
memset(dis,0x3f,sizeof(dis));
memset(vis,false,sizeof(vis));
memset(book,false,sizeof(book));
dis[s]=0;
vis[s]=true;
q.push(s);
while(!q.empty()){
int now=q.front();
vis[now]=false;
q.pop();
for(int i=head[now];i;i=edge[i].next){
int v=edge[i].to;
if(dis[v]>dis[now]+edge[i].val){
dis[v]=dis[now]+edge[i].val;
if(!vis[v]){
vis[v]=true;
q.push(v);
}
}
}
}
for(int i=1;i<=m;i++){
if(dis[edge[i].from]+edge[i].val==dis[edge[i].to])
book[i]=true;
}
}
```
定理2：任意的最短路图，一定不存在环。
证明：假设图中存在环 $u_1$ -> $u_2$ -> $u_3$ -> …… -> $u_n$ -> $u_1$，则有 $dis[u_1]+val[u_2] == dis[u_2]$，$dis[u_2]+val[u_3] == dis[u_3]$，
……
$dis[u_n]+val[u_1] == dis[u_1]$。
因为边权都为正数，则有 $dis[u_n]>dis[u_1]$，$dis[u_1]>dis[u_n]$。
矛盾。
求出最短路图后，考虑如何统计答案。
设 `cnt1[i]` 表示 $S$ 到 $i$ 点的最短路数量，`cnt2[i]` 表示 $i$ 点到终点的最短路数量。
那么对于一条边 $e(u,v)$，根据乘法原理，答案为 $cnt1[u]*cnt2[v]$。
但题目中源点和终点并没有给出，只枚举源点，并不能知道终点。根据定理2可以考虑对最短路图拓扑排序，然后按照拓扑序倒序求 $cnt2$。
具体来说，枚举顺序为拓扑序倒序，当前点为 $u$，$u$ 点指向 $v_1$，$v_2$，则有
$cnt2[u]=cnt2[v_1]+cnt2[v_2]$。
$topo$ 数组与 $tag$ 记录拓扑序。
```cpp
void TopoSort(int s){
memset(ind,0,sizeof(ind));
memset(cnt1,0,sizeof(cnt1));
memset(cnt2,0,sizeof(cnt2));
cnt1[s]=1;
q.push(s);
tag=0;
for(int i=1;i<=m;i++){
if(book[i])
ind[edge[i].to]++;
}
while(!q.empty()){
int now=q.front();
q.pop();
topo[++tag]=now;
for(int i=head[now];i;i=edge[i].next){
if(!book[i])
continue;
int v=edge[i].to;
ind[v]--;
if(ind[v]==0)
q.push(v);
cnt1[v]+=cnt1[now];
cnt1[v]%=mod;
}
}
for(int i=tag;i;i--){
int now=topo[i];
cnt2[now]++;
for(int j=head[now];j;j=edge[j].next){
if(!book[j])
continue;
int v=edge[j].to;
cnt2[now]+=cnt2[v];
cnt2[now]%=mod;
}
}
}
```