1.圖

圖(graph)：頂點(diǎn)(vertex)和邊(edge)組成的集合只祠。
邊：點(diǎn)對(duì)(v,w)侍瑟，如果點(diǎn)對(duì)有序，則稱(chēng)該圖為有向圖(digraph)莱预，否則叫無(wú)向圖柠掂。
鄰接(adjacent)：點(diǎn)v和點(diǎn)w鄰接當(dāng)且僅當(dāng)(v,w)是邊。
權(quán)(weigh)或值(cost)：邊的屬性依沮。
路徑(path)：的頂點(diǎn)序列涯贞，其中()是邊，這樣一條路徑的長(zhǎng)(length)是該路徑的邊數(shù)N-1危喉，不包含邊的路徑長(zhǎng)度為0宋渔，路徑(v,v)叫做環(huán)。
簡(jiǎn)單路徑：路徑上的所有頂點(diǎn)互異姥饰，但路徑的起點(diǎn)和終點(diǎn)可以相同傻谁。
回路(cycle)：滿足且長(zhǎng)至少為1的一條路徑，如果回路是簡(jiǎn)單路徑列粪，則稱(chēng)之為簡(jiǎn)單回路审磁。
如果一個(gè)有向圖沒(méi)有回路，則稱(chēng)其為有向無(wú)環(huán)圖（DAG）,有向無(wú)環(huán)圖一定沒(méi)有雙向邊岂座。
對(duì)于一個(gè)無(wú)向圖态蒂，如果任取它的兩個(gè)頂點(diǎn)，總存在一條路徑费什，則稱(chēng)這個(gè)無(wú)向圖為連通圖（connected）钾恢。
對(duì)于一個(gè)有向圖，如果任取它的兩個(gè)頂點(diǎn)鸳址，總存在一條路徑瘩蚪，則稱(chēng)這個(gè)有向圖為強(qiáng)連通圖（strongly connected）。
如果一個(gè)有向圖不是強(qiáng)連通的稿黍，但是它的基礎(chǔ)圖（underlying graph）疹瘦，即對(duì)應(yīng)的無(wú)向圖連通，則它是弱連通圖（weakly connected）巡球。
完全圖（complete graph）：每一對(duì)頂點(diǎn)之間都存在一條邊的圖言沐。

2.圖的表示

鄰接表：對(duì)每個(gè)頂點(diǎn)邓嘹，用一個(gè)表存放所有鄰接的頂點(diǎn)。
實(shí)現(xiàn)：開(kāi)個(gè)vector<int> a[size]险胰， size為點(diǎn)的個(gè)數(shù)汹押。
如果要保存頂點(diǎn)的名字或者權(quán)，需要用map<struct XX,struct XX> a[size]

3.拓?fù)渑判?/h2>

對(duì)于有向無(wú)環(huán)圖起便，如果有一條v到w的路徑棚贾，則把頂點(diǎn)v排在w的前面。
頂點(diǎn)v的入度（indegree）：邊(u,v)的條數(shù)缨睡。
排序方法：先遍歷鄰接表鸟悴，讓所有入度為0的頂點(diǎn)進(jìn)入隊(duì)列陈辱，讓隊(duì)首元素出隊(duì)并將它和它的邊一起刪除奖年，即它指向的頂點(diǎn)入度都減1，重復(fù)以上步驟直到隊(duì)列為空沛贪，出隊(duì)的順序即為拓?fù)渑判蝽樞颉?/p>

4.最短路徑算法

加權(quán)路徑長(zhǎng)：從到的路徑中陋守，所有邊的權(quán)的加和。
無(wú)權(quán)路徑長(zhǎng)：從到的路徑邊數(shù)利赋，即水评。
單源最短路問(wèn)題：給定一個(gè)加權(quán)圖G和一個(gè)頂點(diǎn)s，找出從s到G中的其他頂點(diǎn)的最短加權(quán)路徑媚送。這里先假定權(quán)都是正的中燥，否則反復(fù)走負(fù)邊可能會(huì)使加權(quán)路徑長(zhǎng)無(wú)限小。從s到s的最短路徑為0塘偎。
無(wú)權(quán)最短路：
直接BFS：從s開(kāi)始疗涉，將s記為0，把所有與s鄰接的頂點(diǎn)記為1吟秩，然后不斷擴(kuò)展鄰接的頂點(diǎn)的最短路徑為原來(lái)頂點(diǎn)加1咱扣，直到所有頂點(diǎn)都算過(guò)了。
實(shí)現(xiàn)：
第一行輸入m涵防，n為頂點(diǎn)數(shù)和邊數(shù)闹伪。
以下的n行各有兩個(gè)整數(shù)，為有向邊壮池。
輸入一個(gè)整數(shù)x偏瓤。
輸出第x個(gè)頂點(diǎn)到每個(gè)頂點(diǎn)的最短路徑長(zhǎng)以及最短路徑，如果到不了椰憋，輸出-1.

