• <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>

            bon

              C++博客 :: 首頁(yè) :: 聯(lián)系 :: 聚合  :: 管理
              46 Posts :: 0 Stories :: 12 Comments :: 0 Trackbacks

            常用鏈接

            留言簿(2)

            我參與的團(tuán)隊(duì)

            搜索

            •  

            最新評(píng)論

            • 1.?re: pku 1861
            • 評(píng)論內(nèi)容較長(zhǎng),點(diǎn)擊標(biāo)題查看
            • --edward2
            • 2.?re: pku 3349
            • 大哥超時(shí) 勒
            • --sum
            • 3.?re: pku 3070
            • 學(xué)習(xí)下,哇哈哈
            • --bear
            • 4.?re: poj 3340
            • 不用DFS的,直接有數(shù)學(xué)規(guī)律的,找出滿足條件的最小的數(shù)就可以了
            • --czcomt
            • 5.?re: pku 3070
            • 方法不錯(cuò)額~~~
            • --Zeor

            閱讀排行榜

            評(píng)論排行榜

            本篇作為最短路系列的擴(kuò)展,講如何用圖論知識(shí)對(duì)差分約束系統(tǒng)進(jìn)行建模并求解。

            1. 線性規(guī)劃問(wèn)題(Linear Program)
                假設(shè)給定了一個(gè)m×n矩陣A,列向量x跟b,線性規(guī)劃問(wèn)題可以描述為在約束
                下求解向量
                使得目標(biāo)函數(shù)最大。其中未知量的數(shù)目為n,約束數(shù)目為m。

            2.差分約束系統(tǒng)
               所謂差分約束系統(tǒng)是線性規(guī)劃的一種特殊情況,其中矩陣A的每一行分別有一個(gè)1跟-1其余元素為0。每個(gè)約束都形如

              

            3.如何用最短路算法求解差分約束系統(tǒng)

               首先構(gòu)造約束圖(Constraint Graph)   

               

               其中邊上的權(quán)值為

               

               下面的定理說(shuō)明,可以用Bellman-Ford算法來(lái)求解差分約束系統(tǒng)。

            Theorem 1  設(shè)差分約束系統(tǒng)對(duì)應(yīng)的約束圖為G=(V,E)。若該圖無(wú)負(fù)權(quán)的環(huán),則差分約束系統(tǒng)的一個(gè)可行解為。若該圖有由源可待的帶負(fù)權(quán)的環(huán),則該系統(tǒng)無(wú)可行解。

            Proof 由于帶權(quán)有向圖最短路若有解,則解



            符合三角不等式

            ,即

            因此x是該系統(tǒng)的一個(gè)可行解。
            若約束圖存在由源可達(dá)的帶負(fù)權(quán)的環(huán),不失一般性,設(shè)該回路為



            用反證法,若該圖有解,則有滿足



            將上面式子相加,左邊為0,右邊為該回路的權(quán)值小于0,得到0<0,矛盾。

            下面給出一個(gè)程序。該程序輸入變量數(shù)目、約束數(shù)目以及具體的約束。若有解則輸出解,否則報(bào)錯(cuò)。

             1 #include <iostream>
             2 #define MAXN 200
             3 #define INF 0xfffffff
             4 
             5 using namespace std;
             6 
             7 int list[MAXN][MAXN][2];        // 圖的鏈接表存儲(chǔ)
             8 int deg[MAXN];                    // 每個(gè)頂點(diǎn)的出度
             9 int delta[MAXN];                // 最終存儲(chǔ)最短路的距離
            10 int trace[MAXN];                // trace[i]表示s到i的最短路i的前驅(qū)
            11 int n,e;                            // 頂點(diǎn)數(shù)
            12 
            13 void initialize_single_source()
            14 {
            15     int i;
            16     for(i=1;i<=n;i++) delta[i]=INF;
            17     trace[i]=-1;
            18 }
            19 
            20 void relax(int a,int b)
            21 {
            22     if(delta[list[a][b][0]]>delta[a]+list[a][b][1])
            23         delta[list[a][b][0]]=delta[a]+list[a][b][1];
            24     trace[list[a][b][0]]=a;
            25 }
            26 
            27 bool checkNegtiveCycle()
            28 {
            29     int i,j,k;
            30     for(i=0;i<=n;i++)
            31     {
            32         for(j=0;j<deg[i];j++)
            33         {
            34             if(delta[list[i][j][0]]>delta[i]+list[i][j][1]) return false;
            35         }
            36     }
            37     return true;
            38 }
            39 
            40 bool bellman_ford()
            41 {
            42     int i,j,k;
            43     for(i=1;i<n;i++)
            44     {
            45         for(j=0;j<=n;j++)
            46         {
            47             for(k=0;k<deg[j];k++)
            48             {
            49                 // 這里j跟k的含義不同:j是頂點(diǎn)編號(hào),k是第j個(gè)頂點(diǎn)的第k條邊
            50                 relax(j,k);
            51             }
            52         }
            53     }
            54     return checkNegtiveCycle();
            55 }
            56 
            57 
            58 
            59 void printSolution()
            60 {
            61     int i;
            62     for(i=1;i<=n;i++) printf("x_{%d}=%d\n",i,delta[i]);
            63     return;
            64 }
            65 
            66 int main()
            67 {
            68     int i,j,k,u,v,b;
            69     // 輸入未知量的個(gè)數(shù)
            70     printf("Enter the number of unknowns:");
            71     scanf("%d",&n);
            72     // 輸入約束數(shù)
            73     printf("Enter the number of constrains:");
            74     scanf("%d",&e);
            75     // 輸入約束
            76     printf("Enter constrains in the format of xi(-)xj(<=)bk\n");
            77     for(i=1;i<=e;i++) deg[i]=0;
            78     for(i=1;i<=e;i++)
            79     {
            80         scanf("%d%d%d",&v,&u,&b);
            81         list[u][deg[u]][0]=v;
            82         list[u][deg[u]][1]=b;
            83         deg[u]++;
            84     }
            85     // 添加新的頂點(diǎn)
            86     deg[0]=n;
            87     for(i=0;i<n;i++)
            88     {
            89         list[0][i][0]=i+1;
            90         list[0][i][1]=0;
            91     }
            92     if(bellman_ford()){printSolution();}
            93     else printf("no solution.\n");
            94     return 1;
            95 }


             

            posted on 2008-02-10 16:23 bon 閱讀(317) 評(píng)論(0)  編輯 收藏 引用 所屬分類: Notes on Introduction to Algorithms
            Google PageRank 
