建图

常用

建图有三种常用方法，以后有多的方法会继续更新

邻接矩阵

邻接矩阵就是所谓的map存图

1
2
3
4
5
6
7
8
9
int map[N][N];//N为最大顶点数
int m;
int u, v, w;
memset(map,-1,sizeof(map));//初始化，默认无副边权
for(int i = 0;i < m;i++){
    cin>>u>>v>>w;
    map[u][v] = w;
    map[v][u] = w;//无向边
}
邻接矩阵的意义

可以思考一下，邻接矩阵到底有什么意义？对邻接矩阵进行次方操作后，新的矩阵有什么意义？

注意一下矩阵乘法的公式

我们对普通的邻接矩阵换一个说法，a[i][j] = 1 表示图上有1种方案可以使从i经过1条边到j。那么根据这个说法，矩阵平方之后之后，新的a[i][j]表示从i到j有a[i][j]种方案使从i经过2条边到j。

因此，邻接矩阵n次方之后里面的每个a[i][j]表示有a[i][j]种方案可以使从i经过n条边到j。

链式前向星

链式前向星储存的是以当前节点为起点的所有边，当前边的to又是下一条边的起点，从而达到存图的目的，储存的是单向边。

edge 储存的是每条边的尾节点，权值，与当前边同一起点的上一条边的编号

head 储存的是以当前点为起点的最后一条边的编号

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
struct node{
	int to;//当前边的目标节点
	int w;//当前边的权值
	int next;//与当前边同一起点的上一条边的编号
}edge[M];
int cnt = 0;
int head[N];
memset(head,-1,sizeof(head));
void add(int u, int v, int w){
    edge[++cnt].to = v;
    edge[cnt].w = w;
    edge[cnt].next = head[u];
    head[u] = cnt;
}
for(int i = 1;i <= n;i++){
    for(int j = head[i];j != -1;j = edge[j].next){//遍历每个顶点的所有边！
        cout<< i << " " << edge[j].to << " " << edge[j].w << endl;
        //******
    }
}

vector存图

vector容器存储的是以i为起点的边的终点

如果有边权可以讲vector中的int改成结构体

无边权

1
2
3
4
vector<int> node[N];
void add(int u, int v){
    node[u].push_back(v);
}

有边权

1
2
3
4
5
6
7
8
9
10
struct edge{
	int to;
	int w;
}e;
vector<edge> node[N];
void add(int u, int v, int w){
	e.to = v;
	e.w = w;
	node[u].push_back(e);
}

各种建图的骚操作

行列缩点

范题：HDU -1045 Fire Net

就是很简单的缩点的思想，但是他是将一行或者一列缩成一个点，因为在一行中和在一列中只能存在一个，即他们有共同特征

如上图，按行将图缩成5个点，按列将图缩为6个点，进行二分匹配即可。因为每匹配一对都代表一个有效点。

最短路

最短路主要有dijkstra，bellman-ford，spfa，floyd，johnson算法

最短路算法 Dijkstra Bellman-Ford Spfa Floyd Johnson
最短路类型 单源最短路 单源最短路 单源最短路 多源最短路 多源最短路
作用于 非负权图 任意图 任意图 任意图 任意图
能否检测负环 不能 能 能 能 能
推荐作用图 稠密图 稀疏图 稀疏图 稠密图 稠密图
时间复杂度 O(MlogN) O(NM) O(NM) O(N^3) O(NMlogM)
空间复杂度 O(M) O(M) O(M) O(n^2) O(N+M)

Dijkstra

关于

dijkstra实际上是一种贪心，从起点出发，逐步更新与选择点相邻的点的距离，然后选择最近的那个点再去更新，直到每个点都去过一次。与prim十分相似，甚至可以说一模一样。

代码

以下代码都是基于链式前向星实现的。

初始版
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int vis[maxn], dis[maxn];
inline int dijkstra(int st, int ed, int n){
	memset(vis, 0, sizeof(vis));
	memset(dis, 0x3f, sizeof(dis));//利用0x3f将dis初始化为最大值，并且dis[0]就是最大值
	dis[st] = 0;//起点距离为0
	for(int i = 0;i < n;i++){
		int now = -1, minn = dis[0];//寻找当前最近的点来进行发散
		for(int j = 1;j <= n;j++){
			if(!vis[j] && dis[j] < minn){
				minn = dis[j];
				now = j;
			}
		}
		if(now == -1) return -1;//没找到说明结束了，全部都是最小值了
		vis[now] = 1;
		for(int j = head[now];j;j = edge[j].next){
			if(!vis[edge[j].to] && dis[edge[j].to] > dis[now] + edge[j].w){//如果利用当前点中转更进，那么果断使用中转值
				dis[edge[j].to] = dis[now] + edge[j].w;
			}
		}
	}
	return dis[ed];
}
堆优化

可以发现，在初始版中最耗时间的是寻找最近的点来发散，那么我们可以利用优先队列让最近的点在最前面来使用，这样就省略了寻找这一步。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
typedef pair<int, int> PII;//先弄一个pair
int vis[maxn], dis[maxn];
inline int dijkstra(int st, int ed){
	memset(vis, 0, sizeof(vis));
	memset(dis, 0x3f, sizeof(dis));
	priority_queue<PII, vector<PII>, greater<PII> > q;//令距离小的先出
	dis[st] = 0;
	q.push(PII(dis[st], st));//先把原点放进去
	PII t;
	while(!q.empty()){
		t = q.top();
		q.pop();
		int now = t.second;
		if(vis[now]) continue;//如果已经更新过了就不用再更新了
		vis[now] = 1;
		for(int i = head[now];i;i = edge[i].next){
			if(!vis[edge[i].to] && dis[edge[i].to] > dis[now] + edge[i].w){
				dis[edge[i].to] = dis[now] + edge[i].w;
				q.push(PII(dis[edge[i].to], edge[i].to));
			}
		}
	}
	return dis[ed];
}

