約束差分

http://poj.org/problem?id=3169
對(duì)于任意i號(hào)奶牛没佑,1<=i<N,在距離上應(yīng)該滿足:
D[i+1] - D[i] >= 0
對(duì)于每個(gè)好感的描述(i,j巷帝,k)匆笤,假設(shè)i<=j研侣,體現(xiàn)到距離上的要求就是:
D[j] - D[i] <= k
對(duì)于每個(gè)反感的描述(i,j炮捧,k)庶诡,假設(shè)i<=j,體現(xiàn)到距離上的要求就是:
D[j] - D[i] >= k

寫成我們約定的形式:
D[j] -D[i ]<= k
D[i] - D[j] <= - k
.對(duì)于差分不等式咆课,a - b <= c 末誓,建一條 b 到 a 的權(quán)值為 c 的邊扯俱,求的是最短路,得到的是最大值(本題求的就是最大值)喇澡,對(duì)于不等式 a - b >= c 迅栅,建一條 b 到 a 的權(quán)值為 c 的邊,求的是最長(zhǎng)路晴玖,得到的是最小值库继。

#include<cstdio>
#include<string.h>
using namespace std;
struct Node
{
    int from,to,w;

}edge[20010];
int n,m,k,dis[1010],INF=0x3f3f3f3f;
void init()
{
    memset(dis,INF,sizeof(dis));
    dis[1]=0;
}
bool Bellman_Ford()
{
    int sum=m+k;
    bool flag;
    for(int i=1;i<=n-1;i++)
    {
        flag=true;
        for(int j=0;j<sum;j++)
        {
            int u=edge[j].from,v=edge[j].to,val=edge[j].w;
            if(dis[v]>dis[u]+val)
            {
                dis[v]=dis[u]+val;
                flag=false;
            }
        }
        if(flag) break;
    }
   for(int j=0;j<sum;j++)
   {
        int u=edge[j].from,v=edge[j].to,val=edge[j].w;
            if(dis[v]>dis[u]+val)
            {
                return true;
            }
   }
   return false;
}
void reChange(int &a,int &b)
{
    int temp=a;
    a=b;
    b=temp;
}
int main()
{
    int u,v,val,t;
     scanf("%d%d%d",&n,&m,&k);
        for(int i=0;i<m;i++)
        {
            scanf("%d%d%d",&u,&v,&val);
            if(u>v) reChange(u,v);
            edge[i].from=u;
            edge[i].to=v;
            edge[i].w=val;
        }
        for(int i=m;i<m+k;i++)
        {
            scanf("%d%d%d",&u,&v,&val);
            if(u<v) reChange(u,v);
            edge[i].from=u;
            edge[i].to=v;
            edge[i].w=-val;
        }
        init();
        if(Bellman_Ford()) printf("-1\n");
        else if(dis[n]==INF) printf("-2\n");
        else printf("%d\n",dis[n]);
        //printf("%d\n",INF);
}
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個(gè)濱河市窜醉,隨后出現(xiàn)的幾起案子宪萄,更是在濱河造成了極大的恐慌,老刑警劉巖榨惰,帶你破解...
    沈念sama閱讀 223,002評(píng)論 6 519
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件拜英,死亡現(xiàn)場(chǎng)離奇詭異,居然都是意外死亡琅催,警方通過查閱死者的電腦和手機(jī)居凶,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,357評(píng)論 3 400
  • 文/潘曉璐 我一進(jìn)店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)藤抡,“玉大人侠碧,你說我怎么就攤上這事〔颍” “怎么了弄兜?”我有些...
    開封第一講書人閱讀 169,787評(píng)論 0 365
  • 文/不壞的土叔 我叫張陵十气,是天一觀的道長(zhǎng)猜年。 經(jīng)常有香客問我,道長(zhǎng)焦履,這世上最難降的妖魔是什么贸典? 我笑而不...
    開封第一講書人閱讀 60,237評(píng)論 1 300
  • 正文 為了忘掉前任视卢,我火速辦了婚禮,結(jié)果婚禮上廊驼,老公的妹妹穿的比我還像新娘据过。我一直安慰自己,他們只是感情好妒挎,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,237評(píng)論 6 398
  • 文/花漫 我一把揭開白布绳锅。 她就那樣靜靜地躺著,像睡著了一般饥漫。 火紅的嫁衣襯著肌膚如雪榨呆。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 52,821評(píng)論 1 314
  • 那天,我揣著相機(jī)與錄音积蜻,去河邊找鬼闯割。 笑死,一個(gè)胖子當(dāng)著我的面吹牛竿拆,可吹牛的內(nèi)容都是我干的宙拉。 我是一名探鬼主播,決...
    沈念sama閱讀 41,236評(píng)論 3 424
  • 文/蒼蘭香墨 我猛地睜開眼丙笋,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼谢澈!你這毒婦竟也來(lái)了?” 一聲冷哼從身側(cè)響起御板,我...
    開封第一講書人閱讀 40,196評(píng)論 0 277
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤锥忿,失蹤者是張志新(化名)和其女友劉穎,沒想到半個(gè)月后怠肋,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體敬鬓,經(jīng)...
    沈念sama閱讀 46,716評(píng)論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,794評(píng)論 3 343
  • 正文 我和宋清朗相戀三年笙各,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了钉答。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 40,928評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡杈抢,死狀恐怖数尿,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情惶楼,我是刑警寧澤右蹦,帶...
    沈念sama閱讀 36,583評(píng)論 5 351
  • 正文 年R本政府宣布,位于F島的核電站鲫懒,受9級(jí)特大地震影響嫩实,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜窥岩,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,264評(píng)論 3 336
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望宰缤。 院中可真熱鬧颂翼,春花似錦、人聲如沸慨灭。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,755評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)氧骤。三九已至呻疹,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間筹陵,已是汗流浹背刽锤。 一陣腳步聲響...
    開封第一講書人閱讀 33,869評(píng)論 1 274
  • 我被黑心中介騙來(lái)泰國(guó)打工镊尺, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留,地道東北人并思。 一個(gè)月前我還...
    沈念sama閱讀 49,378評(píng)論 3 379
  • 正文 我出身青樓庐氮,卻偏偏與公主長(zhǎng)得像,于是被迫代替她去往敵國(guó)和親宋彼。 傳聞我的和親對(duì)象是個(gè)殘疾皇子弄砍,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,937評(píng)論 2 361

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

  • 1. 關(guān)于診斷X線機(jī)準(zhǔn)直器的作用,錯(cuò)誤的是()输涕。 (6.0 分) A. 顯示照射野 B. 顯示中心線 C. 屏蔽多...
    我們村我最帥閱讀 10,617評(píng)論 0 5
  • 今天是來(lái)無(wú)錫的第一個(gè)星期音婶,可算是休息一下了,上周忙搬家莱坎,這周連續(xù)上班衣式,好累啊,今天東東哥哥帶我去吃了飯型奥,吃...
    羅哇閱讀 71評(píng)論 0 0
  • 1瞳收、原型概念 原型是構(gòu)造函數(shù)在編譯階段,由系統(tǒng)為我們創(chuàng)建出的一個(gè)對(duì)象厢汹。(執(zhí)行構(gòu)造函數(shù)代碼時(shí)螟深,js系統(tǒng)會(huì)給這個(gè)構(gòu)造函...
    LorenaLu閱讀 249評(píng)論 0 0
  • 終于就熬到頭啦!每年的這個(gè)時(shí)候烫葬,鋪天蓋地的全是高考的新聞?dòng)嵪⒔缁。屛覀冞@些已經(jīng)從那場(chǎng)“鏖戰(zhàn)”中堅(jiān)持過來(lái)的人免不了的再...
    落墨非白閱讀 196評(píng)論 0 0
  • 01 收到微信團(tuán)隊(duì)的通知 下午正在給合作方講解最新的營(yíng)銷政策,微信噔噔噔的響了幾下搭综,我加的微信群實(shí)在太多了垢箕,雖然屏...
    楚小西閱讀 769評(píng)論 0 0