考研--圖論

1、樸素Dijkstra算法 O(n^2 + m)

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 510;

int n, m;
int g[N][N];
int dist[N];
bool st[N];

int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    
    for(int i = 0;i < n - 1;i ++)
    {
        int t = -1;
        for(int j = 1;j <= n;j ++)
        {
            if(!st[j] && (t == -1 || dist[j] < dist[t]))
                t = j;
        }
        
        st[t] = true;
        
        for(int j = 1;j <= n;j ++)
            dist[j] = min(dist[j], dist[t] + g[t][j]);
    }
    
    if(dist[n] == 0x3f3f3f3f) return -1;
    
    return dist[n];
}
int main()
{
    scanf("%d%d", &n, &m);
    
    memset(g, 0x3f, sizeof g);
    while(m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        g[a][b] = min(g[a][b], c);
    }
    
    printf("%d\n", dijkstra());
    
    return 0;
}

2、spfa

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 100000 + 10, M = 100000 + 10;
// head 表示頭結(jié)點的下標(biāo)
// e[i] 表示節(jié)點i的值秕重,即e[i]是點編號
// ne[i] 表示節(jié)點i的next指針是多少迎变,指向下一個下標(biāo)
// idx 存儲當(dāng)前已經(jīng)用到了哪個點(下標(biāo))
// w[i] 表示i下標(biāo)對應(yīng)的值是w[i]未檩,即可等價成到達(dá)該下標(biāo)i的權(quán)值是w[i]矛辕,即邊的長度
int n, m;
int h[N], w[M], e[M], ne[M], idx;
int dist[N];
bool st[N];//是否在隊列中

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
int spfa()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    queue<int> q;
    q.push(1);
    st[1] = true;//表示1點在隊列中
    while(q.size())
    {
        int t = q.front();
        q.pop();
        
        st[t] = false;
        
        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(dist[j] > dist[t] + w[i]) 
            {
                dist[j] = dist[t] + w[i];
                if(!st[j]) {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
    
    return dist[n];
}
int main()
{
    scanf("%d%d", &n, &m);
    
    memset(h, -1, sizeof h);
    
    while(m --)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
        
    }
    int t = spfa();
    
    if(t == 0x3f3f3f3f) puts("impossible");
    else printf("%d\n", t);
    
    return 0;
}

3、floyd

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 210, INF = 1e9;

int n, m, Q;
int d[N][N];
void floyd()
{
    for(int k = 1;k <= n;k ++)
        for(int i = 1;i <= n;i ++)
            for(int j = 1;j <= n;j ++)
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
int main()
{
    scanf("%d%d%d", &n, &m, &Q);
    for(int i = 1;i <= n;i ++)
        for(int j = 1;j <= n;j ++)
            if(i == j) d[i][j] = 0;
            else d[i][j] = INF;
    
    while(m --)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        d[a][b] = min(d[a][b], c);
    }
    
    floyd();
    
    while(Q --)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        int t = d[a][b];
        if (t > INF / 2) puts("impossible");
        else printf("%d\n", t);
    }
    
    return 0;
}

4熬甚、prim
最小生成樹稠密圖逢渔,O(n^2)

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 510, INF = 0x3f3f3f3f;

int n, m;
int g[N][N];
int dist[N];
bool st[N];

int prim()
{
    memset(dist, INF, sizeof dist);
    int res = 0;
    
    for(int i = 0;i < n;i ++)
    {
        int t = -1;
        for(int j = 1;j <= n;j ++)
        {
            if(!st[j] && (t == -1 || dist[j] < dist[t]))
                t = j;
        }
        
        if(i != 0 && dist[t] == INF) return INF;
        
        st[t] = true;
        
        if(i != 0) res += dist[t];
        
        for(int j = 1;j <= n;j ++)
            dist[j] = min(dist[j], g[t][j]);
    }
    return res;
}
int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1;i <= n; i ++)
        for(int j = 1;j <= n;j ++)
            if(i == j) g[i][j] = 0;
            else g[i][j] = INF;
            
    while(m --)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        g[a][b] = g[b][a] = min(g[a][b], c);
    }
    
    int t = prim();
    
    if(t == INF) puts("impossible");
    else printf("%d\n", t);
    
    return 0;
}

5、Kruskal
最小生成樹稀疏圖乡括,O(mlogm)

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100000 + 10,  M = 200000 + 10, INF = 0x3f3f3f3f;

int n, m;
int p[N];

struct Edge {
    int a, b, w;
    bool operator< (const Edge &t) const {
        return w < t.w;
    }
}edge[M];

int find(int x)
{
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}
int kruskal()
{
    sort(edge, edge + m);
    
    for(int i = 1;i <= n;i ++) p[i] = i;
    
    int res = 0, cnt = 0;
    for(int i = 0;i < m;i ++)
    {
        int a = edge[i].a, b = edge[i].b, w = edge[i].w;
        a = find(a), b = find(b);
        if(a != b) {
            p[a] = b;
            res += w;
            cnt ++;
        }
    }
    if(cnt < n - 1) return INF;
    return res;
}
int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 0;i < m;i ++)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        edge[i] = {a, b, c};
    }
    
    int t = kruskal();
    
    if (t == INF) puts("impossible");
    else printf("%d\n", t);
    
    return 0;
}

6肃廓、拓?fù)渑判?/p>

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 100000 + 10;

