• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            Stoer_Wagner 算法,求無向圖的最小割

              prim算法不僅僅可以求最小生成樹,也可以求“最大生成樹”。最小割集Stoer-Wagner算法就是典型的應用實例。

                求解最小割集普遍采用Stoer-Wagner算法,不提供此算法證明和代碼,只提供算法思路:

            1.min=MAXINT,固定一個頂點P

            2.從點P用類似prim的s算法擴展出“最大生成樹”,記錄最后擴展的頂點和最后擴展的邊

            3.計算最后擴展到的頂點的切割值(即與此頂點相連的所有邊權和),若比min小更新min

            4.合并最后擴展的那條邊的兩個端點為一個頂點(當然他們的邊也要合并,這個好理解吧?)

            5.轉到2,合并N-1次后結束

            6.min即為所求,輸出min

            prim本身復雜度是O(n^2),合并n-1次,算法復雜度即為O(n^3)

            如果在prim中加堆優化,復雜度會降為O((n^2)logn)


            #include <cmath>

            #include 
            <cstdio>

            #include 
            <memory.h>

            #include 
            <algorithm>

            #include 
            <iomanip>

            #include 
            <iostream>

            #include 
            <vector>

            #include 
            <string>

            #include 
            <queue>

             

            using namespace std;

             

            const int N = 500 + 3;

             

            int n, m;

            int mat[N][N];

            int dist[N];

            int visited[N];

            int del[N];  // true表示該點已經被刪掉

             

            // 結點~n

            int Stoer_Wagner()

            {

                 
            int minCut = INT_MAX;  // 無向圖最小割

                 
            int tmp;

                 
            int i, t, j, k, pre;

                 
            int s = 1;   // 源點

                 memset(del, 
            0sizeof(del));

             

                 
            for (t = 1; t < n; t++)  // n - 1次Maximum Adjacency Search

                 {

                     
            for (i = 1; i <= n; i++)

                          
            if (!del[i])

                               dist[i] 
            = mat[s][i];

             

                     memset(visited, 
            0sizeof(visited));

                     visited[s] 
            = 1;

                     k 
            = s;

                     
            for (i = 1; i <= n - t; i++)  // 每次剩下n - t + 1個結點

                     {

                          tmp 
            = -1e9;

                          pre 
            = k;

                          k 
            = 0;

                          
            for (j = 1; j <= n; j++)

                          {

                               
            if (!del[j] && !visited[j] && dist[j] > tmp)

                               {

                                   k 
            = j;

                                   tmp 
            = dist[j];

                               }

                          }

                          
            if (!k) return 0;  // 不連通

             

                          visited[k] 
            = 1;

                          
            for (j = 1; j <= n; j++)

                               
            if (!del[j] && !visited[j])

                                   dist[j] 
            += mat[k][j];

                     }

             

                     minCut 
            = min(minCut, dist[k]);

                     del[k] 
            = 1;  // 刪除k點

             

                     
            // 合并k點和源點

                     

                     
            for (i = 1; i <= n; i++)

                          
            if (!del[i] && i != pre)

                          {

                               mat[pre][i] 
            += mat[k][i];

                               mat[i][pre] 
            = mat[pre][i];

                          }

                 }

             

                 
            return minCut;

            }

             

            int main ()

            {

                 
            int u, v, w, i;

                 
            while (scanf("%d%d"&n, &m) != EOF)

                 {

                     memset(mat, 
            0sizeof(mat));

                     
            while (m--)

                     {

                          scanf(
            "%d%d%d"&u, &v, &w);

                          
            if (u == v) continue;  

                          mat[u 
            + 1][v + 1+= w;

                          mat[v 
            + 1][u + 1+= w;

                     }

                     printf(
            "%d\n", Stoer_Wagner());

                 }

            }


            posted on 2010-10-25 23:46 yzhw 閱讀(542) 評論(0)  編輯 收藏 引用 所屬分類: graph theory

            <2025年7月>
            293012345
            6789101112
            13141516171819
            20212223242526
            272829303112
            3456789

            導航

            統計

            公告

            統計系統

            留言簿(1)

            隨筆分類(227)

            文章分類(2)

            OJ

            最新隨筆

            搜索

            積分與排名

            最新評論

            閱讀排行榜

            看全色黄大色大片免费久久久| 伊人久久大香线蕉av不卡| 久久午夜羞羞影院免费观看| 狠狠色丁香久久婷婷综合| 亚洲精品无码久久千人斩| 大伊人青草狠狠久久| 成人午夜精品久久久久久久小说 | 久久国产精品99精品国产987| 久久久青草青青亚洲国产免观| 久久久精品视频免费观看| 亚洲中文字幕伊人久久无码| 久久久久99精品成人片欧美| 一级做a爱片久久毛片| 欧美精品九九99久久在观看| 精品久久久久久综合日本| 国产呻吟久久久久久久92| 久久精品国产乱子伦| 99久久免费国产精品热| 国内精品久久国产| 久久香蕉国产线看观看乱码| 久久受www免费人成_看片中文| 国产精品久久久久久久久免费 | 伊人久久大香线蕉影院95| 四虎国产精品免费久久| 久久er热视频在这里精品| 久久久久久伊人高潮影院| 久久99久久无码毛片一区二区| 久久精品人人槡人妻人人玩AV| 久久精品极品盛宴观看| 91久久九九无码成人网站| 99久久免费国产特黄| 亚洲午夜久久久影院伊人| 亚洲国产精品无码久久青草 | 欧美与黑人午夜性猛交久久久| 国产精品久久久久久久| 久久国产色AV免费观看| 色8久久人人97超碰香蕉987| 香蕉久久久久久狠狠色| 中文成人无码精品久久久不卡 | 国产精品久久久久AV福利动漫 | 亚洲国产成人久久综合一区77|