Checker - Page Rank Calculator
            久久精品国产亚洲AV不卡| 久久久久亚洲AV成人网人人网站| 亚洲国产成人乱码精品女人久久久不卡| 人妻少妇久久中文字幕 | 国产精品久久久久久久久免费| 伊人久久大香线蕉av不变影院 | 久久AV高清无码| 久久精品国产福利国产秒| 丰满少妇人妻久久久久久| 久久久久一区二区三区| 国产精品美女久久久久av爽 | 香蕉久久影院| 伊人久久大香线焦AV综合影院| 日本久久久久亚洲中字幕| 久久久久99精品成人片直播| 国内精品久久久久| 欧美国产成人久久精品| 狠狠色噜噜色狠狠狠综合久久| 久久天天躁狠狠躁夜夜网站| 91久久国产视频| 久久国内免费视频| 久久超碰97人人做人人爱| 久久国产午夜精品一区二区三区| 久久无码高潮喷水| 久久99久久99小草精品免视看| 色综合久久久久综合99| 人妻无码αv中文字幕久久| 观看 国产综合久久久久鬼色 欧美 亚洲 一区二区 | 国内精品久久久久久不卡影院| 亚洲精品国精品久久99热| 精品久久久久久成人AV| 热久久国产欧美一区二区精品| 久久天堂AV综合合色蜜桃网| 久久久久国产精品嫩草影院| 久久丫精品国产亚洲av| 日本高清无卡码一区二区久久| 精品熟女少妇av免费久久| 亚洲国产日韩欧美综合久久| 国产—久久香蕉国产线看观看| 亚洲va久久久噜噜噜久久狠狠| 久久国产香蕉视频|