外贸公司网站空间,网站上的付费文章怎么做,凤阳做网站,网站首页快照P2570 [ZJOI2010]贪吃的老鼠 在Ta的博客查看 显然二分#xff0c;最大流判定 要满足两个条件#xff1a; (1) 在任一时刻#xff0c;一只老鼠最多可以吃一块奶酪#xff1b; (2) 在任一时刻#xff0c;一块奶酪最多被一只老鼠吃。 先按照奶酪的边界进行离散化#xff0c…P2570 [ZJOI2010]贪吃的老鼠 在Ta的博客查看 显然二分最大流判定 要满足两个条件 (1) 在任一时刻一只老鼠最多可以吃一块奶酪 (2) 在任一时刻一块奶酪最多被一只老鼠吃。 先按照奶酪的边界进行离散化 变成num个块就可以知道每个时间有哪些奶酪了 把每个老鼠拆成num个点 初步 每个老鼠的每个时间的奶酪连接O(len*speed) 首先每个老鼠每个时间段吃的是有限的显然保证1 但是不能保证(2) 改进 考虑让每一个奶酪在时间段只能 证明不会咕了 总感觉不能一定能满足存在一种方案使得总共时间不会超出 卡精度啊 inf设太大了 并且为了防止被inf卡可以直接记录ret表示流出流量直接返回ret即可 #includebits/stdc.h
#define reg register int
#define il inline
#define fi first
#define se second
#define mk(a,b) make_pair(a,b)
#define numb (ch^0)
#define pb push_back
#define solid const auto
#define enter coutendl
#define pii pairint,int
#define double long double
using namespace std;
typedef long long ll;
templateclass Til void rd(T x){char ch;x0;bool flfalse;while(!isdigit(chgetchar()))(ch-)(fltrue);for(xnumb;isdigit(chgetchar());xx*10numb);(fltrue)(x-x);
}
templateclass Til void output(T x){if(x/10)output(x/10);putchar(x%100);}
templateclass Til void ot(T x){if(x0) putchar(-),x-x;output(x);putchar( );}
templateclass Til void prt(T a[],int st,int nd){for(reg ist;ind;i) ot(a[i]);putchar(\n);}namespace Miracle{
const int N33;
const int P33*33*244;
const double inf1e9;
const double eps1e-8;
int n,m;
struct node{int nxt,to;double w;
}e[2*(P*NNP)];
int hd[P],cnt1;
int p[N],st[N],nd[N];
int sp[N];
double mem[2*N];
int num;
int sum;
void add(int x,int y,double z){e[cnt].nxthd[x];e[cnt].toy;e[cnt].wz;hd[x]cnt;e[cnt].nxthd[y];e[cnt].tox;e[cnt].w0;hd[y]cnt;
}
int d[P];
int s,t;
double dfs(int x,double flow){if(xt) return flow;double resflow;for(reg ihd[x];ireseps;ie[i].nxt){int ye[i].to;if(e[i].wepsd[y]d[x]1){double kdfs(y,min(res,e[i].w));if(!k) d[y]0;res-k;e[i].w-k;e[i^1].wk;}}return flow-res;
}
int q[P],l,r;
bool bfs(){memset(d,0,sizeof d);l1;r0;q[r]s;d[s]1;while(lr){int xq[l];for(reg ihd[x];i;ie[i].nxt){int ye[i].to;if(e[i].weps!d[y]){d[y]d[x]1;q[r]y;if(yt) return true;}}}return false;
}
int id(int x,int y){return m(x-1)*numy;
}
bool che(double mid){memset(hd,0,sizeof hd);cnt1;num0;for(reg i1;im;i){mem[num]st[i];mem[num]nd[i]mid;}sort(mem1,memnum1);numunique(mem1,memnum1)-mem-1;--num;//warning!!!
s0,tid(n,num)1;for(reg i1;im;i){add(i,t,p[i]);}for(reg i1;in;i){for(reg j1;jnum;j){for(reg k1;km;k){if(st[k]mem[j]mem[j1]nd[k]mid){add(id(i,j),k,(double)sp[i]*(mem[j1]-mem[j]));}}add(s,id(i,j),(double)sp[i]*i*(mem[j1]-mem[j]));}}double flow0,ret0;while(bfs()){while(1){flowdfs(s,inf);if(floweps) break;retflow;}}if(retepssum) return true;return false;
}
void clear(){sum0;s0;t0;
}
bool cmp(int x,int y){return xy;
}
int main(){int T;rd(T);while(T--){clear();rd(m);rd(n); for(reg i1;im;i){rd(p[i]);rd(st[i]);rd(nd[i]);sump[i];}for(reg i1;in;i){rd(sp[i]);}sort(sp1,spn1,cmp);sp[n1]0;for(reg i1;in;i){sp[i]-sp[i1];}double L0.0,R1e73;for(reg i1;i60;i){double mid(RL)/2;if(che(mid)) Rmid;else Lmid;}printf(%.10Lf\n,L);}return 0;
}}
signed main(){Miracle::main();return 0;
}/*Author: *Miracle*
*/ 转载于:https://www.cnblogs.com/Miracevin/p/10840899.html
