Post 3

Veröffentlicht am | Edited on

Only hate the road when you’re missing home.

「一本通 3.2 练习 4」新年好

题目描述

原题来自：CQOI 2005

重庆城里有 nn 个车站，mm 条双向公路连接其中的某些车站。每两个车站最多用一条公路连接，从任何一个车站出发都可以经过一条或者多条公路到达其他车站，但不同的路径需要花费的时间可能不同。在一条路径上花费的时间等于路径上所有公路需要的时间之和。

佳佳的家在车站 11，他有五个亲戚，分别住在车站 a,b,c,d,ea,b,c,d,e。过年了，他需要从自己的家出发，拜访每个亲戚（顺序任意），给他们送去节日的祝福。怎样走，才需要最少的时间？

输入格式

第一行：n,mn,m 为车站数目和公路的数目。

第二行：a,b,c,d,ea,b,c,d,e 为五个亲戚所在车站编号。

以下 mm 行，每行三个整数 x,y,tx,y,t，为公路连接的两个车站编号和时间。

输出格式

输出仅一行，包含一个整数 TT，为最少的总时间。

样例

样例输入

1
2
3
4
5
6
7
8
6 6
2 3 4 5 6
1 2 8
2 3 3
3 4 4
4 5 5
5 6 2
1 6 7

样例输出

1
21

数据范围与提示

对于全部数据，

题解

一道最短路的基础题。

显然需要知道这6个点之间两两最短路，需要6遍Dijkstra。

然后状态压缩DP：不能光记录联通点集的最短距离，需要加上最后到达的一个点，否则很容易找出反例：有时候需要走重边，必须是最后到达的点才能直接走一条边。

Code：

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
#define maxn 50005
int head[maxn] , cnt , dis[7][7] , id[maxn] , idx , n , m , d[maxn] , f[7][1<<7] , ans = 10000000;
bool vis[maxn];
std::vector<int> v;
struct edge{
	int next, to , dis;
}e[maxn<<2];
struct Node{
	int v , k;
	bool operator < (const Node& x)const{
		return v > x.v;
	}
};
inline void add(int x , int y , int ds)
{
	e[++cnt].next = head[x];
	e[cnt].to = y;
	e[cnt].dis = ds;
	head[x] = cnt;
}
inline void SPDIJ(int s)
{
	std::priority_queue<Node> q;
	std::memset(d,0x7f,sizeof(d));
	std::memset(vis,false,sizeof(vis));
	d[s] = 0;
	q.push((Node){d[s] , s});
	while(!q.empty())
	{
		int k = q.top().k;
		q.pop();
		if(vis[k])	continue;
		vis[k] = true;
		for(int i = head[k] ; i ; i = e[i].next){
			int v = e[i].to , dv = e[i].dis;
			if(d[k] + dv < d[v]){
				d[v] = d[k] + dv;
				q.push((Node){d[v] , v});
			}
		}
	}
	for(int i = 0 ; i < v.size() ; ++i)
		if(v[i] != s)
			dis[id[s]][id[v[i]]] = dis[id[v[i]]][id[s]] = d[v[i]];
}
int main()
{
	scanf("%d%d",&n,&m);
	v.push_back(1);
	for(int i = 1 ; i <= 5 ; ++i){
		int x;
		scanf("%d",&x);
		v.push_back(x);
	}
	for(int i = 0 ; i < v.size() ; ++i)
		id[v[i]] = idx++;
	for(int i = 1 ; i <= m ; ++i){
		int x , y , d;
		scanf("%d%d%d",&x,&y,&d);
		add(x,y,d) , add(y,x,d);
	}
	for(int i = 0 ; i < v.size() ; ++i)
		SPDIJ(v[i]);

	std::memset(f,0x7f,sizeof(f));
	int S = (1 << 6) - 1;
	f[0][1] = 0; // must from the 0 point
	for(int i = 1 ; i <= S ; ++i)
		for(int j = 0 ; j <= 5 ; ++j)
			for(int k = 0 ; k <= 5 ; ++k)
				if(i & (1 << j))
					f[k][i | (1 << k)] = std::min(f[k][i | (1 << k)] , f[j][i] + dis[j][k]);  
	for(int i = 0 ; i <= 5 ; ++i)
		ans = std::min(ans , f[i][S]);
	printf("%d",ans);
}

[HAOI2012]道路

题目描述

C国有n座城市，城市之间通过m条[b]单向[/b]道路连接。一条路径被称为最短路，当且仅当不存在从它的起点到终点的另外一条路径总长度比它小。两条最短路不同，当且仅当它们包含的道路序列不同。我们需要对每条道路的重要性进行评估，评估方式为计算有多少条不同的最短路经过该道路。现在，这个任务交给了你。