int n, m;
int h[N], e[N], ne[N], idx;
int d[N], qv[N], qidx;

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
bool topsort()
{
    queue<int> q;
    for(int i = 1;i <= n;i ++)
        if(d[i] == 0)
            q.push(i);
            
    while(q.size())
    {
        int t = q.front();
        q.pop();
        qv[qidx ++] = t;
        
        for(int i = h[t];i != -1;i = ne[i])
        {
            int j = e[i];
            d[j] --;
            if(d[j] == 0) q.push(j);
        }
    }
    
    return qidx == n;
}
int main()
{
    scanf("%d%d", &n, &m);
    
    memset(h, -1, sizeof h);
    
    for(int i = 0;i < m;i ++)
    {
        int a, b, c;
        scanf("%d%d", &a, &b);
        add(a, b);
        d[b] ++;
    }
    
    if(!topsort()) puts("-1");
    else {
        for (int i = 0; i < n; i ++ ) printf("%d ", qv[i]);
        puts("");
    }
}
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個濱河市诲泌,隨后出現(xiàn)的幾起案子盲赊,更是在濱河造成了極大的恐慌,老刑警劉巖敷扫,帶你破解...
    沈念sama閱讀 217,509評論 6 504
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件哀蘑,死亡現(xiàn)場離奇詭異,居然都是意外死亡葵第,警方通過查閱死者的電腦和手機(jī)绘迁,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 92,806評論 3 394
  • 文/潘曉璐 我一進(jìn)店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來卒密,“玉大人缀台,你說我怎么就攤上這事∠妫” “怎么了膛腐?”我有些...
    開封第一講書人閱讀 163,875評論 0 354
  • 文/不壞的土叔 我叫張陵睛约,是天一觀的道長。 經(jīng)常有香客問我哲身,道長辩涝,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 58,441評論 1 293
  • 正文 為了忘掉前任勘天,我火速辦了婚禮怔揩,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘误辑。我一直安慰自己,他們只是感情好歌逢,可當(dāng)我...
    茶點故事閱讀 67,488評論 6 392
  • 文/花漫 我一把揭開白布巾钉。 她就那樣靜靜地躺著,像睡著了一般秘案。 火紅的嫁衣襯著肌膚如雪砰苍。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 51,365評論 1 302
  • 那天阱高,我揣著相機(jī)與錄音赚导,去河邊找鬼。 笑死赤惊,一個胖子當(dāng)著我的面吹牛吼旧,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播未舟,決...
    沈念sama閱讀 40,190評論 3 418
  • 文/蒼蘭香墨 我猛地睜開眼圈暗,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了裕膀?” 一聲冷哼從身側(cè)響起员串,我...
    開封第一講書人閱讀 39,062評論 0 276
  • 序言:老撾萬榮一對情侶失蹤,失蹤者是張志新(化名)和其女友劉穎昼扛,沒想到半個月后寸齐,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 45,500評論 1 314
  • 正文 獨居荒郊野嶺守林人離奇死亡抄谐,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 37,706評論 3 335
  • 正文 我和宋清朗相戀三年渺鹦,在試婚紗的時候發(fā)現(xiàn)自己被綠了。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片蛹含。...
    茶點故事閱讀 39,834評論 1 347
  • 序言:一個原本活蹦亂跳的男人離奇死亡海铆,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出挣惰,到底是詐尸還是另有隱情卧斟,我是刑警寧澤殴边,帶...
    沈念sama閱讀 35,559評論 5 345
  • 正文 年R本政府宣布,位于F島的核電站珍语,受9級特大地震影響锤岸,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜板乙,卻給世界環(huán)境...
    茶點故事閱讀 41,167評論 3 328
  • 文/蒙蒙 一是偷、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧募逞,春花似錦蛋铆、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,779評論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至纠脾,卻和暖如春玛瘸,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背苟蹈。 一陣腳步聲響...
    開封第一講書人閱讀 32,912評論 1 269
  • 我被黑心中介騙來泰國打工糊渊, 沒想到剛下飛機(jī)就差點兒被人妖公主榨干…… 1. 我叫王不留,地道東北人慧脱。 一個月前我還...
    沈念sama閱讀 47,958評論 2 370
  • 正文 我出身青樓渺绒,卻偏偏與公主長得像,于是被迫代替她去往敵國和親菱鸥。 傳聞我的和親對象是個殘疾皇子芒篷,可洞房花燭夜當(dāng)晚...
    茶點故事閱讀 44,779評論 2 354

推薦閱讀更多精彩內(nèi)容

  • (題目來源:Acwing) 一.圖的遍歷Acwing847 給定一個n個點m條邊的有向圖,圖中可能存在重邊和自環(huán)采缚。...
    _NewMoon閱讀 637評論 0 2
  • 4 算法初步 4.2 散列 線性探查法:沖突后檢查下一位针炉。 平方探查法:沖突后依次檢查 。超出散列表長度扳抽,取余篡帕。 ...
    方木南閱讀 914評論 0 6
  • 圖定義和相關(guān)術(shù)語 抽象看,圖由頂點(Vertex)和邊(Edge)組成贸呢,可記作G(V,E)镰烧。連接邊的兩個頂點一定要...
    一斗閱讀 435評論 0 0
  • 圖的概念 圖是一種非線性的數(shù)據(jù)結(jié)構(gòu),一個圖中有兩類東西,一種是結(jié)點楞陷,一種是邊.我們用V這個集合來表示節(jié)點(vert...
    fredal閱讀 2,328評論 2 14
  • 目錄 1.基本圖算法參見基本的圖算法參見深度優(yōu)先搜索和廣度優(yōu)先搜索專題 2.最小生成樹——無向圖參見最小生成樹 3...
    王偵閱讀 1,518評論 0 1