5109: [CodePlus 2017]大吉大利，晚上吃鸡！
Time Limit: 30 Sec Memory Limit: 1024 MB
Submit: 107 Solved: 57
[Submit][Status][Discuss]Description
最近《绝地求生：大逃杀》风靡全球，皮皮和毛毛也迷上了这款游戏，他们经常组队玩这款游戏。在游戏中，皮皮和毛毛最喜欢做的事情就是堵桥，每每有一个好时机都能收到不少的快递。当然，有些时候并不能堵桥，皮皮和毛毛会选择在其他的必经之路上蹲点。K博士作为一个老年人，外加有心脏病，自然是不能玩这款游戏的，但是这并不能妨碍他对这款游戏进行一些理论分析，比如最近他就对皮皮和毛毛的战士很感兴趣。【题目描述】游戏的地图可以抽象为一张n个点m条无向边的图，节点编号为1到n，每条边具有一个正整数的长度。假定大魔王都会从S点出发到达T点（S和T已知），并且只会走最短路，皮皮和毛毛会在A点和B点埋伏大魔王。为了保证一定能埋伏到大魔王，同时又想留大魔王一条生路，皮皮和毛毛约定A点和B点必须满足：1.大魔王所有可能路径中，必定会经过A点和B点中的任意一点2.大魔王所有可能路径中，不存在一条路径同时经过A点和B点K博士想知道，满足上面两个条件的A,B点对有多少个，交换A,B的顺序算相同的方案Input
第一行输入四个整数n,m,S,T(1≤n≤5×10^4,1≤m≤5×10^4,1≤S,T≤n)，含义见题目描述。接下来输入m行，每行输入三个整数u,v,w(1≤u,v≤n,1≤w≤10^9)表示存在一条长度为w的边链接u和v。1≤n≤5×10^4,1≤m≤5×10^4,1≤w≤10^9Output
输出一行表示答案Sample Input
7 7 1 7
1 2 2
2 4 2
4 6 2
6 7 2
1 3 2
3 5 4
5 7 2Sample Output
6
【样例 1 解释】
合法的方案为 < 2, 3 >, < 2, 4 >, < 4, 3 >, < 4, 5 >, < 6, 3 >, < 6, 5 > 。HINT
来自 CodePlus 2017 11 月赛，清华大学计算机科学与技术系学生算法与竞赛协会 荣誉出品。Credit：idea/陈宇 命题/陈宇 验题/邢健开Git Repo：https://git.thusaac.org/publish/CodePlus201711本次比赛的官方网址：cp.thusaac.org感谢腾讯公司对此次比赛的支持。
题目简述
给定一张有边权（边权全为正）的无向图， $n$ 个点 $m$ 条边，给定起点 $S$ 和终点 $T$ ，问有多少对 $A$ 和 $B$ 满足从 $S$ 到 $T$ 的任意最短路一定经过 $A$ 或者 $B$ ，但是不存在某条最短路同时经过 $A$ 和 $B$ 。
解法一
首先是最暴力的解法，枚举任意点对 $A$ 和 $B$ ，然后删掉 $A$ 和 $B$ ，看看最短距离是否会变长，然后查看 $dis(S, A) + dis(A, B) + dis(B, T)$ 是否和 $dis(S, T)$ 相等，其中 $dis(X, Y)$ 表示原图中点 $X$ 到 $Y$ 的最短距离，由此可以判断枚举的 $A$ 和 $B$ 是否是合法的点对。
其中， $dis(X, Y)$ 可以用floyd求解
时间复杂度： $O \left(n3 \right)$
期望得分： $30$
解法二
首先，虽然题目中给定的是无向图，但是实际上我们可以先从 $S$ 出发求一遍最短路，然后问题变成了：“在有向无环图上，求有多少个满足条件的点对 $A,B$ ,满足从 $S$ 到 $T$ 的所有路径一定经过 $A,B$ 其中一点，并且不存在路径同时经过 $A,B$ ”。
求解这到题目的一个关键点在于： 满足条件的点对 $A,B$ 具有特点：从 $S$ 到 $A$ 的方案数 $\times$ 从 $A$ 到 $T$ 的方案数 + 从 $S$ 到 $B$ 的方案数 $\times$ 从 $B$ 到 $T$ 的方案数 $=$ 从 $S$ 到 $T$ 的方案数。
所以在有向无环图上用动态规划求解路径条数，再去掉 $A$ 可以到达 $B$ 或 $B$ 可以到达 $A$ 的情况即可求解这到题目。
PS：方案数可能会爆掉怎么办？可以对方案数求余一个大整数，如果觉得不够的话可以求余两个大整数。
时间复杂度： $O \left(n2+nm \right)$
期望得分： $60$
解法三
在解法二中，定义 $F(X) = $ 从 $S$ 到 $X$ 的方案数 $\times$ 从 $X$ 到 $T$ 的方案数 = 从 $S$ 经过 $X$ 到达 $T$ 的方案数，所以满足条件的点对 $A,B$ 为:
$F(A) + F(B) = F(T)$
$A$ 和 $B$ 不能相互到达
对于条件 $1$ ，我们可以使用数据结构进行优化（使用std::map即可），而对于条件 $2$ ，我们可以使用 bitset 位压 $32$ 或者 $64$ 位进行加速，使得最终时间和空间都能够承受。
时间复杂度： $O\left(n \log{n}+\frac{nm}{w}\right)$，其中 $w$ 是位压的字长。
期望得分： $100$
题解已经说的很清楚了，标算是hash+压位实现，但是考场上没时间写的话，就用map代替hash，用bitset代替压位，当然代价是常数大了好多倍。
这里说一下传递闭包
所谓传递性，可以这样理解：对于一个节点i，如果j能到i，i能到k，那么j就能到k。求传递闭包，就是把图中所有满足这样传递性的节点都弄出来，计算完成后，我们也就知道任意两个节点之间是否相连。
传递闭包的计算过程一般可以用Warshell算法描述：
For 每个节点i Do
For 每个节点j Do
If j能到i Then
For 每个节点k Do
a[j, k] := a[j, k] Or ( a[j, i] And a[ i, k] )
其中a数组为布尔数组，用来描述两个节点是否相连，可以看做一个无权图的邻接矩阵。可以看到，算法过程跟Floyd很相似，三重循环，枚举每个中间节点。只不过传递闭包只需要求出两个节点是否相连，而不用求其间的最短路径长。
上面的方法可以求出任意两个点是否连通，不过点数不多的时候一般我们可以压位或者bitset，然后就成了：
（实际上是lnk[i][e[j].s]但是可以将数组压缩成一维，也就是：）
rep(i,1,n-1) for (int j=1; j<=cnt; j++) lnk[e[j].s]|=lnk[e[j].t];
这样后面的按照题解做就好了。代码还是比较繁琐的。
#include<map>
#include<queue>
#include<bitset>
#include<cstdio>
#include<algorithm>
#define rep(i,l,r) for (int i=l; i<=r; i++)
typedef long long ll;
using namespace std; const int N=;
int n,m,u,v,w,cnt,S,T,h[N];
struct E{ int to,nxt,w; }e[N<<];
queue<int> Q;
int vis[N],iT[N]; ll dis[N],rdis[N]; void add(int x,int y,int z){
e[++cnt]=(E){y,h[x],z}; h[x]=cnt;
e[++cnt]=(E){x,h[y],z}; h[y]=cnt;
} void spfa(ll dis[],int S){
rep(i,,n) dis[i]=1ll<<,vis[i]=;
Q.push(S); vis[S]=; dis[S]=;
while (!Q.empty()){
int x=Q.front(); Q.pop(); vis[x]=;
for (int i=h[x],k; i; i=e[i].nxt)
if (dis[k=e[i].to]>dis[x]+e[i].w){
dis[k]=dis[x]+e[i].w;
if (!vis[k]) vis[k]=,Q.push(k);
}
}
} namespace G{
int h[N],rh[N],d[N],rd[N],cnt;
ll f[N],g[N];
queue<int>Q;
bitset<N>lnk[N],rlnk[N];
map<ll,bitset<N> >M;
struct E{ int s,t,nxt; }e[N<<]; void add(int x,int y){
e[++cnt]=(E){x,y,h[x]}; h[x]=cnt; d[y]++;
e[++cnt]=(E){y,x,rh[y]}; rh[y]=cnt; rd[x]++;
} ll solve(){
f[S]=; g[T]=; Q.push(S);
while (!Q.empty()){
int x=Q.front(); Q.pop();
for (int i=h[x]; i; i=e[i].nxt){
f[e[i].t]+=f[x];
if (!(--d[e[i].t])) Q.push(e[i].t);
}
}
Q.push(T);
while (!Q.empty()){
int x=Q.front(); Q.pop();
for (int i=rh[x]; i; i=e[i].nxt){
g[e[i].t]+=g[x];
if (!(--rd[e[i].t])) Q.push(e[i].t);
}
}
rep(i,,n) lnk[i].set(i),rlnk[i].set(i);
rep(i,,n-) for (int j=; j<=cnt; j+=) lnk[e[j].s]|=lnk[e[j].t];
rep(i,,n-) for (int j=; j<=cnt; j+=) rlnk[e[j].s]|=rlnk[e[j].t];
rep(i,,n) M[1ll*f[i]*g[i]].set(i);
ll res=;
rep(i,,n){
if (!M.count(f[T]-f[i]*g[i])) continue;
res+=(M[f[T]-f[i]*g[i]] & (~lnk[i]) & (~rlnk[i])).count();
}
return res>>;
}
} int main(){
freopen("bzoj5109.in","r",stdin);
freopen("bzoj5109.out","w",stdout);
scanf("%d%d%d%d",&n,&m,&S,&T);
rep(i,,m) scanf("%d%d%d",&u,&v,&w),add(u,v,w);
spfa(dis,S); spfa(rdis,T);
rep(i,,n) if (dis[i]+rdis[i]==dis[T]) iT[i]=;
rep(x,,n) if (iT[x])
for (int i=h[x]; i; i=e[i].nxt)
if (dis[e[i].to]==dis[x]+e[i].w && iT[e[i].to]) G::add(x,e[i].to);
printf("%lld\n",G::solve());
return ;
}