网页型网站,科技项目申报,物流系统网站策划书,wordpress 登录密码验证正题
题目链接:http://poj.org/problem?id1201 题目大意
求一个最少数量的数字集合满足
在li∼ril_i\sim r_ili∼ri的范围的数字至少是cic_ici个 解题思路
设sis_isi表示0∼i0\sim i0∼i的范围内数字个数。然后其实条件就是sr−si≥cs_r-s_i\geq csr−si≥c。…正题
题目链接:http://poj.org/problem?id1201 题目大意
求一个最少数量的数字集合满足
在li∼ril_i\sim r_ili∼ri的范围的数字至少是cic_ici个 解题思路
设sis_isi表示0∼i0\sim i0∼i的范围内数字个数。然后其实条件就是sr−si≥cs_r-s_i\geq csr−si≥c。然后就是差分约束。
但是需要注意si−si−1≤1s_i-s_{i-1}\leq 1si−si−1≤1且si−si−1≥0s_i-s_{i-1}\geq 0si−si−1≥0这两个隐藏条件。 codecodecode
#includecstdio
#includecstring
#includequeue
using namespace std;
const int N50100;
struct node{int to,next,w;
}a[N*4];
int tot,ls[N],f[N],n,m;
bool v[N];
queueint q;
void addl(int x,int y,int w)
{a[tot].toy;a[tot].nextls[x];a[tot].ww;ls[x]tot;
}
void spfa()
{memset(f,0xcf,sizeof(f));q.push(1);v[1]1;f[1]0;while(!q.empty()){int xq.front();q.pop();v[x]0;for(int ils[x];i;ia[i].next){int ya[i].to;if(f[x]a[i].wf[y]){f[y]f[x]a[i].w;if(!v[y]){v[y]1;q.push(y);}}}}
}
int main()
{n50000;scanf(%d,m);for(int i1;im;i){int x,y,w;scanf(%d%d%d,x,y,w);x2;y2;addl(x,y1,w);}for(int i2;in2;i)addl(i-1,i,0),addl(i,i-1,-1);spfa();printf(%d,f[n2]);
}