#include<iostream>
#include<vector>
#include<queue>
#include<string>
#include<sstream>
using namespace std;
int m, n;
struct vertex {
    int num;
    int dist;
    int from;
}v[100];
vector<int> edge[1000];
queue<vertex> q;
int a, b, x;
int len;
int num;
int main() {
    cin >> m >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a >> b;
        edge[a].push_back(b);
    }
    cin >> x;
    for (int i = 1; i <= m; i++) {
        v[i].num = i;
        v[i].dist = -1;
    }
    v[x].dist = 0;
    v[x].from = -1;
    q.push(v[x]);
    while (!q.empty()) {
        vertex now = q.front();
        q.pop();
        num = now.num;
        len = edge[num].size();
        for (int i = 0; i < len; i++) {
            if (v[edge[num][i]].dist == -1) {
                v[edge[num][i]].dist = v[num].dist + 1;
                v[edge[num][i]].from = num;
                q.push(v[edge[num][i]]);
            }
        }
    }
    int temp;
    stringstream ss;
    string out;
    for (int i = 1; i <= m; i++) {
        cout << v[i].dist << endl;
        if (v[i].dist == -1) continue;
        cout << i;
        temp = i;
        ss.clear();
        out.clear();
        while (v[temp].from != -1) {
            ss << "<-" << v[temp].from;
            temp = v[temp].from;
        }
        ss >> out;
        cout << out << endl;
    }
    return 0;
}

時(shí)間復(fù)雜度：
有權(quán)最短路（Djikstra算法）
需要標(biāo)記數(shù)組bool known[n]厅克，來(lái)標(biāo)記到該頂點(diǎn)的最短路徑是否確定。
初始化：把所有頂點(diǎn)都置成unknown熏矿，最短距離都置成已骇。
s到s最短距離置為0离钝，s設(shè)置為known。
對(duì)于和s鄰接的所有頂點(diǎn)褪储，最短距離記為s到它們的帶權(quán)距離卵渴。
找出這些頂點(diǎn)中距離s最近的那個(gè)，它到s的最短距離就是它直接到s的距離鲤竹。（反證：如果能從別的地方過(guò)來(lái)最短浪读，由于權(quán)非負(fù)，它一定不是離s最近的頂點(diǎn)辛藻。）設(shè)這個(gè)頂點(diǎn)為s1碘橘，并把它設(shè)成known。
對(duì)于和s1鄰接的所有頂點(diǎn)吱肌，最短距離記為s1到它們的帶權(quán)距離痘拆。
再找出unknown頂點(diǎn)中s到它的距離最短的那個(gè)，設(shè)這個(gè)頂點(diǎn)為s2氮墨，并把它設(shè)成known纺蛆。
對(duì)于和s2鄰接的所有頂點(diǎn)，更新它們的最短距離（如果加上s2的距離比現(xiàn)有的距離短规揪，就更新）桥氏。
重復(fù)以上操作直到所有的頂點(diǎn)都被標(biāo)記成known。
對(duì)于邊數(shù)很多（）的圖（稠密圖）猛铅，直接遍歷所有unknown頂點(diǎn)字支，找出離s最短的頂點(diǎn)即可，時(shí)間復(fù)雜度奸忽。
實(shí)現(xiàn)：
第一行輸入m堕伪，n為頂點(diǎn)數(shù)和邊數(shù)。
以下的n行各有三個(gè)整數(shù)月杉，為有向邊和它的權(quán)刃跛。
輸入一個(gè)整數(shù)x。
輸出第x個(gè)頂點(diǎn)到每個(gè)頂點(diǎn)的帶權(quán)最短路徑長(zhǎng)以及最短路徑苛萎，如果到不了桨昙，輸出-1.

