电子商务网站开发费用,免费虚拟主机管理系统下载,在线crm软件有哪些优势?,德阳建设局官方网站图
注:CSDN貌似不支持较长公式#xff0c;可以复制到Markdown编辑器查看
图的表示
邻接矩阵 空间复杂度 Θ ( V 2 ) Θ(V^2) Θ(V2)邻接链表 空间复杂度 Θ ( V E ) Θ(VE) Θ(VE)
BFS 邻接链表 时间复杂度 Θ ( V E ) Θ(VE) Θ(VE)
void BFS(Graph G, int v) {//…图
注:CSDN貌似不支持较长公式可以复制到Markdown编辑器查看
图的表示
邻接矩阵 空间复杂度 Θ ( V 2 ) Θ(V^2) Θ(V2)邻接链表 空间复杂度 Θ ( V E ) Θ(VE) Θ(VE)
BFS 邻接链表 时间复杂度 Θ ( V E ) Θ(VE) Θ(VE)
void BFS(Graph G, int v) {//从顶点v出发广度优先遍历图Gvisit(v);//访问初始顶点vsited[v] true;//标记访问Enqueue(Q, v);//入队while (!isEmpty(Q)) {DeQueue(Q, v);//出队for (w FirstNeighbor(G, v); w 0; w NextNeighbor(G, v, w))if (!visited[w]) {//w为v未访问邻接顶点visit(w);//访问visited[w] true;//标记EnQueue(Q, w);//进队}}
}无权最短路径问题 前驱子图BFS生成树
DFS 递归是核心 void DFS(Graph G,int v){visit(v);visited[v]true;for(wFirstNeighbour(G,v);w0;wNextNeighor(G,v,w)){if(!visited[w]){DFS(G,w);}}
}Topolpgical sort 拓扑排序是可以用来简单地判环的,若能则无环。 // deg是入度在存图的时候需要录入数据
// A是排序后的数组
int deg[MAXN], A[MAXN];
bool toposort(int n)
{int cnt 0;queueint q;//若是priority_queue,则可以输出字典序最大/小拓扑序for (int i 1; i n; i)if (deg[i] 0)q.push(i);while (!q.empty()){int t q.front();q.pop();A[cnt] t;for (auto to : edges[t]){deg[to]--;if (deg[to] 0) // 出现了新的入度为0的点q.push(to);}}return cnt n;//
}最小生成树
[Kruskal][https://blog.csdn.net/yf_li123/article/details/75195549] , [Prim算法][https://blog.csdn.net/yf_li123/article/details/75148998]
单源最短路径 #mermaid-svg-zlnJVYrGQTqkx5eW {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-zlnJVYrGQTqkx5eW .error-icon{fill:#552222;}#mermaid-svg-zlnJVYrGQTqkx5eW .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-zlnJVYrGQTqkx5eW .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-zlnJVYrGQTqkx5eW .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-zlnJVYrGQTqkx5eW .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-zlnJVYrGQTqkx5eW .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-zlnJVYrGQTqkx5eW .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-zlnJVYrGQTqkx5eW .marker{fill:#333333;stroke:#333333;}#mermaid-svg-zlnJVYrGQTqkx5eW .marker.cross{stroke:#333333;}#mermaid-svg-zlnJVYrGQTqkx5eW svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-zlnJVYrGQTqkx5eW .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-zlnJVYrGQTqkx5eW .cluster-label text{fill:#333;}#mermaid-svg-zlnJVYrGQTqkx5eW .cluster-label span{color:#333;}#mermaid-svg-zlnJVYrGQTqkx5eW .label text,#mermaid-svg-zlnJVYrGQTqkx5eW span{fill:#333;color:#333;}#mermaid-svg-zlnJVYrGQTqkx5eW .node rect,#mermaid-svg-zlnJVYrGQTqkx5eW .node circle,#mermaid-svg-zlnJVYrGQTqkx5eW .node ellipse,#mermaid-svg-zlnJVYrGQTqkx5eW .node polygon,#mermaid-svg-zlnJVYrGQTqkx5eW .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-zlnJVYrGQTqkx5eW .node .label{text-align:center;}#mermaid-svg-zlnJVYrGQTqkx5eW .node.clickable{cursor:pointer;}#mermaid-svg-zlnJVYrGQTqkx5eW .arrowheadPath{fill:#333333;}#mermaid-svg-zlnJVYrGQTqkx5eW .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-zlnJVYrGQTqkx5eW .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-zlnJVYrGQTqkx5eW .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-zlnJVYrGQTqkx5eW .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-zlnJVYrGQTqkx5eW .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-zlnJVYrGQTqkx5eW .cluster text{fill:#333;}#mermaid-svg-zlnJVYrGQTqkx5eW .cluster span{color:#333;}#mermaid-svg-zlnJVYrGQTqkx5eW div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-zlnJVYrGQTqkx5eW :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 最短路径 单源 多源 所有边权为正 存在负边权 朴素Dijikstra O(n^2) 堆优化的Dijiksta O(mlogn) Bellman-Ford O(mn) spfa Floyd O(n^3) Bellman-Ford
//检测有无负环
//spfa可以计算有负环 单元最短路径
void bellman_ford()
{memset(dist, 0x3f, sizeof dist);dist[1] 0;for (int i 0; i k; i ){memcpy(last, dist, sizeof dist);for (int j 0; j m; j ){auto e edges[j];dist[e.b] min(dist[e.b], last[e.a] e.c);}}
}[Topological-sort][https://blog.csdn.net/dragon8462_/article/details/119746134]
//只能有向无环图Dijisktra [Dijkstra算法介绍及其优先队列优化和斐波那契堆优化][https://blog.csdn.net/qq_33903332/article/details/116095232]
//
int dijkstra()
{// 初始化 一号点到起点的距离为0 其他点到起点的距离为正无穷memset(dist, 0x3f, sizeof dist); dist[1] 0;for(int i 0; i n -1; i ) // n - 1迭代{int t -1;// 找到未加到 st 集合的最短距离for(int j 1; j n ; j )if( !st[j] (t -1 || dist[t] dist[j]) )t j;// 将t点加入到集合st[t] true;// 更新从t出去的所有的边他组成的路径能不能更强其他点的距离for(int j 1; j n; j)dist[j] min(dist[j], dist[t] w[t][j]); }
}//堆优化
const int N 1e57;
const int INF 0x3f3f3f3f;
struct Node{int to, w;
};//to指向另一端的结点, w表示边的长度
vectorNode g[N];//邻接表存储图
int n, m, s;//n-结点数, m-边数, s-源点
int d[N];//记录源点s到图中所有结点的最短路
bool vis[N];//在Dijkstra算法中用于记录结点是否访问
void Dijkstra_2(int s) {memset(d, 0x3f, sizeof(d));//初始距离设为INF d[s] 0;//源点到源点的距离为 0//使用优先队列实现堆, 默认以pair的first从大到小排序priority_queue pairint, int q;q.push(make_pair(0, s));//源点放入堆中 while (!q.empty()) {pairint, int t q.top(); q.pop();int from t.second;if (vis[from]) continue;//跳过已经访问过的结点 vis[from] true;//以该点为中间结点更新最短路径 for (int i 0; i g[from].size(); i) {int to g[from][i].to;int w g[from][i].w;if (d[to] d[from] w) {d[to] d[from] w;if (vis[to] false) {//first以负数存储, d小的反而大, 在堆顶 q.push(make_pair(-d[to], to));}}}}
}
所有点对最短路径 Dijisktra跑n遍(不带负权)-Greedy Floyd-Warshall-DP (假设权重可以为负但不能有权重为负的环路。) d i j k d_{ij}^k dijk为从结点 $i $到 j j j 的所有中间结点全部取自集合 { 1 , 2 , . . . , k } \{1,2,...,k\} {1,2,...,k}的一条最短路径的权重。 当 k 0 k 0 k0时也就是从结点 $i $到 j j j 的路径上不包括任何结点。这样路径上只有 ( i , j ) (i,j) (i,j)这一条边此时 d i j 0 w ( i , j ) d_{ij}^0 w(i,j) dij0w(i,j)。 当 k ⩾ 1 k \geqslant 1 k⩾1时又可以分为两种情况 结点 $i $到 j j j 的最短路径 p p p没有经过结点 k k k此时 d i j k d i j k − 1 d_{ij}^k d_{ij}^{k-1} dijkdijk−1。结点 $i $到 j j j 的最短路径 p p p经过结点了 k k k d i j k d i k k − 1 d k j k − 1 d_{ij}^k d_{ik}^{k-1} d_{kj}^{k-1} dijkdikk−1dkjk−1。 D $d_{ij}^k \begin{cases} w(i,j) k0\ min{d_{ij}^{k-1}, d_{ik}^{k-1} d_{kj}^{k-1} } k\geqslant 1\ \end{cases}\$ PI(前驱矩阵) $\pi_{ij}^k \begin{cases} \pi_{ij}^{k-1} d_{ij}^{k-1} \leqslant d_{ik}^{k-1} d_{kj}^{k-1}\ \pi_{kj}^{k-1} d_{ij}^{k-1} \gt d_{ik}^{k-1} d_{kj}^{k-1}\ \end{cases}\$ FLOYD-WARSHALL(W)n W.rowsD0 Wlet P n x n martix initialized with nil//前驱矩阵for i 1 to nfor j 1 to nif i ! j and D[i, j] ∞P[i, j] ifor k 1 to nDk new n x n matrix //可以直接用两个矩阵颠倒for i1 to nfor j 1 to nD[ij] min(Dk-1[ij], Dk-1[ik] Dk-1[kj])$$D^0 \begin{bmatrix} 0 3 8 \infty -4 \ \infty 0 \infty 1 7 \ \infty 4 0 \infty \infty \ 2 \infty -5 0 \infty \ \infty \infty \infty 6 0 \ \end{bmatrix} P^0 \begin{bmatrix} NIL 1 1 NIL 1 \ NIL NIL NIL 2 2 \ NIL 3 NIL NIL NIL \ 4 NIL 4 NIL NIL \ NIL NIL NIL 5 NIL \ \end{bmatrix}\ D^1 \begin{bmatrix} 0 3 8 \infty -4 \ \infty 0 \infty 1 7 \ \infty 4 0 \infty \infty \ 2 5 -5 0 -2 \ \infty \infty \infty 6 0 \ \end{bmatrix} P^1 \begin{bmatrix} NIL 1 1 NIL 1 \ NIL NIL NIL 2 2 \ NIL 3 NIL NIL NIL \ 4 1 4 NIL 1 \ NIL NIL NIL 5 NIL \ \end{bmatrix}\ D^2 \begin{bmatrix} 0 3 8 4 -4 \ \infty 0 \infty 1 7 \ \infty 4 0 5 11 \ 2 5 -5 0 -2 \ \infty \infty \infty 6 0 \ \end{bmatrix} P^2 \begin{bmatrix} NIL 1 1 2 1 \ NIL NIL NIL 2 2 \ NIL 3 NIL 2 2 \ 4 1 4 NIL 1 \ NIL NIL NIL 5 NIL \ \end{bmatrix}\ D^3 \begin{bmatrix} 0 3 8 4 -4 \ \infty 0 \infty 1 7 \ \infty 4 0 5 11 \ 2 5 -5 0 -2 \ \infty \infty \infty 6 0 \ \end{bmatrix} P^3 \begin{bmatrix} NIL 1 1 2 1 \ NIL NIL NIL 2 2 \ NIL 3 NIL 2 2 \ 4 3 4 NIL 1 \ NIL NIL NIL 5 NIL \ \end{bmatrix}\ D^4 \begin{bmatrix} 0 3 -1 4 -4 \ 3 0 -4 1 -1 \ 7 4 0 5 3 \ 2 -1 -5 0 -2 \ 8 5 1 6 0 \ \end{bmatrix} P^4 \begin{bmatrix} NIL 1 4 2 1 \ 4 NIL 4 2 1 \ 4 3 NIL 2 1 \ 4 3 4 NIL 1 \ 4 3 4 5 NIL \ \end{bmatrix}\ D^5 \begin{bmatrix} 0 1 -3 2 -4 \ 3 0 -4 1 -1 \ 7 4 0 5 3 \ 2 -1 -5 0 -2 \ 8 5 1 6 0 \ \end{bmatrix} P^5 \begin{bmatrix} NIL 3 4 5 1 \ 4 NIL 4 2 1 \ 4 3 NIL 2 1 \ 4 3 4 NIL 1 \ 4 3 4 5 NIL \ \end{bmatrix}\\$$ csdn好像不支持这么长的公式 可以参考算法导论或者下面的图片 最大流流网络的最大容量问题最小分割问题
参考https://zhuanlan.zhihu.com/p/356840694
#include queue
#include stdio.h
#include cstring
#define INF 2147483467
using namespace std;
using ll long long;const int maxn 520010, maxm 520010;
int n, m, s, t;struct Edge{ll to, next, weight;
};
Edge edges[maxm];
int edge_cnt 1, head[maxn], cur[maxn];void add(int x,int y,int w){edges[edge_cnt].next head[x];edges[edge_cnt].to y;edges[edge_cnt].weight w;head[x] edge_cnt;
}int level[maxn];
bool bfs(){memset(level, 0, sizeof(level));memcpy(cur, head, sizeof(head));queueint q;q.push(s);level[s] 1;while (!q.empty()){int u q.front();q.pop();for (int i head[u]; i ! 0; i edges[i].next){ll v edges[i].to, flow edges[i].weight;if (flow 0 level[v] 0){level[v] level[u] 1;q.push(v);}} }return (level[t] ! 0);
}int dfs(int p s, int cur_flow INF){if (p t) return cur_flow;ll ret 0;for (int i cur[p]; i ! 0; i edges[i].next){cur[p] i;ll v edges[i].to, vol edges[i].weight;if (level[v] level[p] 1 vol 0){int f dfs(v, min(cur_flow - ret, vol));edges[i].weight - f;edges[i^1].weight f;ret f;if (ret cur_flow) return ret;}}return ret;
}ll dinic(){ll max_flow 0;while (bfs()){max_flow dfs();}return max_flow;
}int main(){scanf(%d %d %d %d, n, m, s, t);for (int i 1; i m ; i){int x, y, w;scanf(%d %d %d, x, y, w);add(x, y, w);add(y, x, 0);}printf(%lld, dinic());return 0;
}
