首页 > 代码库 > HDU 1384 Intervals (差分约束)
HDU 1384 Intervals (差分约束)
Sample Input
5 3 7 3 8 10 3 6 8 1 1 3 1 10 11 1
Sample Output
6
题意:给你n个数u,v,w;要求在[u,v]区间至少取w个数(整数),求最少要取多少个数。
S[v+1] - S[u] >= w, S[i+1] - S[i] >=0&&<=1,S[i] - S[i+1] <=-1.
在u,v+1之间建一条边,跑一遍SPFA即可。
#include <iostream> #include <stdio.h> #include <string.h> #include<string> #include<math.h> #include<queue> #include<stack> #include <algorithm> #include<vector> #include<map> using namespace std; #define M 100 #define inf 0x3fffffff #define maxn 50005 #define ll long long struct edge { int v,num,next; }e[maxn*4]; int edge_num,a,b,vis[maxn],d[maxn]; int head[maxn]; void add(int a,int b,int c) { e[edge_num].num=b; e[edge_num].v=c; e[edge_num].next=head[a]; head[a]=edge_num++; } int n; void SPFA() { queue<int>q; memset(vis,0,sizeof(vis)); memset(d,-50005,sizeof(d)); /*for(int i=a;i<=b;i++) d[i]=-50005;*/ while(!q.empty()) q.pop(); q.push(a); d[a]=0;vis[a]=1; while(!q.empty()) { int u=q.front(); q.pop(); for(int i=head[u];i!=-1;i=e[i].next) { int v=e[i].num; if(d[v]<d[u]+e[i].v) { d[v]=d[u]+e[i].v; if(!vis[v]) { q.push(v); vis[v]=1; } } } vis[u]=0; } } int main() { while(~scanf("%d",&n)) { edge_num=0; memset(head,-1,sizeof(head)); int u,v,w; a=inf,b=0; while(n--) { scanf("%d%d%d",&u,&v,&w); if(u<a) a=u; if(v+1>b) b=v+1; add(u,v+1,w); } for(int i=a;i<b;i++) { add(i+1,i,-1); add(i,i+1,0); } SPFA(); printf("%d\n",d[b]); } return 0; }
HDU 1384 Intervals (差分约束)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。