HDU 1384 Intervals （差分约束） - c++编程基础

TOP

HDU 1384 Intervals （差分约束）

2015-07-20 17:45:40 来源: 作者: 【大中小】浏览:3次

Sample Input

Sample Output

题意：给你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 
  
   
#include 
   
     #include 
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include 
         
           #include
          
            #include
            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
            
             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]
             
              b) b=v+1; add(u,v+1,w); } for(int i=a;i


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：poj 1163 The Triangle (动态规划..	下一篇：hdu 4288 Coder（树形结构-线段树..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: