「CodePlus 2017 11月赛」大吉大利,晚上吃鸡! - 最短路径DAG+bitset | Bill Yang's Blog

「CodePlus 2017 11月赛」大吉大利,晚上吃鸡! - 最短路径DAG+bitset

题目大意

    最近《绝地求生:大逃杀》风靡全球,皮皮和毛毛也迷上了这款游戏,他们经常组队玩这款游戏。
在游戏中,皮皮和毛毛最喜欢做的事情就是堵桥,每每有一个好时机都能收到不少的快递。
    当然,有些时候并不能堵桥,皮皮和毛毛会选择在其他的必经之路上蹲点。
    K博士作为一个老年人,外加有心脏病,自然是不能玩这款游戏的,但是这并不能妨碍他对这款游戏进行一些理论分析,比如最近他就对皮皮和毛毛的战士很感兴趣。


    游戏的地图可以抽象为一张$n$个点$m$条无向边的图,节点编号为$1$到$n$,每条边具有一个正整数的长度。
    假定大魔王都会从$S$点出发到达$T$点($S$和$T$已知),并且只会走最短路,皮皮和毛毛会在$A$点和$B$点埋伏大魔王。
    为了保证一定能埋伏到大魔王,同时又想留大魔王一条生路,皮皮和毛毛约定$A$点和$B$点必须满足:
    $1.$大魔王所有可能路径中,必定会经过$A$点和$B$点中的任意一点
    $2.$大魔王所有可能路径中,不存在一条路径同时经过$A$点和$B$点
    K博士想知道,满足上面两个条件的$A,B$点对有多少个,交换$A,B$的顺序算相同的方案。


题目分析

考虑由于只走最短路,因此将最短路径DAG建出来,并统计最短路条数$f[x,0/1]$。
设$F[x]$表示从$S\rightarrow T$走最短路经过$x$的方案数,$F[x]=f[x,0]\cdot f[x,1]$。

对于第一个条件,相当于$F[A]+F[B]=F[T]$,枚举点$A$,相当于统计$F[T]-F[B]=F[A]$的$B$的个数,将合法的$B$用bitset存下来。

对于第二个条件,相当于$A,B$不能互达,从$S$和$T$分别做一次传递闭包,$A$所能到达的点集的补集即为合法的$B$的位置,用bitset存下来。

对于上述两个条件取个交集即可得到个数。

注意还可以选择在一个最短路径DAG上的必经点和一个不在最短路径DAG上的点作为答案。


代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<bitset>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
using namespace std;
typedef long long LL;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=50005;
struct Edge {
int from,to,dist;
};
int m,s,t,InDegree[maxn];
LL n,Dist[maxn][2],f[maxn][2];
bool vst[maxn],bj[maxn];
vector<Edge>edges[maxn];
vector<int>G[maxn],fG[maxn],P;
bitset<maxn>g[maxn][2];
map<LL,bitset<maxn> >M;
void AddEdge(int x,int y,int v) {
edges[x].push_back((Edge) {x,y,v});
}
void AddEdge(int x,int y) {
G[x].push_back(y);
fG[y].push_back(x);
}
struct QueNode {
LL d;
int u;
bool operator < (const QueNode& b) const {
return d>b.d;
}
};
void Dijkstra(int s,int id) {
for(int i=1; i<=n; i++)Dist[i][id]=LLONG_MAX/2;
Dist[s][id]=0;
memset(vst,0,sizeof(vst));
f[s][id]=1;
priority_queue<QueNode>Q;
Q.push((QueNode) {0,s});
while(!Q.empty()) {
int Now=Q.top().u;
Q.pop();
if(vst[Now])continue;
vst[Now]=1;
for(Edge& e:edges[Now]) {
int Next=e.to;
if(Dist[Next][id]>Dist[Now][id]+e.dist) {
Dist[Next][id]=Dist[Now][id]+e.dist;
f[Next][id]=f[Now][id];
Q.push((QueNode) {Dist[Next][id],Next});
} else if(Dist[Next][id]==Dist[Now][id]+e.dist)f[Next][id]+=f[Now][id];
}
}
}
void Top_Sort(int id) {
memset(InDegree,0,sizeof(InDegree));
for(auto Now:P)G[Now].clear(),fG[Now].clear();
for(auto Now:P)
for(auto e:edges[Now]) {
int Next=e.to;
if(bj[Next]&&Dist[Now][id]+e.dist==Dist[Next][id]) {
AddEdge(Now,Next);
InDegree[Next]++;
}
}
queue<int>Q;
stack<int>S;
for(auto p:P)
if(!InDegree[p])Q.push(p);
while(!Q.empty()) {
int Now=Q.front();
Q.pop();
S.push(Now);
for(int Next:G[Now]) {
InDegree[Next]--;
if(!InDegree[Next])Q.push(Next);
}
}
for(auto p:P)g[p][id][p-1]=1;
while(!S.empty()) {
int Now=S.top();
S.pop();
for(int Next:fG[Now])
g[Next][id]|=g[Now][id];
}
}
int main() {
n=Get_Int();
m=Get_Int();
s=Get_Int();
t=Get_Int();
for(int i=1; i<=m; i++) {
int x=Get_Int(),y=Get_Int(),v=Get_Int();
AddEdge(x,y,v);
AddEdge(y,x,v);
}
Dijkstra(s,0);
if(Dist[t][0]==LLONG_MAX/2) {
printf("%lld\n",n*(n-1)/2);
return 0;
}
Dijkstra(t,1);
for(int i=1; i<=n; i++)
if(Dist[i][0]+Dist[i][1]==Dist[t][0])P.push_back(i),bj[i]=1;
for(auto p:P)M[f[p][0]*f[p][1]]|=1<<(p-1);
Top_Sort(0);
Top_Sort(1);
LL ans=0,cnt=0;
for(int i=0; i<P.size(); i++) {
auto p=P[i];
ans+=((M[f[t][0]-f[p][0]*f[p][1]]>>i)&(~g[p][0]>>i)&(~g[p][1]>>i)).count();
}
for(auto p:P)if(f[p][0]*f[p][1]==f[t][0])cnt++;
ans+=cnt*(n-P.size());
printf("%lld\n",ans);
return 0;
}
0%