SPFA

关于

SPFA其实与Dij也有相似之处，但是更加侧重与dp，没有贪心的意味，而且dij在解决有负权边的时候就会失效，这个时候就需要spfa，spfa也是bl的队列优化。

思路

Spfa先从一个点出发，然后从当前点开始更新到其他点的距离，这一步称之为松弛操作，然后入队，重复以上步骤。

与dij不同的是，dij每次找最近的点走而且每个点只会去一次，而spfa每个点都可以去，只要下一个点能够更近就可以再去更新一下，一个发现如果存在负环，那么肯定存在去某个点的次数超过n，我们也经常用这个方式来判断图是否存在负环。

代码

SLF优化spfa
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
int vis[maxn];
int dis[maxn];
int num_cnt[maxn];
inline int spfa(int st, int aim, int n){
	memset(dis, INF, memset(dis));
	memset(vis, 0, sizeof(vis));
	dis[st] = 0;
	deque<int> q;
	q.push_front(st);
	vis[st] = 1;
	num[st] = 1;
	int flag = 0;
	int now;
	while(!q.empty()){
		now = q.front();
		q.pop_front();
		vis[now] = 0;
		for(int i = head[now];i;i = edge[i].next){
			if(dis[edge[i].to] > dis[now] + edge[i].w){
				dis[edge[i].to] = dis[now] + edge[i].w;
				num_cnt[edge[i].to] = num_cnt[now] + 1;
				if(num_cnt[edge[i].to] > n) flag = 1;
				if(!vis[edge[i].to]){
					if(!q.empty() && dis[edge[i].to] >= dis[q.front]) q.push_back(edge[i].to);
					else q.push_front(edge[i].to);
					vis[edge[i].to] = 1;
				}
			}
		}
	}
	return flag;
}
LLL+SLF优化spfa
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
int dis[maxn];
int vis[maxn];
int num_cnt[maxn];
inline int spfa(int st, int aim, int n){
	memset(dis, INF, sizeof(dis));
	deque<int> q;
	int now = st;
	dis[now] = 0;
	vis[now] = 1;
	int num = 1;
	int flag = 0;
	num_cnt[now] = 1;
	int sum = 0;
	q.push_front(now);
	while(!q.empty()){
		int now = q.front();
		while(num * dis[now] > sum){
			q.pop_front();
			q.push_back(now);
			now = q.front();
		}
		q.qop_front();
		num--;
		sum -= dis[now];
		vis[now] = 1;
		for(int i = head[now];i;i = edge[i].next){
			if(dis[edge[i].to] > dis[now] + edge[i].w){
				dis[edge[i].to] = dis[now] + edge[i].w;
				num_cnt[edge[i].to] = num_cnt[now] + 1;
				if(num_cnt[edge[i].to] > n) flag = 1;
				if(!vis[edge[i].to]){
					if(!q.empty() && dis[edge[i].to] <= dis[q.front()]) q.push_front(edge[i].to);
					else q.push_back(edge[i].to);
					vis[edge[i].to] = 1;
					sum += dis[edge[i].to];
					num++;
				}
			}
		}
	}
	return flag;
}

二分图

染色法判断二分图

书上给二分图的定义是图上不存在奇数环，最经典的判断方法是染色，即当前点与其相邻的点染两种不同的颜色，如果某个点已经染过了而且颜色与当前点相同，那么这个图不能化为二分图，否则可以按照颜色将图化为一个二分图。

注意染色，注意2^1 = 3, 3 ^ 1 = 2，因此可以用2和1来异或来表示两种不同的颜色。

代码

dfs写法

1
2
3
4
5
6
7
8
9
10
11
12
int color[maxn];
inline int dfs(int now,int c){
	color[now] = c;
	for(int i = head[now];i;i = edge[i].next){
		if(!color[edge[i].to]){
			if(!dfs(edge[i].to, c ^ 1)) return 0;
		}else{
			if(color[edge[i].to] == color[now]) return 0;
		}
	}
	return 1;
}

bfs写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int color[maxn];
inline int bfs(int now){
	queue<int> q;
	bfs[now] = 2;
	q.push(now);
	while(!q.empty()){
		now = q.front();
		q.pop();
		for(int i = head[now];i;i = edge[i].next){
			if(!color[edge[i].to]){
				color[edge[i].to] = color[now] ^ 1;
				q.push(edge[i].to);
			}else{
				if(color[edge[i].to] == color[now]) return 0;
			}
		}
	}
	return 1;
}

匈牙利算法

匈牙利算法常用于求二分图最大流匹配，我更愿称其为凑合凑合算法。

基本思路

匈牙利算法实质上就是一种贪心，就像你找女朋友一样，如果你的目标对象已经有对象了，那么让她的原配去看看还有没有其他选择来把你的目标让给你，然后对他的原配再来一次，重复往返，直到能把你的目标让给你为止，否则你就要单身了。对每个人都这么来一次，就把最多能够匹配的对数求出来了，也就是二分图的最大流匹配。(要想生活过得去，头上总得带点绿)

代码

dfs写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int id[maxn];//原配
int vis[maxn];
inline int dfs(int now){
    for(int i = head[now];i;i = edge[i].next){
        if(!vis[edge[i].to]){
            vis[edge[i].to] = 1;
            if(!id[edge[i].to] || dfs(id[edge[i].to])){
                id[edge[i].to] = now;
                return 1;
            }
        }
    }
    return 0;
}
inline int hungarian(int n){
    int ans;
    for(int i = 1;i <= n;i++){
        memset(vis, 0, sizeof(vis));
        if(dfs(i)) ans++;
    }
    return ans;
}