1768 種樹 3 時(shí)間限制: 2 s 空間限制: 256000 KB 題目等級 : 鉆石 Diamond 題目描述 Description 為了綠化鄉(xiāng)村，H村積極響應(yīng)號召，開始種樹了。 H村里有n幢房屋，這些屋子的排列順序很有特點(diǎn)，在一條直線上。于是方便起見，我們給它們標(biāo)上1~n。樹就種在房子前面的空地上。 同時(shí)，村民們向村長提出了m個(gè)意見，每個(gè)意見都是按如下格式：希望第li個(gè)房子到第ri個(gè)房子的房前至少有ci棵樹。 因?yàn)槊總€(gè)房屋前的空地面積有限，所以每個(gè)房屋前最多只能種ki棵樹。 村長希望在滿足村民全部要求的同時(shí)，種最少的樹以節(jié)約資金。請你幫助村長。 輸入描述 Input Description 輸入第1行，包含兩個(gè)整數(shù)n，m。 第2行，有n個(gè)整數(shù)ki。 第3~m+1行，每行三個(gè)整數(shù)li，ri，ci。 輸出描述 Output Description 輸出1個(gè)整數(shù)表示在滿足村民全部要求的情況下最少要種的樹。村民提的要求是可以全部滿足的。 樣例輸入 Sample Input 4 3 3 2 4 1 1 2 4 2 3 5 2 4 6 樣例輸出 Sample Output 8 數(shù)據(jù)范圍及提示 Data Size & Hint 對于30%的數(shù)據(jù)，0
/*比較簡單的差分約束.但要注意源點(diǎn)的選取. 由約束條件可得(1)dis[y+1]-dis[x]>=z.(2)0<=dis[i]-dis[i-1]<=k[i].因?yàn)槭桥茏铋L路.所以要把(2)式拆成dis[i]-dis[i-1]>=0.dis[i-1]-dis[i]>=-k[i].spfa松弛即可.*/#include<cstring>#include<cstdio>#include<queue>#define MAXN 500001using namespace std;struct data{int v,next,x;}e[MAXN*3];int n,m,k[MAXN],head[MAXN],dis[MAXN],cut;bool b[MAXN];void add(int u,int v,int x){ e[++cut].v=v; e[cut].x=x; e[cut].next=head[u]; head[u]=cut;}int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar(); return x*f;}void spfa(){ memset(dis,-127/3,sizeof dis); queue<int>q;q.push(0);dis[0]=0; while(!q.empty()) { int u=q.front();q.pop();b[u]=false; for(int i=head[u];i;i=e[i].next) { int v=e[i].v; if(dis[v]<dis[u]+e[i].x) { dis[v]=dis[u]+e[i].x; if(!b[v]) b[v]=true,q.push(v); } } } return ;}int main(){ int x,y,z; n=read(),m=read(); for(int i=1;i<=n;i++) k[i]=read(); for(int i=1;i<=m;i++) { x=read(),y=read(),z=read(); add(x-1,y,z); } add(0,1,0); for(int i=1;i<=n;i++) add(i,i+1,0),add(i,i-1,-k[i]); spfa();新聞熱點(diǎn)
疑難解答
