數(shù)據(jù)結(jié)構(gòu)與算法分析-C++描述 第9章 圖

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):w_1,w_2,...,w_N的頂點(diǎn)序列涯贞,其中(w_i,w_{i+1})是邊,這樣一條路徑的長(zhǎng)(length)是該路徑的邊數(shù)N-1危喉,不包含邊的路徑長(zhǎng)度為0宋渔,路徑(v,v)叫做環(huán)。
簡(jiǎn)單路徑:路徑上的所有頂點(diǎn)互異姥饰,但路徑的起點(diǎn)和終點(diǎn)可以相同傻谁。
回路(cycle):滿足w_1=w_N且長(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):從v_1v_n的路徑中陋守,所有邊的權(quán)的加和。
無(wú)權(quán)路徑長(zhǎng):從v_1v_n的路徑邊數(shù)利赋,即n-1水评。
單源最短路問(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塘偎。
(1)無(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ù)雜度:O(n+m)
(2)有權(quán)最短路(Djikstra算法)
需要標(biāo)記數(shù)組bool known[n]厅克,來(lái)標(biāo)記到該頂點(diǎn)的最短路徑是否確定。
初始化:把所有頂點(diǎn)都置成unknown熏矿,最短距離都置成\infty已骇。
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ù)很多(N=O(M^2))的圖(稠密圖)猛铅,直接遍歷所有unknown頂點(diǎn)字支,找出離s最短的頂點(diǎn)即可,時(shí)間復(fù)雜度O(N^2)奸忽。
實(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ù)雜度降到O((n+m)log_2n)
先補(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;
}

(3)負(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)化版本大:O(MN)

#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)蒿涎。
(4)負(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
(1)最大流問(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ù)雜度:O(nm^2)
(2)二分圖匹配
已知A={a_1,a_2,...,a_n};B={b_1,b_2,...,b_m},對(duì)于每個(gè)a_i宠叼,都有若干b_j與之匹配先巴,求最多能匹配多少組?
此問(wèn)題可以轉(zhuǎn)化為最大流問(wèn)題:如果a_i能和b_j匹配冒冬,則它們之間存在價(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ù)雜度:O(n^2m)劈愚,適用于邊數(shù)較多的圖瞳遍。
特別地,在二分圖匹配問(wèn)題中為O(n^{1/2}m)
例題: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
二分圖匹配還可以用匈牙利算法是晨,這里先欠著……
(3)最小費(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
(1)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ù)雜度:O(n^2)
同理Dijkstra惰许,堆優(yōu)化后時(shí)間復(fù)雜度降到O(mlogn)席覆。
以下的模板用了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;
}

(2)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.剩下的先欠著

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個(gè)濱河市返敬,隨后出現(xiàn)的幾起案子遂庄,更是在濱河造成了極大的恐慌,老刑警劉巖劲赠,帶你破解...
    沈念sama閱讀 222,590評(píng)論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件涛目,死亡現(xiàn)場(chǎng)離奇詭異,居然都是意外死亡凛澎,警方通過(guò)查閱死者的電腦和手機(jī)霹肝,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,157評(píng)論 3 399
  • 文/潘曉璐 我一進(jìn)店門(mén),熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)塑煎,“玉大人沫换,你說(shuō)我怎么就攤上這事∽钐” “怎么了讯赏?”我有些...
    開(kāi)封第一講書(shū)人閱讀 169,301評(píng)論 0 362
  • 文/不壞的土叔 我叫張陵,是天一觀的道長(zhǎng)冷尉。 經(jīng)常有香客問(wèn)我漱挎,道長(zhǎng),這世上最難降的妖魔是什么雀哨? 我笑而不...
    開(kāi)封第一講書(shū)人閱讀 60,078評(píng)論 1 300
  • 正文 為了忘掉前任磕谅,我火速辦了婚禮,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘怜庸。我一直安慰自己当犯,他們只是感情好,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,082評(píng)論 6 398
  • 文/花漫 我一把揭開(kāi)白布割疾。 她就那樣靜靜地躺著嚎卫,像睡著了一般。 火紅的嫁衣襯著肌膚如雪宏榕。 梳的紋絲不亂的頭發(fā)上拓诸,一...
    開(kāi)封第一講書(shū)人閱讀 52,682評(píng)論 1 312
  • 那天,我揣著相機(jī)與錄音麻昼,去河邊找鬼奠支。 笑死,一個(gè)胖子當(dāng)著我的面吹牛抚芦,可吹牛的內(nèi)容都是我干的倍谜。 我是一名探鬼主播,決...
    沈念sama閱讀 41,155評(píng)論 3 422
  • 文/蒼蘭香墨 我猛地睜開(kāi)眼叉抡,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼尔崔!你這毒婦竟也來(lái)了?” 一聲冷哼從身側(cè)響起褥民,我...
    開(kāi)封第一講書(shū)人閱讀 40,098評(píng)論 0 277
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤季春,失蹤者是張志新(化名)和其女友劉穎,沒(méi)想到半個(gè)月后消返,有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體载弄,經(jīng)...
    沈念sama閱讀 46,638評(píng)論 1 319
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,701評(píng)論 3 342
  • 正文 我和宋清朗相戀三年撵颊,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了宇攻。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 40,852評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡倡勇,死狀恐怖尺碰,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情译隘,我是刑警寧澤,帶...
    沈念sama閱讀 36,520評(píng)論 5 351
  • 正文 年R本政府宣布洛心,位于F島的核電站固耘,受9級(jí)特大地震影響,放射性物質(zhì)發(fā)生泄漏词身。R本人自食惡果不足惜厅目,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,181評(píng)論 3 335
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧损敷,春花似錦葫笼、人聲如沸。這莊子的主人今日做“春日...
    開(kāi)封第一講書(shū)人閱讀 32,674評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)。三九已至诱桂,卻和暖如春洋丐,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背挥等。 一陣腳步聲響...
    開(kāi)封第一講書(shū)人閱讀 33,788評(píng)論 1 274
  • 我被黑心中介騙來(lái)泰國(guó)打工友绝, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留,地道東北人肝劲。 一個(gè)月前我還...
    沈念sama閱讀 49,279評(píng)論 3 379
  • 正文 我出身青樓迁客,卻偏偏與公主長(zhǎng)得像,于是被迫代替她去往敵國(guó)和親辞槐。 傳聞我的和親對(duì)象是個(gè)殘疾皇子掷漱,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,851評(píng)論 2 361