#include<fstream>
#include<iostream>
#include<vector>
#define INF 1000000
using namespace std;
int m, n;
int a;
int x;
struct edge {
    int to;
    int w;
};

struct vertex {
    int num;
    vector<edge> list;
    bool known;
    int dist;
    int from = -1;
}v[1000];

void printpath(vertex now) {
    if (now.from != -1) {
        printpath(v[now.from]);
        cout << "->";
    }
    cout << now.num;
}

edge temp;
int main() {
    ifstream fin("input.txt");
    fin >> m >> n;
    for (int i = 1; i <= n; i++) {
        fin >> a >> temp.to >> temp.w;
        v[a].list.push_back(temp);
    }
    for (int i = 1; i <= m; i++) {
        v[i].num = i;
        v[i].known = false;
        v[i].dist = INF;
    }
    fin >> x;
    v[x].dist = 0;
    int minnum;
    int mindist;
    int len;
    int num;
    while (1) {
        minnum = -1;
        mindist = INF;
        for (int i = 1; i <= m; i++) {
            if (v[i].known) continue;
            if (v[i].dist < mindist) {
                minnum = i;
                mindist = v[i].dist;
            }
        }
        if (minnum == -1) break;
        v[minnum].known = true;
        len = v[minnum].list.size();
        for (int i = 0; i < len; i++) {
            num = v[minnum].list[i].to;
            if (v[num].known) continue;
            if (v[minnum].dist + v[minnum].list[i].w < v[num].dist) {
                v[num].dist = v[minnum].dist + v[minnum].list[i].w;
                v[num].from = minnum;
            }
        }
    }
    for (int i = 1; i <= m; i++) {
        cout << i << ":" << endl << v[i].dist << endl;
        printpath(v[i]);
        cout << endl;
        cout << endl;
    }
    return 0;
}

相比上面的無(wú)權(quán)最短路：用了文件輸入便于測(cè)試，將鄰接表放進(jìn)了vertex類(lèi)里腌歉，輸出路徑改為了正向輸出（用遞歸實(shí)現(xiàn)）蛙酪。
優(yōu)化：用優(yōu)先隊(duì)列（堆）返回距離s最近的結(jié)點(diǎn)，能把時(shí)間復(fù)雜度降到
先補(bǔ)充一種數(shù)據(jù)結(jié)構(gòu)：鏈?zhǔn)角跋蛐恰?br> 相當(dāng)于一個(gè)多叉樹(shù)翘盖。

int top;
int head[10010];
struct Edge {
    int to;
    int w;
    int next;
}edge[200010];
void add(int u, int v, int w) {
    edge[++top].to = v;
    edge[top].w = w;
    edge[top].next = head[u];
    head[u] = top;
}

https://www.luogu.org/problem/P4779
Djikstra（堆優(yōu)化版）：

#include<iostream>
#include<queue>
#define INF 2147483647
using namespace std;
int n, m, s;
int head[200010], vis[100010], dist[100010];
int top;
struct Edge {
    int to;
    int next;
    int w;
}edge[200010];
struct vertex {
    int num;
    int dist;
    bool operator < (const vertex &x) const {//STL的優(yōu)先隊(duì)列是最大堆桂塞，要重載成最小堆
        if (x.dist < dist) return true;
        else return false;
    }
};
void add(int u, int v, int w) {
    edge[++top].to = v;
    edge[top].w = w;
    edge[top].next = head[u];
    head[u] = top;
}
vertex temp;
void Djikstra() {
    for (int i = 1; i <= n; i++) dist[i] = INF;
    priority_queue<vertex> q;
    dist[s] = 0;
    temp.num = s;
    temp.dist = 0;
    q.push(temp);
    while (!q.empty()) {
        temp = q.top();
        q.pop();
        int u = temp.num;
        if (vis[u]) continue;
        vis[u] = 1;
        for (int i = head[u]; i; i = edge[i].next) {
            int d = edge[i].to;
            if (dist[d] > dist[u] + edge[i].w) {
                dist[d] = dist[u] + edge[i].w;
                if (!vis[d]) {//只用給用到的結(jié)點(diǎn)編號(hào)
                    temp.num = d;
                    temp.dist = dist[d];
                    q.push(temp);
                }
            }
        }
    }
}

