【图论动态规划拆点】luoguP3953 逛公园-白红宇

【图论动态规划拆点】luoguP3953 逛公园

阅读量：5099 次

发布时间：2019-06-13

本文共 8007 字，大约阅读时间需要 26 分钟。

经典的动态规划拆点问题。

题目描述

策策同学特别喜欢逛公园。公园可以看成一张 NN 个点 MM 条边构成的有向图，且没有自环和重边。其中1号点是公园的入口， NN 号点是公园的出口，每条边有一个非负权值，代表策策经过这条边所要花的时间。

策策每天都会去逛公园，他总是从1号点进去，从 NN 号点出来。

策策喜欢新鲜的事物，它不希望有两天逛公园的路线完全一样，同时策策还是一个特别热爱学习的好孩子，它不希望每天在逛公园这件事上花费太多的时间。如果1号点到 NN 号点的最短路长为 dd ，那么策策只会喜欢长度不超过 d + Kd+K 的路线。

策策同学想知道总共有多少条满足条件的路线，你能帮帮它吗？

为避免输出过大，答案对 PP 取模。

如果有无穷多条合法的路线，请输出 -1−1 。

输入输出格式

输入格式：

第一行包含一个整数 TT , 代表数据组数。

接下来 TT 组数据，对于每组数据：第一行包含四个整数 N,M,K,PN,M,K,P ，每两个整数之间用一个空格隔开。

接下来 MM 行，每行三个整数 a_i,b_i,c_iai,bi,ci ，代表编号为 a_i,b_iai,bi 的点之间有一条权值为 c_ici 的有向边，每两个整数之间用一个空格隔开。

输出格式：

输出文件包含 TT 行，每行一个整数代表答案。

说明

【样例解释1】

对于第一组数据，最短路为 33 。 $1 – 5, 1 – 2 – 4 – 5, 1 – 2 – 3 – 5$ 为 33 条合法路径。

【测试数据与约定】

对于不同的测试点，我们约定各种参数的规模不会超过如下

测试点编号					是否有0边
1	5	5	10	0	否
2	5	1000	2000	0	否
3	5	1000	2000	50	否
4	5	1000	2000	50	否
5	5	1000	2000	50	否
6	5	1000	2000	50	是
7	5	100000	200000	0	否
8	3	100000	200000	50	否
9	3	100000	200000	50	是
10	3	100000	200000	50	是

对于 100%的数据, $\le P \le 10^9,1 \le a_i,b_i \le N ,0 \le c_i \le 10001≤P≤109,1≤ai,bi≤N,0≤ci≤1000 。$

数据保证：至少存在一条合法的路线。

题目分析

计数题那么当然首先考虑dp啊。这是一个经典的拆点模型。由于k非常小，所以可以把每一个点拆成$k$个状态。

以上就是拆点的核心。

dp状态怎么设①

“拆点”听上去很高端，但实际上应该大家都在写题时不知不觉应用过。这里可以用$f[i][j]$表示$dis[1][i]=mnDis[1][i]+j$的方案数，其中$mnDis[1][i]$表示1到i的最短路径长度。

之所以$j$这一维代表的路径长度是$mnDis[1][i]+j$，是因为1..i的最短路长度是固定的，可以预先处理，而不用在状态里枚举。（这个和所谓的“dp套dp”非常像，本质就是通过预处理节省时间复杂度）

那么有了状态就很容易想到大概的转移思路了。用$dis[i]$表示1...i的最短路长度，那么通过一条边$(u,v,w)$存在$f[u][d]->f[v][dis[u]+d+w-dis[v]]$。

假设现在已经判断完是否存在零环了（这个对边排序或者怎么搞都行），那么具体的转移方程应该是怎么样的？

dp转移怎么搞①ⅰ

最初我是想：既然$f[u][d]->f[v][dis[u]+d+w-dis[v]]$，并且必定有$dis[u]+w≥dis[v]$，那么每一次转移时$f[i][j]$这个状态的$j$必定是单调增的啊，那么从$f[1][0]$开始对图进行记忆化搜索不就好了吗？

麻烦就麻烦在这样dp转移还受到多条最短路的干扰。

举个最简单的例子，这个做法先$1->4$遍历到了$f[4][0]$一次，然后用这个$f[4][0]=1$向外贡献答案。然而过了一会儿从1开始的路径$1->2->3->4$又遍历到了$f[4][0]$，于是又用$f[4][0]=2$向外贡献答案。这样不就重复计算了吗！

当然可以每次遍历到的时候先减去上一次的贡献再处理。但是这样便既不是我们最初想要达到的，又变得十分冗长，况且并不是没有改进的方法。

dp转移怎么搞①ⅱ ——70pts dp

在没有零边的情况下，注意到dp的顺序一定是先做$dis[]$小的，再做$dis[]$大的。那么就可以以端点到原点距离对于边排序，再做一次稳定的$O(mk)$转移。

