/*

4416 FFF 團(tuán)臥底的后宮

?

?時(shí)間限制: 1 s ?空間限制: 128000 KB ?題目等級(jí) : 黃金 Gold 題解 題目描述?Description

你在某日收到了 FFF 團(tuán)臥底的求助,在他某日旅游回來(lái),他的后宮們出現(xiàn)了一些不可調(diào)和的矛盾,如果 FFF 團(tuán)臥底把自己的寶貝分給 a 號(hào)妹子,那么 b 號(hào)妹子至少要在站在 a 號(hào)妹子的右邊距離 d,妹子才愿意得到那個(gè)寶貝。可是后宮里也有玩得好的妹子呀,她們總是渴望親近一點(diǎn),如果把自己的寶貝分給 a 號(hào)妹子,那么與她親近的妹子與 a 號(hào)妹子的距離不會(huì)超過(guò) l。現(xiàn)在總共有 n 個(gè)妹子,k 個(gè)這樣的矛盾關(guān)系,m 個(gè)親近關(guān)系。假設(shè)他的寶貝是無(wú)限的,保證每一個(gè)妹子都有寶貝的情況下,第 n 個(gè)妹子和第一個(gè)妹子的最遠(yuǎn)距離是多少呢?

輸入描述?Input Description

第一行為 n,m,k

此后 m 行為親近關(guān)系

此后 k 行為矛盾關(guān)系

輸出描述?Output Description

一行,為最長(zhǎng)的距離*/

//差分約束 如果x與y之間距離小于k，建一條x到y(tǒng)權(quán)值為k的邊；如果x與y之間距離大于k，建一條y到x權(quán)值為-k的邊；
#include<cstdio> #include<iostream> #define M 99999999 using namespace std; int cnt,n,m1,m2,head[1005],next[40005],u[40006],f[1005],t[1005],b[1005]; long long d[1005],v[40005]; int ha,ta; void jia(int a1,int a2,int a3) {cnt++;next[cnt]=head[a1];head[a1]=cnt;u[cnt]=a2;v[cnt]=a3;return; } int main() {int a1,a2,a3;scanf("%d%d%d",&n,&m1,&m2);for(int i=1;i<=m1;i++){scanf("%d%d%d",&a1,&a2,&a3);jia(a1,a2,a3);}for(int i=1;i<=m2;i++){scanf("%d%d%d",&a1,&a2,&a3);jia(a2,a1,-a3);}for(int i=2;i<=n;i++)d[i]=M;ta=1;f[1]=1;t[1]++;b[1]=1;for(;ha!=ta;){ha++;if(ha>1002)ha=1;b[f[ha]]=0;for(int i=head[f[ha]];i;i=next[i])if(d[u[i]]>d[f[ha]]+v[i]){d[u[i]]=d[f[ha]]+v[i];t[u[i]]++;if(t[u[i]]==n+1){printf("-1");return 0;}if(!b[u[i]]){ta++;if(ta>1002)ta=1;b[u[i]]=1;f[ta]=u[i];}}}if(d[n]==M)printf("-2");elseprintf("%lld",d[n]);return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/xydddd/p/5153376.html

總結(jié)

以上是生活随笔為你收集整理的差分约束 4416 FFF 团卧底的后宫的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。