int main() {
    int u, v, w;
    cin >> n >> m >> s;
    for (int i = 1; i <= m; i++) {
        cin >> u >> v >> w;
        add(u, v, w);
    }
    Djikstra();
    for (int i = 1; i <= n; i++) cout << dist[i] << ' ';
    return 0;
}

負(fù)權(quán)最短路（不含負(fù)環(huán)）
https://www.luogu.org/problem/P3371
對(duì)于非負(fù)權(quán)圖，Djikstra最優(yōu)馍驯，但是對(duì)于負(fù)權(quán)圖就不行了阁危，只能用SPFA玛痊。
SPFA：用BFS遍歷每一個(gè)結(jié)點(diǎn)u，如果u指向的結(jié)點(diǎn)v原來(lái)的最短路比現(xiàn)在u的最短路加上u到v的距離長(zhǎng)狂打，則更新v的最短路擂煞，同時(shí)由于v之后結(jié)點(diǎn)的最短路也會(huì)改變，要將v進(jìn)入隊(duì)列趴乡，同時(shí)要設(shè)一個(gè)標(biāo)記數(shù)組以防止重復(fù)進(jìn)隊(duì)对省。
這種算法的時(shí)間復(fù)雜度比Djikstra的優(yōu)化版本大：。

#include<iostream>
#include<queue>
const long long inf = 2147483647;
const int maxn = 10005;
const int maxm = 500005;
using namespace std;
int n, m, s, top = 1;
int dist[maxn], inque[maxn], head[maxm];
struct Edge {
    int to;
    int w;
    int next;
}edge[maxm];
void add(int u, int v, int w) {
    edge[++top].to = v;
    edge[top].w = w;
    edge[top].next = head[u];
    head[u] = top;
}
void spfa() {
    queue<int> q;
    for (int i = 1; i <= n; i++) {
        dist[i] = inf;
        inque[i] = 0;
    }
    q.push(s);
    dist[s] = 0;
    inque[s] = 1;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        inque[u] = 0;
        for (int i = head[u]; i > 0; i = edge[i].next) {
            int d = edge[i].to;
            if (dist[d] > dist[u] + edge[i].w) {
                dist[d] = dist[u] + edge[i].w;
                if (inque[d] == 0) {
                    inque[d] = 1;
                    q.push(d);
                }
            }
        }
    }
}
int main() {
    cin >> n >> m >> s;
    for (int i = 1; i <= m; i++ ) {
        int u, v, w;
        cin >> u >> v >> w;
        add(u, v, w);
    }
    spfa();
    for (int i = 1; i <= n; i++) cout << dist[i] << ' ';
    return 0;
}

這種算法要保證圖中不含負(fù)環(huán)（權(quán)值和為負(fù)的環(huán)）晾捏，否則會(huì)無(wú)限循環(huán)蒿涎。
負(fù)環(huán)問(wèn)題
在SPFA中，如果一個(gè)結(jié)點(diǎn)被訪問(wèn)n次惦辛，說(shuō)明它所在環(huán)越加越小劳秋，故存在負(fù)環(huán)，可以設(shè)置一個(gè)cnt數(shù)組保存訪問(wèn)的次數(shù)裙品。
例題：https://www.luogu.org/problem/P3385
注意每一次讀數(shù)據(jù)都要清空cnt和head……
代碼：https://www.luogu.org/record/22610301

5.網(wǎng)絡(luò)流問(wèn)題

https://baijiahao.baidu.com/s?id=1607147031919790970&wfr=spider&for=pc
最大流問(wèn)題：
對(duì)于一個(gè)有權(quán)圖G俗批，選定一個(gè)點(diǎn)S為起點(diǎn)，點(diǎn)T為終點(diǎn)市怎，電流從S流向T，要求對(duì)于所有既不是S又不是T的頂點(diǎn)辛慰，流入的電流等于流出的電流区匠，且流經(jīng)
每一條邊的電流都不超過(guò)該邊的權(quán)，求最多有多少電流能從S流到T帅腌？

增廣路：從S到T的一條路徑驰弄，若選取這條路徑，從S到T的流可以增加速客。
如果一個(gè)狀態(tài)不存在增廣路戚篙，則此狀態(tài)確定的流為最大流。
一個(gè)樸素的想法：從S開(kāi)始BFS溺职，當(dāng)找到一條到T的通路時(shí)岔擂，就把此通路所有邊的權(quán)都減去這條通路上所有邊的最小權(quán)，直到?jīng)]有S到T的通路為止浪耘。
但是這樣不對(duì)乱灵，因?yàn)榭梢詷?gòu)造反例使得這樣計(jì)算的結(jié)果與選擇通路的順序有關(guān)。
EK算法：一開(kāi)始給原來(lái)的圖G的每條邊都補(bǔ)上權(quán)為0的反向邊七冲，每次某一條邊進(jìn)行減法運(yùn)算時(shí)痛倚，它的反向邊同時(shí)進(jìn)行加法運(yùn)算，這樣結(jié)果就與選擇通路的順序無(wú)關(guān)了澜躺。原因是反向邊相當(dāng)于可以把之前走過(guò)來(lái)的人再攆回去蝉稳，從而得到更好的走法抒蚜。
模板題：https://www.luogu.org/problem/P3376
本題數(shù)據(jù)規(guī)模很大，不能用vector（會(huì)超時(shí)）耘戚，而且也不好訪問(wèn)反向邊削锰，也不能用二維數(shù)組（會(huì)超空間），可以用鏈?zhǔn)角跋蛐恰?/p>

#include<iostream>
#include<queue>
#include<algorithm>
#include<memory.h>
#define INF 1<<30
using namespace std;
int n, m, s, t;
int top = 1, head[100010];  //top表示棧頂毕莱，head[u]表示上一個(gè)起點(diǎn)為u的邊器贩。
bool isused[100010];  //標(biāo)記某個(gè)結(jié)點(diǎn)是否用過(guò)
queue<int> q;
struct Edge {
    int to; //終點(diǎn)編號(hào)
    int w; //權(quán)
    int next; //前一個(gè)與它共起點(diǎn)的邊
}edge[200010]; 
struct Pre {
    int v;
    int e;
}pre[100010];  //找到增廣路后，某一個(gè)頂點(diǎn)的前一個(gè)頂點(diǎn)以及以它為終點(diǎn)的邊

void add(int u, int v, int w) { //添加邊
    edge[++top].to = v;
    edge[top].w = w;
    edge[top].next = head[u];
    head[u] = top;//每新加進(jìn)一條邊朋截，就讓它的next指向與它共起點(diǎn)的前一條邊蛹稍；對(duì)于第一條邊，讓它的next=0
}
int x;
int to;
bool bfs() {//廣搜找增廣路
    while (!q.empty()) q.pop(); //清空隊(duì)列
    memset(pre, -1, sizeof(pre)); //初始化標(biāo)記數(shù)組
    memset(isused, 0, sizeof(isused));
    q.push(s); //起點(diǎn)進(jìn)隊(duì)
    isused[s] = 1;  //別忘了把起點(diǎn)設(shè)置為isused部服，因?yàn)橛须p向邊
    while (!q.empty()) { //BFS
        x = q.front();
        q.pop();//取隊(duì)首元素并讓其出隊(duì)
        for (int i = head[x]; i > 0; i = edge[i].next){  //遍歷所有以x為起點(diǎn)的邊
            to = edge[i].to;
            if (!isused[to] && edge[i].w > 0) { //如果終點(diǎn)已經(jīng)用過(guò)唆姐，就不要走這條路了
                pre[to].v = x; //to的前置頂點(diǎn)為x
                pre[to].e = i; //to的前置邊為i
                if (to == t) return 1;  //終點(diǎn)是t，說(shuō)明找到了一條增廣路
                isused[to] = 1;
                q.push(to);
            }
        }
    }
    return 0;
}
int EK() {
    int res = 0;
    while (bfs()) {
        int mi = INF;
        for (int i = t; i != s; i = pre[i].v) {
            mi = min(mi, edge[pre[i].e].w);  //找到增廣路上的最小邊 
        }
        for (int i = t; i != s; i = pre[i].v) {
            edge[pre[i].e].w -= mi; //增廣路上的正向邊減去mi
            edge[pre[i].e ^ 1].w += mi;  
            //由于top從1開(kāi)始廓八，正向邊為2奉芦，4，6...剧蹂，反向邊都是3,5,7....声功，所以它們僅有最后一個(gè)二進(jìn)制位不同
            //用異或可以實(shí)現(xiàn)訪問(wèn)反向邊
        }
        res += mi;
    }
    return res;
}
int main() {
    cin >> n >> m >> s >> t;
    int u, v, w;
    for (int i = 1; i <= m; i++) {
        cin >> u >> v >> w;
        add(u, v, w); //讀入正向邊
        add(v, u, 0); //讀入反向邊
    }
    cout << EK();
    return 0;
}