1 //由于是按照另一种写法改编而来，所以这份代码有点丑  2 #include
      
         3 const int maxn = 100035;  4 const int maxm = 200035;  5   6 int n,m,T,k,p,deal,DIS,mnDis,ans;  7 int initNxt[maxm],initHead[maxn],initEdgeTot;  8 int nxt[maxm],head[maxm],edgeTot;  9 int judge4cir0[maxn]; 10 int dis[maxn][2]; 11 int f[maxn][53]; 12 bool bad[maxn],visQ[maxn]; 13 struct Edge 14 { 15     int u,v,val; 16     long long w; 17     Edge(int b=0, int c=0):v(b),val(c) {} 18 }edgesSv[maxm],initEdges[maxm],edges[maxm]; 19 struct cmp 20 { 21     bool operator()(int a, int b) 22     { 23         return dis[a][DIS] > dis[b][DIS]; 24     } 25 }; 26 std::priority_queue

, cmp> disQ; 27 28 int read() 29 { 30 char ch = getchar(); 31 int num = 0; 32 bool fl = 0; 33 for (; !isdigit(ch); ch = getchar()) 34 if (ch=='-') fl = 1; 35 for (; isdigit(ch); ch = getchar()) 36 num = (num<<1)+(num<<3)+ch-48; 37 if (fl) num = -num; 38 return num; 39 } 40 bool cmpEdge1(Edge b, Edge a) 41 { 42 if (b.val!=a.val) return b.val < a.val; 43 return b.w < a.w; 44 } 45 bool cmpEdge2(Edge a, Edge b) 46 { 47 if (dis[a.u][0]!=dis[b.u][0]) return dis[a.u][0] < dis[b.u][0]; 48 return dis[a.v][0] < dis[b.v][0]; 49 } 50 void initAddedge(int u, int v, int w) 51 { 52 initEdges[++initEdgeTot] = Edge(v, w), initNxt[initEdgeTot] = initHead[u], initHead[u] = initEdgeTot; 53 } 54 void addedge(int u, int v, int w) 55 { 56 edges[++edgeTot] = Edge(v, w), nxt[edgeTot] = head[u], head[u] = edgeTot; 57 } 58 bool legal() 59 { 60 memset(judge4cir0, -1, sizeof judge4cir0); 61 while (edgesSv[deal+1].val==0&&deal

k) continue; 99 (f[v][y+dis[x][0]+w-dis[v][0]] += f[x][y]) %= p;100 dp(v, y+dis[x][0]+w-dis[v][0]);101 }102 }103 int main()104 {105 // freopen("lg3953.in","r",stdin);106 // freopen("lg3953.out","w",stdout);107 T = read();108 while (T--)109 {110 memset(initHead, -1, sizeof initHead);111 memset(dis, 0x3f3f3f3f, sizeof dis);112 memset(head, -1, sizeof head);113 memset(bad, 0, sizeof bad);114 memset(f, 0, sizeof f);115 n = read(), m = read(), k = read(), p = read();116 ans = mnDis = deal = edgeTot = initEdgeTot = 0;117 for (int i=1; i<=m; i++)118 edgesSv[i].u = read(), edgesSv[i].v = read(),119 edgesSv[i].w = 1ll*edgesSv[i].u*edgesSv[i].v, edgesSv[i].val = read();120 std::sort(edgesSv+1, edgesSv+m+1, cmpEdge1);121 if (!legal()){122 puts("-1");123 continue;124 }125 for (int i=deal+1; i<=m; i++)126 initAddedge(edgesSv[i].u, edgesSv[i].v, edgesSv[i].val);127 DIS = 0, dijsktra(1);128 memset(initHead, -1, sizeof initHead);129 initEdgeTot = 0;130 for (int i=1; i<=m; i++)131 initAddedge(edgesSv[i].v, edgesSv[i].u, edgesSv[i].val);132 DIS = 1, dijsktra(n);133 mnDis = dis[n][0], f[1][0] = 1;134 for (int i=1; i<=n; i++)135 if (dis[i][0]==dis[0][0]||dis[i][1]==dis[0][0]||dis[i][0]+dis[i][1] > mnDis+k)136 bad[i] = 1;137 std::sort(edgesSv+1, edgesSv+m+1, cmpEdge2);138 for (int d=0; d<=k; d++)139 for (int i=1; i<=m; i++)140 {141 int u = edgesSv[i].u, v = edgesSv[i].v, w = edgesSv[i].val;142 if (!bad[u]&&!bad[v])143 {144 int tt = d+dis[u][0]+w-dis[v][0];145 if (tt <= k){146 (f[v][tt] += f[u][d]) %= p;147 }148 }149 }150 for (int i=0; i<=k; i++) (ans += f[n][i]) %= p;151 printf("%d\n",ans);152 }153 return 0;154 }

无零边-70pts

dp转移怎么搞①ⅲ ——100pts dp

那么有零边意味着什么呢？意味着仅仅需要对于零边单独拓扑序处理即可。

这是一个仅用$dis[]$排序而不够的例子。

dp状态怎么设②

但其实dp题的状态是一个很玄妙的东西。

用$mnDis[i]$表示i到n的最短路，那么这一次$f[i][j]$表示的是$dis[i][n]+j≤mnDis[i]$的方案数。

注意前一种状态是严格=的方案数，而这里利用了前缀和的方法，表示了所有≤的方案数。

dp转移怎么搞②

这样表示的好处在于：从$f[1][k]$直接开始，并不用考虑拓扑序，可以记忆化搜索，并且遇到处理过状态的直接return即可。原因便是这种状态下，答案的贡献是被动的；而不是答案从自身这个状态转移出去。因此一旦搜索到终点$i==n$，$f[i][d]$就可以+1，同时在这个状态路径上的其他所有状态，都会且仅会收到一次这个合法状态的反馈。

或许有点绕口……？不过细想也就是这个理。

还注意到在这种遍历方式之下，如果访问到了尚未出栈的节点，就意味着出现了零环。因此可以省去预判断零环的过程。

那么就可以愉快地记忆化搜索啦。

1 #include
     
        2 const int maxn = 100035;  3 const int maxm = 200035;  4   5 int n,m,T,k,p,ans;  6 int nxt[maxm],head[maxm],edgeTot;  7 int dis[maxn];  8 int f[maxn][53];  9 bool visQ[maxn],stk[maxn][53]; 10 struct Edge 11 { 12     int u,v,val; 13     Edge(int b=0, int c=0):v(b),val(c) {} 14 }edgesSv[maxm],edges[maxm]; 15 struct cmp 16 { 17     bool operator()(int a, int b) 18     { 19         return dis[a] > dis[b]; 20     } 21 }; 22 std::priority_queue

, cmp> disQ; 23 24 int read() 25 { 26 char ch = getchar(); 27 int num = 0; 28 bool fl = 0; 29 for (; !isdigit(ch); ch = getchar()) 30 if (ch=='-') fl = 1; 31 for (; isdigit(ch); ch = getchar()) 32 num = (num<<1)+(num<<3)+ch-48; 33 if (fl) num = -num; 34 return num; 35 } 36 void addedge(int u, int v, int w) 37 { 38 edges[++edgeTot] = Edge(v, w), nxt[edgeTot] = head[u], head[u] = edgeTot; 39 } 40 void dijsktra(int s) 41 { 42 disQ.push(s), dis[s] = 0; 43 while (disQ.size()) 44 { 45 int tt = disQ.top(); 46 disQ.pop(), visQ[tt] = 0; 47 for (int i=head[tt]; i!=-1; i=nxt[i]) 48 { 49 int v = edges[i].v, w = edges[i].val; 50 if (dis[tt]+w < dis[v]){ 51 dis[v] = dis[tt]+w; 52 if (!visQ[v]) 53 visQ[v] = 1, disQ.push(v); 54 } 55 } 56 } 57 } 58 int dp(int x, int y) 59 { 60 if (f[x][y]) return f[x][y]; 61 if (stk[x][y]) return -1; 62 if (x==n) f[x][y]++; 63 stk[x][y] = 1; 64 for (int i=head[x]; i!=-1; i=nxt[i]) 65 { 66 int v = edges[i].v, w = edges[i].val; 67 int tt = y-dis[v]+dis[x]-w; 68 if (tt>=0){ 69 int tmp = dp(v, tt); 70 if (tmp==-1){ 71 stk[x][y] = 0; 72 return -1; 73 } 74 (f[x][y] += f[v][tt]) %= p; 75 } 76 } 77 stk[x][y] = 0; 78 return f[x][y]; 79 } 80 int main() 81 { 82 // freopen("lg3953.in","r",stdin); 83 T = read(); 84 while (T--) 85 { 86 memset(dis, 0x3f3f3f3f, sizeof dis); 87 memset(head, -1, sizeof head); 88 memset(f, 0, sizeof f); 89 n = read(), m = read(), k = read(), p = read(), edgeTot = 0; 90 for (int i=1; i<=m; i++) 91 edgesSv[i].u = read(), edgesSv[i].v = read(), edgesSv[i].val = read(); 92 memset(head, -1, sizeof head); 93 edgeTot = 0; 94 for (int i=1; i<=m; i++) 95 addedge(edgesSv[i].v, edgesSv[i].u, edgesSv[i].val); 96 dijsktra(n); 97 memset(head, -1, sizeof head); 98 edgeTot = 0; 99 for (int i=1; i<=m; i++)100 addedge(edgesSv[i].u, edgesSv[i].v, edgesSv[i].val);101 printf("%d\n",dp(1, k));102 }103 return 0;104 }