Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <cstring>
- #include <algorithm>
- #include <vector>
- #include <cmath>
- using namespace std;
- const int N = 30,M = 30;
- const int V = 3*N*M;
- const double eps = 1e-9;
- bool cmp(int a,int b) {return a>b;}
- struct edge{
- double cap,flow;
- int to, r_edge;
- edge() {}
- edge(int _to, double _c, int _r ):
- cap(_c), flow(0), to(_to), r_edge(_r) {}
- };
- int n, m, p[N], r[N], d[N], s[M], W;
- int nv;
- vector<edge> g[10000];
- int addV() {g[nv].clear(); return nv++; }
- void addE(int a,int b, double cap){
- g[a].push_back(edge(b, cap, g[b].size()));
- g[b].push_back(edge(a, 0, g[a].size()-1));
- }
- int start, target;
- vector<char> used(V);
- bool dfs(int v,double d){
- if(v == target) return true;
- used[v]=1;
- int sz=g[v].size();
- for (int i=0;i<sz;i++){
- edge &e = g[v][i];
- int u=e.to,r=e.r_edge;
- if(e.flow + d <= e.cap && !used[u] && dfs(u,d)){
- e.flow += d, g[u][r].flow -= d;
- return true;
- }
- }
- return false;
- }
- double maxFlow(){
- double d = 1.0e6, sum=0;
- for(int i=0;i<40;i++,d /= 2)
- while(true){
- used.assign(sizeof(used),0);
- if(!dfs(start,d)) break;
- sum += d;
- }
- return sum;
- }
- bool check( double add ){
- nv=0;
- start=addV();
- target=addV();
- int cheeze=nv;
- for(int i=0;i<n;i++)
- addE(addV(),target,(double)p[i]);
- vector<double> ti;
- for(int i=0;i<n;i++){
- ti.push_back((double)r[i]);
- ti.push_back(d[i] + add);
- }
- sort(ti.begin(),ti.end());
- ti.resize(unique(ti.begin(), ti.end()) - ti.begin());
- for(int i=1;i<(int)ti.size();i++){
- double dt=ti[i]-ti[i-1];
- int vc = nv;
- for(int j=0;j<m;j++)
- addE(start,addV(),dt*s[j]*(j+1));
- for(int j=0;j<m;j++)
- for(int k=0;k<n;k++)
- if((r[k]-eps <= ti[i-1]) && (ti[i] <= d[k]+add+eps))
- addE(vc+j,cheeze+k,dt*s[j]);
- }
- return fabs(maxFlow() - W) < eps;
- }
- int main(){
- scanf("%d%d", &n, &m);
- for(int i=0;i<n;i++){
- scanf("%d%d%d",p+i,r+i,d+i);
- W += p[i];
- }
- for(int i=0;i<m;i++)
- scanf("%d",s+i);
- sort(s,s+m,cmp);
- for(int i=0;i < m-1;i++)
- s[i] -= s[i+1];
- double l=0,r=1.0e9;
- while(r-l<eps){
- double mid=(l+r)/2;
- if(check(mid)) r=mid;
- else l=mid;
- }
- printf("%.7lf\n",l);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement