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;
}