時(shí)間復(fù)雜度：
二分圖匹配
已知A={,,...,};B={,,...,}，對(duì)于每個(gè)宠叼，都有若干與之匹配先巴，求最多能匹配多少組？
此問(wèn)題可以轉(zhuǎn)化為最大流問(wèn)題：如果能和匹配冒冬，則它們之間存在價(jià)值為1的單向邊伸蚯，再新增兩個(gè)頂點(diǎn)s和t，讓s指向所有a简烤，所有b指向t剂邮，求s到t的最大流即可。
當(dāng)然可以用EK算法横侦，但是求最大流有更優(yōu)的Dinic算法：
先求所有頂點(diǎn)到s的最短距離（BFS）挥萌，然后用dfs求最短距離遞增的增廣路，這樣可以一次找到多條增廣路丈咐。

#include<iostream>
#include<algorithm>
#include<queue>
#include<memory.h>
#define INF 1<<30
using namespace std;
int dep[10010], head[10010];  //dep儲(chǔ)存s到每個(gè)結(jié)點(diǎn)的最短路徑長(zhǎng)
int top = 1;
int maxflow; //最大流
int n, m, s, t;
struct Edge {
    int to;
    int w;
    int next;
}edge[200010];
void add(int u, int v, int w) {
    edge[++top].to = v;
    edge[top].w = w;
    edge[top].next = head[u];
    head[u] = top;
}
bool bfs() {
    memset(dep, 0x3f, sizeof(dep)); //memset的技巧：不能直接設(shè)置大數(shù)瑞眼，但可以設(shè)置0x3f，此時(shí)每個(gè)元素的值為0x3f3f3f3f
    dep[s] = 0; //s結(jié)點(diǎn)為0層
    queue<int> q;
    q.push(s);
    while (!q.empty()) {  //BFS求最短路徑長(zhǎng)
        int u = q.front();
        q.pop();
        for (int i = head[u]; i > 0; i = edge[i].next) {   //遍歷以u(píng)為起點(diǎn)的邊
            int d = edge[i].to;
            if (dep[d] > dep[u] + 1 && edge[i].w > 0) {  //保證u直接能到d結(jié)點(diǎn)比u的層數(shù)深1棵逊，注意要判斷w>0防雙向邊
                dep[d] = dep[u] + 1;
                q.push(d);
            }
        }
    }
    if (dep[t] != 0x3f3f3f3f) return 1; //能到達(dá)t伤疙，說(shuō)明能分層
    return 0; 
}

int dfs(int u,int flow) { //u：當(dāng)前的結(jié)點(diǎn)，flow：從s到當(dāng)前結(jié)點(diǎn)的最大流，返回值：從當(dāng)前結(jié)點(diǎn)到t的最大流
    int rlow = 0; //余量：從當(dāng)前結(jié)點(diǎn)到t的最大流
    if (u == t) return flow;  //已經(jīng)到了t徒像，最大流不再改變
    for (int i = head[u]; i > 0; i = edge[i].next) { //遍歷以u(píng)為起點(diǎn)的邊
        int d = edge[i].to;
        if (edge[i].w > 0 && dep[d] == dep[u] + 1) { //判斷終點(diǎn)是否比起點(diǎn)的層數(shù)多1
            rlow = dfs(d, min(flow, edge[i].w)); //遞歸地搜索能到達(dá)t的最大流黍特，如果到達(dá)不了，rlow=0锯蛀，繼續(xù)搜索別的頂點(diǎn)
            if (rlow > 0) { //如果能到達(dá)灭衷，沿途的正向邊減rlow，負(fù)向邊加rlow
                edge[i].w -= rlow;
                edge[i ^ 1].w += rlow;
                return rlow;
            }
        }
    }
    return 0;//如果搜不到rlow>0旁涤，說(shuō)明按照當(dāng)前層數(shù)排序已經(jīng)沒(méi)有增廣路了翔曲，需要改變層序
}

