Advertisement
Guest User

Untitled

a guest
Nov 20th, 2019
167
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.44 KB | None | 0 0
  1. #include <cstdio>
  2. #include <cstring>
  3. #include <algorithm>
  4. #include <vector>
  5. #include <cmath>
  6.  
  7. using namespace std;
  8. const int N = 30,M = 30;
  9. const int V = 3*N*M;
  10. const double eps = 1e-9;
  11.  
  12. bool cmp(int a,int b) {return a>b;}
  13. struct edge{
  14. double cap,flow;
  15. int to, r_edge;
  16. edge() {}
  17. edge(int _to, double _c, int _r ):
  18. cap(_c), flow(0), to(_to), r_edge(_r) {}
  19. };
  20.  
  21. int n, m, p[N], r[N], d[N], s[M], W;
  22.  
  23. int nv;
  24. vector<edge> g[10000];
  25. int addV() {g[nv].clear(); return nv++; }
  26. void addE(int a,int b, double cap){
  27. g[a].push_back(edge(b, cap, g[b].size()));
  28. g[b].push_back(edge(a, 0, g[a].size()-1));
  29. }
  30.  
  31. int start, target;
  32. vector<char> used(V);
  33. bool dfs(int v,double d){
  34. if(v == target) return true;
  35. used[v]=1;
  36. int sz=g[v].size();
  37. for (int i=0;i<sz;i++){
  38. edge &e = g[v][i];
  39. int u=e.to,r=e.r_edge;
  40. if(e.flow + d <= e.cap && !used[u] && dfs(u,d)){
  41. e.flow += d, g[u][r].flow -= d;
  42. return true;
  43. }
  44. }
  45. return false;
  46. }
  47. double maxFlow(){
  48. double d = 1.0e6, sum=0;
  49. for(int i=0;i<40;i++,d /= 2)
  50. while(true){
  51. used.assign(sizeof(used),0);
  52. if(!dfs(start,d)) break;
  53. sum += d;
  54. }
  55. return sum;
  56. }
  57.  
  58. bool check( double add ){
  59. nv=0;
  60. start=addV();
  61. target=addV();
  62. int cheeze=nv;
  63. for(int i=0;i<n;i++)
  64. addE(addV(),target,(double)p[i]);
  65. vector<double> ti;
  66. for(int i=0;i<n;i++){
  67. ti.push_back((double)r[i]);
  68. ti.push_back(d[i] + add);
  69. }
  70. sort(ti.begin(),ti.end());
  71. ti.resize(unique(ti.begin(), ti.end()) - ti.begin());
  72. for(int i=1;i<(int)ti.size();i++){
  73. double dt=ti[i]-ti[i-1];
  74. int vc = nv;
  75. for(int j=0;j<m;j++)
  76. addE(start,addV(),dt*s[j]*(j+1));
  77. for(int j=0;j<m;j++)
  78. for(int k=0;k<n;k++)
  79. if((r[k]-eps <= ti[i-1]) && (ti[i] <= d[k]+add+eps))
  80. addE(vc+j,cheeze+k,dt*s[j]);
  81. }
  82. return fabs(maxFlow() - W) < eps;
  83. }
  84.  
  85. int main(){
  86. scanf("%d%d", &n, &m);
  87. for(int i=0;i<n;i++){
  88. scanf("%d%d%d",p+i,r+i,d+i);
  89. W += p[i];
  90. }
  91. for(int i=0;i<m;i++)
  92. scanf("%d",s+i);
  93. sort(s,s+m,cmp);
  94. for(int i=0;i < m-1;i++)
  95. s[i] -= s[i+1];
  96. double l=0,r=1.0e9;
  97. while(r-l<eps){
  98. double mid=(l+r)/2;
  99. if(check(mid)) r=mid;
  100. else l=mid;
  101. }
  102. printf("%.7lf\n",l);
  103. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement