sdutoj 3911 指定长度路径数 矩阵快速幂

缘起

日常浪费生命~ sdutoj 3911 指定长度路径数

分析

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
Time Limit: 1000 ms		Memory Limit: 65536 KiB
Problem Description
题目给出一个有n个节点的有向图，求该有向图中长度为k的路径条数。方便起见，节点编号为1,2,…,n，用邻接矩阵表示该有向图。该有向图的节点数不少于2并且不超过500

例如包含两个节点的有向图，图中有两条边1 → 2 ,2 → 1 。

长度为1的路径有两条：1 → 2 和 2 →1 ；

长度为2的路径有两条：1 → 2 → 1和2 → 1 → 2 ；

偷偷告诉你也无妨，其实这个图无论k取值多少 ( k > 0 )，长度为k的路径都是2条。

Input
多组输入，每组输入第一行是有向图中节点的数量即邻接矩阵的行列数n。接下来n行n列为该图的邻接矩阵。接下来一行是一个整数k.k小于30.

Output
输出一个整数，即为图中长度为k的路径的条数。

Sample Input
3
0 1 0
0 0 1
0 0 0
2
Sample Output
1

令 

1
2
3
dp[u][v][k]是从u到v长度为k的路径的条数. 答案是\Sigma_{u,v}{dp[u][v][k]}
对于任何0<=x<=k都有
dp[u][v][k]=\Sigma_{w是图中所有顶点}dp[u][w][x]*dp[w][v][k-x]

令G_{k}[u[v] 为矩阵{dp[u][v][k]} u,v是有向图中所有顶点. 则

1
Gk=G_{k-x}*G_{x}

其中

1
G0是单位矩阵，G1=邻接矩阵

注意, 为什么不对x求和? 例如4=1+3=2+2，因为一条路是1+3，一条路是2+2，那么后面的2+2其实就是一条1+3啊（从一个2挪一个顶点到2去就变成了1+3了）~ 这样就会重复计算了. 所以不需要对x求和.

其实本题的模型好像当时我自学组合数学的时候见过~

所以

1
Gk=G1^k

复杂度是 O(N^3*logk). 最后的答案就是Gk中所有元素的和.

注意下面代码的 #pragma 编译选项. 不然爆栈, 应该可以将其置为全局变量. 但是懒的搞了,直接暴力过

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
//#include "stdafx.h"
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <stdio.h>
#include <string.h>
//#define LOCAL

const int maxn = 505;
int n,k, g[maxn][maxn];

void m_mul(int a[maxn][maxn],int b[maxn][maxn])
{
	int ans[maxn][maxn];
	memset(ans, 0, sizeof(ans));
	for (int i = 0; i<n; i++)
	{
		for (int j = 0; j<n;j++)
		{
			for (int k = 0; k<n; k++)
			{
				ans[i][j]+=a[i][k]*b[k][j];
			}
		}
	}
	memcpy(a, ans, sizeof(ans));
}

void ksm(int a[maxn][maxn], int b)
{
	int ans[maxn][maxn];
	for (int i = 0; i<n; i++)
	{
		for (int j = 0;j<n; j++)
		{
			ans[i][j] =i==j;
		}
	}
	while(b)
	{
		if (b&1)
		{
			m_mul(ans, a);
		}
		if (b>1)
		{
			m_mul(a,a);
		}
		b>>=1;
	}
	memcpy(a, ans, sizeof(ans));
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	while(~scanf("%d", &n))
	{
		for (int i = 0; i<n; i++)
		{
			for (int j = 0; j<n; j++)
			{
				scanf("%d", g[i]+j);
			}
		}
		scanf("%d", &k);
		ksm(g,k);
		int ans = 0;
		for (int i = 0; i<n;i++)
		{
			for (int j = 0; j<n; j++)
			{
				ans+=g[i][j];
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}

ac情况

RunID Nick Name Problem Result Time Memory Language Code Len Submission Time
6556229 yfs 3911 Accepted 92 ms 3144 KiB g++ 1183 B 2019-09-20 10:26:37