[spfa][區(qū)間問(wèn)題]
背景
你知道嗎，SQ Class的人都很喜歡打CS。（不知道CS是什么的人不用參加這次比賽）。
描述
今天，他們?cè)诖蛞粡埥蠨USTII的地圖，萬(wàn)惡的恐怖分子要炸掉藏在A區(qū)的SQC論壇服務(wù)器！我們SQC的人誓死不屈，即將于恐怖分子展開(kāi)激戰(zhàn)，準(zhǔn)備讓一個(gè)人守著A區(qū)，這樣恐怖分子就不能炸掉服務(wù)器了。（一個(gè)人就能守住??這人是機(jī)械戰(zhàn)警還是霹靂游俠？）
但是問(wèn)題隨之出現(xiàn)了，由于DustII中風(fēng)景秀麗，而且不收門(mén)票，所以n名反恐精英們很喜歡在這里散步，喝茶。他們不愿意去單獨(dú)守在荒無(wú)人煙的A區(qū)，在指揮官的一再命令下，他們終于妥協(xié)了，但是他們每個(gè)人都要求能繼續(xù)旅游，于是給出了自己的空閑時(shí)間，而且你強(qiáng)大的情報(bào)系統(tǒng)告訴了你恐怖份子計(jì)劃的進(jìn)攻時(shí)間（從s時(shí)刻到e時(shí)刻）。

當(dāng)然，精明的SQC成員不會(huì)為你免費(fèi)服務(wù)，他們還要收取一定的傭金（注意，只要你聘用這個(gè)隊(duì)員，不論他的執(zhí)勤時(shí)間多少，都要付所有被要求的傭金）。身為指揮官的你，看看口袋里不多的資金（上頭真摳！），需要安排一個(gè)計(jì)劃，雇傭一些隊(duì)員，讓他們?cè)诒ＷC在進(jìn)攻時(shí)間里每時(shí)每刻都有人員執(zhí)勤，花費(fèi)的最少資金。
格式
輸入格式
第一行是三個(gè)整數(shù)n(1≤n≤10000)，s和e（1≤s≤e≤90000）。

接下來(lái)n行，描述每個(gè)反恐隊(duì)員的信息：空閑的時(shí)間si, ei（1≤si≤ei≤90000）和傭金ci（1≤ci≤300000）。

輸出格式
一個(gè)整數(shù)，最少需支付的傭金，如果無(wú)解，輸出“-1”。

樣例1
樣例輸入1
3 1 5
1 3 3
4 5 2
1 1 1
樣例輸出1[復(fù)制]
5
限制

提示

敵人從1時(shí)刻到4時(shí)刻要來(lái)進(jìn)攻，一共有3名反恐隊(duì)員。第1名從1時(shí)刻到3時(shí)刻有空，要3元錢(qián)（買(mǎi)糖都不夠??）。以此類推。

一共要付5元錢(qián)，選用第1名和第2名。

來(lái)源
SQ CLASS公開(kāi)編程競(jìng)賽2008——Problem D
Source: WindTalker, liuichou, royZhang

題目思路
這道題的題目可以這樣概括，有一個(gè)區(qū)間[s,t]，然后有一些小區(qū)間，來(lái)覆蓋整個(gè)區(qū)間，可以轉(zhuǎn)成求最短路徑，這里我用SPFA。
可是這樣其實(shí)建圖很難建，
幾個(gè)易錯(cuò)誤的地方：
1.比如第一個(gè)反恐隊(duì)員，可以守[1,6],但是6過(guò)后時(shí)間其他隊(duì)員的錢(qián)可能比一個(gè)[3,~]，還要多，所以這個(gè)隊(duì)員守的過(guò)程中是可以換用其他反恐隊(duì)員的，，。[很垃圾的我做的時(shí)候并沒(méi)有想到這個(gè)很坑爹的地方，然而這個(gè)地方卻是這道題最巧妙的一個(gè)地方。QAQ]
處理方法

for(int i = s; i<=e+1;i++){ ed[++tot]=ii(i,head[i+1],0); head[i+1]=tot;}

每一個(gè)都建一條反邊回去，代價(jià)即為0，i+1到i的邊，這樣的意思就相當(dāng)于這個(gè)時(shí)刻，其他隊(duì)員即使開(kāi)始時(shí)間在這個(gè)時(shí)刻前面也可以跳回去用這個(gè)更優(yōu)的隊(duì)員。
2.這道題給的數(shù)據(jù)范圍是n[1,10000],時(shí)刻點(diǎn)是[1,90000],這個(gè)范圍一定要注意，開(kāi)邊應(yīng)該至少開(kāi)成[90000+10000],n個(gè)人的邊加上90000個(gè)時(shí)刻的反邊，這里的節(jié)點(diǎn)是時(shí)刻，，不要弄成人了。,有些別人的代碼邊開(kāi)的很大，，其實(shí)[90000+10000]就夠了。
3.因?yàn)檫@是區(qū)間，不是單純的點(diǎn)，最好的處理區(qū)間的方法就是加一個(gè)1，什么意思，1__2__3__4__5__6,比如這是一個(gè)區(qū)間，求[1，5]，但是這里的時(shí)刻其實(shí)是一個(gè)“__”,所以其實(shí)點(diǎn)的話是[1,6].
……..原諒我說(shuō)了這么多，我只是越寫(xiě)越覺(jué)得這道題很好QAQ…………

#include<iostream> #include<cstdio> #include<cstring> #include<queue> using namespace std; #define LL long long #define cle(x) memset(x,0,sizeof(x)) #define maxcle(x) memset(x,127,sizeof(x)) #ifdef WIN32 #define AUTO "%I64d" #else #define AUTO "%lld" #endif using namespace std; const int N=90050,INF=0x3f3f3f3f,M=10050; int n,s,e; struct ii{int to,ne,v;ii(int to=0,int ne=0,int v=0):to(to),ne(ne),v(v){ } }ed[N+M];//記住不是N，節(jié)點(diǎn)是時(shí)間節(jié)點(diǎn) int head[N],tot; inline int readin(){int res=0;char ch;while((ch = getchar())>'9'||ch<'0');res=ch-'0';while((ch = getchar())>='0'&&ch<='9')res=res*10+ch-'0';return res; } void init(){n=readin(),s=readin(),e=readin();for(int i = 1; i<= n; i++){int x=readin(),y=readin(),z=readin();if(x<=e&&y>=s){x=max(s,x),y=min(e+1,y+1);//區(qū)間加一ed[++tot]=ii(y,head[x],z);head[x]=tot;}}for(int i = s; i<=e+1;i++){ed[++tot]=ii(i,head[i+1],0);head[i+1]=tot;}//建反邊，！！！！可以中途換其他人使其更優(yōu) } bool inq[N]; LL dis[N]; queue<int>q; void spfa() {q.push(s),inq[s]=1;maxcle(dis);dis[s]=0;bool flag=false;while(!q.empty()){int u=q.front();q.pop(),inq[u]=false;for(int i=head[u];i;i=ed[i].ne){int v=ed[i].to;if(dis[v]>dis[u]+ed[i].v){dis[v]=dis[u]+ed[i].v;if(v==e+1)flag=true;if(!inq[v]){inq[v]=true;q.push(v);} }}}if(!flag)printf("-1\n");else printf(AUTO,dis[e+1]); } int main(){freopen("vijos.in","r",stdin);freopen("vijos.out","w",stdout);init();spfa();return 0; }

。。。祝您AC

總結(jié)

以上是生活随笔為你收集整理的vijos p1404遭遇战的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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