哪些公司做企业网站,简单自适应网站,wordpress 导航站主题,潜江资讯网招聘信息手机版d[i]表示在[0,i]这个区间内一共选了d[i]个数 对于每个为[ai,bi]的区间#xff0c;你必须在这个区间上至少取ci个不同的整数#xff0c;用d[i]如何表示#xff1f; d[ bi ]-d[ ai-1 ] ci Edge:(ai-1 - bi) val ci 另外#xff1a; 0d[i]-d[i-1]1 对应边Ed…d[i]表示在[0,i]这个区间内一共选了d[i]个数 对于每个为[ai,bi]的区间你必须在这个区间上至少取ci个不同的整数用d[i]如何表示 d[ bi ]-d[ ai-1 ] ci Edge:(ai-1 - bi) val ci 另外 0d[i]-d[i-1]1 对应边Edge:(i-1,i) val0 Edge(i,i-1) val-1 可以令d[maxa-1]0 那么最后d[maxb]-d[maxa-1] 就是最后的答案。 #include cstdio#include iostream#include queue#include string.husing namespace std;#define INF 0x3f3f3f3f#define N 200001int first[N],e,d[N], w[N],v[N],next[N];int n,m;bool inq[N];void init(){ e0; memset(first,-1,sizeof(first)); memset(inq,0,sizeof(inq));}void addedge(int a,int b,int x){ v[e]b; next[e]first[a]; w[e]x; first[a]e;}void SPFA(int min1,int max1){ for(int imin11;imax1;i){ d[i]-INF; } d[min1]0; queueint q; q.push(min1); inq[min1] 1; while(!q.empty()){ int ith q.front(); q.pop(); inq[ith] 0; for(int i first[ith];i ! -1;i next[i]){ if(d[v[i]]d[ith]w[i]){ d[v[i]] d[ith]w[i]; if(!inq[v[i]]){ q.push(v[i]); inq[v[i]] 1; } } } }}int main(){ // freopen(test.txt,r,stdin); int t,a,b,x; scanf(%d,t); init(); int s130,e0; for(int i0;it;i){ scanf(%d%d%d,a,b,x); addedge(a-1,b,x); if(a-1s)sa-1; if(be)eb; } for(int is;ie;i){ addedge(i,i1,0); addedge(i1,i,-1); } SPFA(s,e); printf(%d\n,d[e]); return 0;}转载于:https://www.cnblogs.com/Mr-Xu-JH/p/3877262.html