int Dinic() {//返回最大流
    int lowflow;
    while (bfs()) { //如果能分層
        while (1) {
            lowflow = dfs(s, INF); //返回一條增廣路的最大流
            if (lowflow > 0) maxflow += lowflow; 
            else break; //如果找不到增廣路，break出去改變層序
        }
    }
    return maxflow;
}

int main() {
    cin >> n >> m >> s >> t;
    int u, v, w;
    for (int i = 1; i <= m; i++) {
        cin >> u >> v >> w;
        add(u, v, w);
        add(v, u, 0);
    }
    cout << Dinic();
    return 0;
}

時(shí)間復(fù)雜度：劈愚，適用于邊數(shù)較多的圖瞳遍。
特別地，在二分圖匹配問(wèn)題中為
例題：https://www.luogu.org/problem/P2756
只需要把上面的代碼改一下就行菌羽，設(shè)一個(gè)不是結(jié)點(diǎn)的s和t掠械，讓它們分別指向外籍飛行員和被英國(guó)飛行員指向，再用res數(shù)組保存u指向d的關(guān)系（注意它的位置注祖，必須是能走到終點(diǎn)的情況）猾蒂，輸出即可。
完整代碼：https://www.luogu.org/record/22582768
二分圖匹配還可以用匈牙利算法是晨，這里先欠著……
最小費(fèi)用最大流
https://www.luogu.org/problem/P3381
對(duì)于每條邊有兩個(gè)權(quán)肚菠，分別是流和流過(guò)單位流量的費(fèi)用，要求在最大流的前提下署鸡，求最小費(fèi)用案糙。
把EK算法中的BFS改成SPFA即可，注意SPFA的對(duì)象是費(fèi)用不是流靴庆，對(duì)于反向邊，費(fèi)用要變成負(fù)的怒医。
https://www.luogu.org/record/22610301

6.最小生成樹(shù)

最小生成樹(shù)：對(duì)于一個(gè)無(wú)向圖G炉抒，包含G的所有頂點(diǎn)的樹(shù)中，權(quán)值和最低的樹(shù)叫做G的最小生成樹(shù)稚叹。
只有連通圖有最小生成樹(shù)焰薄，且最小生成樹(shù)不包含環(huán)，即它的邊數(shù)比頂點(diǎn)數(shù)少1扒袖。
求最小生成樹(shù)：https://www.luogu.org/problem/P3366
Prim
適用于稠密圖塞茅。遍歷所有起點(diǎn)u已經(jīng)在樹(shù)上的邊(u,v)，找出權(quán)值最小的邊季率，把它加到最小生成樹(shù)上野瘦。重復(fù)以上步驟直到所有頂點(diǎn)都在樹(shù)上。

#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 5010;
const int maxm = 200010;
const int INF = 1 << 30;
int n, m, u, v, w;
int top, head[maxn], dist[maxn]; //dist:到現(xiàn)在在樹(shù)上的點(diǎn)的最小距離
int num, now;
int res;
bool vis[maxn];
struct Edge {
    int to;
    int next;
    int w;
}edge[maxm*2];//無(wú)向圖，所有的邊都是雙向邊
void add(int u, int v, int w) {
    edge[++top].to = v;
    edge[top].w = w;
    edge[top].next = head[u];
    head[u] = top;
}
void prim() {
    for (int i = 1; i <= n; i++) dist[i] = INF;
    now = 1;
    for (int i = head[1]; i; i = edge[i].next) {
        dist[edge[i].to] = min(dist[edge[i].to], edge[i].w);
    } //從第一個(gè)點(diǎn)開(kāi)始設(shè)置鞭光，用min解決重邊問(wèn)題
    while (++num < n) { //到n結(jié)束吏廉，此時(shí)加了n-1條邊
        int minn = INF;
        vis[now] = 1;
        for (int i = 1; i <= n; i++) {//找到最短的邊，并把它的終點(diǎn)加到樹(shù)上
            if (!vis[i] && minn > dist[i]) {
                minn = dist[i];
                now = i;
            }
        }
        res += minn;
        for (int i = head[now]; i; i = edge[i].next) { //更新dist
            int d = edge[i].to;
            if (dist[d] > edge[i].w && !vis[d]) dist[d] = edge[i].w;
        }
    }
}