输入输出格式

输入格式：

第一行包含两个正整数n、m

接下来m行每行包含三个正整数u、v、w，表示有一条从u到v长度为w的道路

输出格式：

输出应有m行，第i行包含一个数，代表经过第i条道路的最短路的数目对[b]1000000007取模[/b]后的结果

输入输出样例

输入样例#1：

1
2
3
4
5
4 4
1 2 5
2 3 5
3 4 5
1 4 8

输出样例#1：

1
2
3
4
2
3
2
1

说明

数据规模

30%的数据满足：n≤15、m≤30

60%的数据满足：n≤300、m≤1000

100%的数据满足：n≤1500、m≤5000、w≤10000

题解

这道题真的挺难的。。需要你自己构造算法。

首先能想到一条重要的性质。

对于S—>T的最短路上，最短路上任意一点都是到S的最短路（也是单源最短路树的基础）

一条边（u，v）的答案就是所有S—>T中，S到u最短路的个数与v到T最短路并且经过S到u的最短路个数的乘积。

但是单源最短路树是不够的，因为它只是一条最短路。

也许我们可以受到一点启发。

假如我们把所有以S为源点的最短路都加入到一张图中，如果保证边权为正（题目很恶心的没有说清楚）

那么能否得出这张图没有环呢？显然可以，因为如果有正环就和定义矛盾了（环上任意一点和相邻点从两个方向得到的关系都矛盾）

那么这个DAG满足什么性质呢？显然对于反图，到点v的都是v出边的最短路上的点。

这样整道题的做法就不难想了。

首先对于每个点，我们需要知道它到其它点的最短路数目，可以通过最短路计数解决。记为

然后再用一些办法构造出这个最短路DAG，拓扑排序。记为

对于每条边（u，v），答案就是

那么如何构造这个图呢？

最短路的时候是可以建出来的。每当我们成功松弛一次，我们就把这个点入边清空，把这条边加进去，假如相同就直接把这条边加进去。

这里有一个小trick，我们在跑dijkstra建DAG的时候一开始会建出错误的边，因此，我们在改变点V的dis值时需要删除这个点的所有出边，此时直接清掉邻接表的表头就好了。

Code下午写QWQ，上午想这题3小时结果AC自动机都没看完，效率有点低下。

先放Code：

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
// luogu-judger-enable-o2
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <queue>
#include <cstring>
#define maxn 5005
#define ll long long
#define mod 1000000007
struct edge{
    int next , to , dis;
};
bool val[maxn << 3];
struct Graph
{
    int head[maxn] , ct , rd[maxn] , eref[maxn << 4];
    edge e[maxn<<4];
    inline void add(int x , int y,  int d , int num)
    {
        e[++ct].next = head[x];
        e[ct].to = y;
        e[ct].dis = d;
        head[x] = ct;
        rd[y] ++ ;
        eref[ct] = num;
    }
    inline void Del(int x){
        for(int i = head[x] ; i ; i = e[i].next)
            --rd[e[i].to] ,  val[eref[i]] = false;
        head[x] = 0;
    }	
    inline edge operator[](int x){
        return e[x];
    }
    inline int operator()(int x){
        return head[x];
    }
    inline void clear()
    {
        ct = 0;
        std::memset(head,0,sizeof(head));
        std::memset(rd,0,sizeof(rd));
    }
    inline bool valid(int x){
    	return val[eref[x]];
    }
}g , r , p;
int n , m , d[maxn];
bool vis[maxn];
struct ed{
    int fr ,to , dis;
}er[maxn<<4];
struct Node{
    int v , k;
    bool operator < (const Node& x)const{
        return v > x.v;
    }
};
ll f[maxn] , t[maxn] , ans[maxn];
inline void Create(int s)
{
    std::memset(d,0x7f,sizeof(d));
    std::memset(vis,false,sizeof(vis));
    d[s] = 0;
    std::priority_queue<Node> q;
    q.push((Node){d[s] , s});
    f[s] = 1;
    while(!q.empty())
    {
        int k = q.top().k;
        q.pop();
        if(vis[k])	continue;
        vis[k] = true;
        for(int i = g(k) ; i ; i = g[i].next){
            int v = g[i].to , dv = g[i].dis;
            if(d[k] + dv < d[v]){
                r.Del(v);
                r.add(v , k , dv , g.eref[i]);
                d[v] = d[k] + dv;
                q.push((Node){d[v] , v});
                f[v] = f[k];
            }
            else if(d[k] + dv == d[v]) (f[v] += f[k]) %= mod , r.add(v , k , dv , g.eref[i]);
        }
    }
    for(int i = 1 ; i <= m ; ++i){
        if(d[er[i].fr] + er[i].dis == d[er[i].to])
    		val[i] = true;
    }
}
inline void DP()
{
    std::queue<int> q;
    for(int i = 1 ; i <= n ; ++i){
    	for(int j = r(i) ; j ; j = r[j].next){
    		if(r.valid(j) && !t[i])
    			++t[i];
        }
    }
    for(int i = 1 ; i <= n ; ++i)
        if(!r.rd[i])
            q.push(i);
    while(!q.empty())
    {
        int k = q.front();
        q.pop();
        for(int i = r(k) ; i ; i = r[i].next){
        	if(!r.valid(i))	continue;
            int v = r[i].to;
            (t[v] += t[k]) %= mod;
            --r.rd[v];
            if(!r.rd[v])	q.push(v);
        }
    }
            
}
inline void Solve(int S)
{
    std::memset(val,false,sizeof(val));
    std::memset(f,0,sizeof(f));
    std::memset(t,0,sizeof(t));
    r.clear();
    Create(S);
    DP();
    for(int i = 1 ; i <= m ; ++i)
        if(val[i]){
            int u = er[i].fr , v = er[i].to;
            (ans[i] += f[u] * t[v] % mod) %= mod;
        }
}
int main()
{
    scanf("%d%d",&n,&m);
    int num = 0;
    for(int i = 1 ; i <= m ; ++i){
        int x , y , d;
        scanf("%d%d%d",&x,&y,&d);
        g.add(x,y,d,i) , er[++num].fr = x , er[num].to = y, er[num].dis = d;
    }
    for(int i = 1 ; i <= n ; ++i){
        Solve(i);
    }
    for(int i =  1;  i <= m ; ++i)
        printf("%lld\n",ans[i]);
}

6个小时后终于AC了本题，某些血的教训必须说一说。。。

  • 首先，假如这道题比较复杂，功能模块比较多，那么不妨写完一个模块就调试一下其正确性，这非常重要
  • 一定要保持头脑冷静，注意各种细节，比如数组没有清空，一些写的完全不对的地方等等。。
  • 不要弃疗，要越战越勇。也许离正解就差一个细节。

各种错误比如：

1
g.add(x,y,d,i) , er[++num].fr = x , er[num].to, er[num].dis;

与上文对比效果极佳。

这道题是道不错的图论好题。

开始刷AC自动机

先讲讲AC自动机的原理。

AC自动机是一种有限状态自动机，可以在O(n + m*l)的时间里完成匹配。

与KMP不同的是AC自动机所匹配的最大相同前后缀可以来自其他模式串而不必只是它自己，这意味着母串匹配的复杂度和KMP是相同的。

原理大概就是这样。。

今天挺颓（多亏了那道让我写了6小时的题），AC自动机的题连同Hash的题下周全完成就OK。

写了写模板代码，虽然懂了原理 ， 对于优化还是有点不懂。。

Code：

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <queue>
#define maxn 1000005
#define maxc 26
int id[maxn] , idx , cur = 1;
char s[maxn];
struct AC_Automaton
{
	int tr[maxn][maxc] , tot , next[maxn];
	bool Ma[maxn];
	inline void insert(char* s)
	{
		int len = std::strlen(s + 1) , u = 1;
		for(int i = 1 ; i <= len ; ++i){
			int c = s[i] - 97;
			if(!tr[u][c])	tr[u][c] = ++ tot; 
			u = tr[u][c];
		}
		Ma[u] ++;
	}
	inline void GetFail()
	{
		std::queue<int> q;
		for(int i = 0 ; i < 26 ; ++i)
			tr[0][i] = 1;
		q.push(1) , next[1] = 0;
		while(!q.empty())
		{
			int k = q.front();
			q.pop();
			for(int i = 0 ; i < 26 ; ++i){
				if(!tr[k][i])	tr[k][i] = tr[next[k]][i];
				else{
					q.push(tr[k][i]);
					next[tr[k][i]] = tr[next[k]][i];
				}
			}
		}
	}
	inline int find(char* s)
	{
		int len = std::strlen(s + 1);
		int u = 1 , ans = 0;
		for(int i = 1 ; i <= len ; ++i){
			u = tr[u][s[i]-97];
			++ans;
		}
		return ans;
	}
}