int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> u >> v >> w;
        add(u, v, w);
        add(v, u, w);
    }
    prim();
    cout << res;
    return 0;
}

時(shí)間復(fù)雜度：
同理Dijkstra惰许，堆優(yōu)化后時(shí)間復(fù)雜度降到席覆。
以下的模板用了pair模板類(lèi)，同上面的Dijkstra模板相比要精煉許多汹买，因?yàn)閜air重載了小于運(yùn)算符（見(jiàn)前面的某篇筆記）佩伤，而且可以用make_pair構(gòu)造函數(shù)。

#include<iostream>
#include<utility>
#include<queue>
using namespace std;
const int maxn = 5010;
const int maxm = 200010;
const int inf = 1 << 30;
struct Edge {
    int to;
    int w;
    int next;
}edge[maxm*2];
int top, head[maxn], dist[maxn], vis[maxn];
int n, m, u, v, w;
int cnt, res;
typedef pair<int, int> p;//因?yàn)閜air類(lèi)的排序是字典序晦毙，所以first是dist生巡，second是編號(hào)
priority_queue<p, vector<p>, greater<p> > q;//最小堆
void add(int u, int v, int w) {
    edge[++top].to = v;
    edge[top].w = w;
    edge[top].next = head[u];
    head[u] = top;
}
void prim() {
    dist[1] = 0;
    for (int i = 2; i <= n; i++) dist[i] = inf;
    q.push(make_pair(0, 1));//第一個(gè)頂點(diǎn)進(jìn)堆
    while (!q.empty() && cnt < n) {
        int minn = q.top().first;
        int u = q.top().second;
        q.pop();
        if (vis[u]) continue;
        cnt++;
        res += minn;
        vis[u] = 1;
        for (int i = head[u]; i; i = edge[i].next) {//更新頂點(diǎn)距離
            int d = edge[i].to;
            if (!vis[d]&&edge[i].w < dist[d]) {
                dist[d] = edge[i].w;
                q.push(make_pair(dist[d], d));
            }
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> u >> v >> w;
        add(u, v, w);
        add(v, u, w);
    }
    prim();
    if (cnt == n) cout << res;
    else cout<<"orz";
        return 0;
}

Kruskal
適用于稀疏圖。將邊按照權(quán)從小到大排序结序，從權(quán)值最小的邊開(kāi)始選取障斋，如果出現(xiàn)環(huán)則跳過(guò)（用并查集判斷），直到邊數(shù)比總點(diǎn)數(shù)少1徐鹤。

#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 5010;
const int maxm = 200010;
struct Edge {//不用鏈?zhǔn)角跋蛐橇死罚挥么婷總€(gè)邊的權(quán)
    int u;
    int v;
    int w;
    bool operator < (const Edge& x) const {
        return w < x.w;
    }
}edge[maxm];
int fa[5010];
int n, m, res, u, v, cnt;
int find(int x) {//并查集模板
    if (x == fa[x]) return x;
    return fa[x] = find(fa[x]);
}
void kruskal() {
    sort(edge, edge + m); //按邊權(quán)從小到大排序
    for (int i = 0; i < m; i++) {
        u = find(edge[i].u);
        v = find(edge[i].v);
        if (u == v) continue;  //如果成環(huán)（起點(diǎn)和終點(diǎn)已經(jīng)連通）則跳過(guò)
        res += edge[i].w;
        fa[v] = u;//將起點(diǎn)和終點(diǎn)設(shè)為連通
        if (++cnt == n - 1) break;
    }
}
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) fa[i] = i;//初始化并查集
    for (int i = 0; i < m; i++) cin >> edge[i].u >> edge[i].v >> edge[i].w;
    kruskal();
    if(cnt == n-1)cout << res;
    else cout << "orz";
    return 0;
}

7.剩下的先欠著