首页 > ACM题库 > HDU-杭电 > HDU 4128-Running relay-网络流-[解题报告]HOJ
2015
04-16

HDU 4128-Running relay-网络流-[解题报告]HOJ

Running relay

问题描述 :

The school track-and-field team is taking a running relay race. There are n (2<=n<=104) members in the team. In order to let everybody participate in the race, each member should run at least d (0<=d<=10) meters. Besides that, everyone can run arbitrary distance. The whole length of the track is L (1<=L<=105) meters.

For the ith member in the team, if he is in a good mood, then it takes him ti seconds (1<=ti<=4×104) to run one meter. If he is in a bad mood, then it takes him si (1<=si<=4×104, 1<=ti<=si) seconds to run one meter.

As the coach of the team, you can assign the running distance of each member in advance. Suppose that, it takes S seconds for the team to complete the relay race if all the members are in bad moods and it takes T seconds for the team to complete the relay race if all the members are in good moods. You do want to have a good score. But you don’t want to have a very bad score even if someone is in a bad mood. So you want to know the minimum value of T on condition that S should not be larger than W (1<=W<=2147483647).

输入:

The input begins with a line containing an integer, indicating the number of test cases. There are no more than 100 test cases.

For each case, the first line begins with four integers — the above mentioned n, d, L and W. Then n lines follow, each representing a member. Each line contains two integers s and t, meaning that the member spends s seconds to run one meter when he/she is in a bad mood, and spends t seconds to run one meter when he/she is in a good mood.

输出:

The input begins with a line containing an integer, indicating the number of test cases. There are no more than 100 test cases.

For each case, the first line begins with four integers — the above mentioned n, d, L and W. Then n lines follow, each representing a member. Each line contains two integers s and t, meaning that the member spends s seconds to run one meter when he/she is in a bad mood, and spends t seconds to run one meter when he/she is in a good mood.

样例输入:

2
2 1 20 141
8 3
6 6
3 8 20 200
8 3
6 6
7 1

样例输出:

88.50
No solution
Hint
In the first case, the first member runs 10.5 meters and the second member runs 9.5 meters. S=8×10.5+6×9.5=141=W, T=3×10.5+6×9.5=88.5. In the second case, every member should run at least 8 meters. But the length of the track is only 20 meters. Because 8×3>20, there is no solution.

之前用对偶定理解决了个网络流,这次又碰到了个半平面交…可惜漏了个约束条件,对偶后的变量少了一个

首先把至少要跑的d先跑完,得到新的L和W

设每个人跑的长度是xi,同时令xn=L-sigma(xi)

我们的目标min(sigma(ti*xi)+tn*(L-sigma(xi)))

变形得(-max(sigma((tn-ti)*xi)))+tn*L

常数不去管它,只考虑max的式子

再来考虑约束条件

1、L-sigma(xi)>=0 ===> sigma(xi)<=L (一开始漏了这个,就变成了一维问题…)

2、sigma(si*xi)+sn*(L-sigma(xi))<=W ===> sigma((si-sn)*xi)<=W-sn*L

写成矩阵形式

max (tn-t1,….ti-tn)*(x1,…xi…)’

约束条件

1、 (1,1,1…)*(x1….xi…)’<=L

2、 (s1-sn…si-sn…)*(x1…xi…)’<=W-sn*L  
(不方便写成一个矩阵,只好分开写)

对偶后

min (y1,y2)*(L,W-sn*L)’

约束条件

(y1,y2)*(1,1,1….)

(s1-sn,…si-sn…)
>=(tn-t1…tn-ti…) (这里必须合到一起了==)

我们把约束条件从矩阵中取出来,变成了n-1个不等式

y1+y2*(si-sn)>=tn-ti

我们发现这就是一个半平面,因此求个半平面交就得到了可行解的区间,然后在各个端点取极值就好了

一开始我漏了一个条件,就变成了一维的了…

然后判无解可以在对偶之前判…

值得一提的是,这个在poj上过不了,poj上时限卡成1s了…

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#define sqr(x) ((x)*(x))
const double oo=1e50,eps=1e-8,pi=acos(-1.0);
using namespace std;
struct point{
    double x,y,z,_,d;
}p[200000];
int s[200000],t[200000];
int n,d,L,W,T,u[200000],st[200000];
double WW,LL,tot,Min;
inline double cr(point e,point r) {return e.x*r.y-e.y*r.x;}
inline double dot(point e,point r) {return e.x*r.x+e.y*r.y+e.z*r.z;}
inline void cross(point p,point q,point &e)
{
    e.x=p.y*q.z-p.z*q.y;
    e.y=p.z*q.x-p.x*q.z;
    e.z=p.x*q.y-p.y*q.x;
}
inline void ori(point &a)
{
    a._=atan2(a.y,a.x);
    a.d=a.z/sqrt(sqr(a.x)+sqr(a.y));
}
inline bool cmp(int i,int j)
{
    double tmp=p[i]._-p[j]._;
    if (fabs(tmp)>pi/2) return tmp<-eps;
    tmp=cr(p[i],p[j]);
    if (fabs(tmp)>eps) return tmp>eps;
    return p[i].d<p[j].d;
}
inline bool check(point L,point T,point I)
{
    point p;
    cross(L,T,p);
    if (dot(p,I)>-eps) return 1;
    return 0;
}
double doit()
{
    int tot=0;
    ++tot,p[tot].x=1,p[tot].y=0,p[tot].z=0;
    ++tot,p[tot].x=0,p[tot].y=1,p[tot].z=0;
    ++tot,p[tot].x=-1,p[tot].y=0,p[tot].z=oo;
    ++tot,p[tot].x=0,p[tot].y=-1,p[tot].z=oo;
    for (int i=1;i<=n-1;i++) {
        ++tot;
        p[tot].x=s[i]-s[n];
        p[tot].y=1;
        p[tot].z=t[i]-t[n];
    }
    for (int i=1;i<=tot;i++) ori(p[i]),u[i]=i;
    sort(u+1,u+tot+1,cmp);
    int h,r;
    st[h=r=1]=u[1]; 
    for (int i=2;i<=tot;i++) {
        if (fabs(cr(p[u[i]],p[u[i-1]]))<eps) continue;
        for (;(h<r) && (!check(p[st[r-1]],p[st[r]],p[u[i]]));r--) ;
        for (;(h<r) && (!check(p[st[h]],p[st[h+1]],p[u[i]]));h++) ;
        st[++r]=u[i];
    }
    for (;(h<r) && (!check(p[st[r-1]],p[st[r]],p[st[h]]));r--) ;
//    for (;(h<r) && (!check(p[st[h]],p[st[h+1]],p[st[r]]));h++) ;
    st[r+1]=st[h];
    double ans=oo;
    for (int i=h;i<=r;i++) {
        point e;
        if ((st[i]==3) || (st[i]==4) || (st[i+1]==3) || (st[i+1]==4)) continue;
        cross(p[st[i]],p[st[i+1]],e);
        e.x/=e.z,e.y/=e.z,e.z=1;
        double sum=(WW-s[n]*LL)*e.x+e.y*LL;
        ans=min(ans,sum);
    }
    return -ans;
}
int main()
{
    scanf("%d",&T);
    for (;T;T--) {
        scanf("%d%d%d%d",&n,&d,&L,&W);
        LL=L-d*n,WW=W;
        tot=0,Min=oo;
        for (int i=1;i<=n;i++) {
            scanf("%d%d",&s[i],&t[i]);
            WW-=s[i]*d;
            tot+=d*t[i];
            Min=min(Min,(double)s[i]);
        }
        if (WW<0 || LL<0) {
            printf("No solution\n");
            continue;
        }
        if (1==n) {
            if (L*s[1]>W) printf("No solution\n");
            else printf("%.2lf\n",(double)L*t[1]);
            continue;
        }
        if (Min*LL>WW) {
            printf("No solution\n");
            continue;
        }
        double ans=doit()+t[n]*LL+tot;
        if (ans<-eps) {
            printf("No solution\n");
            continue;
        }
//        cout<<low<<' '<<lim<<' '<<WW-s[n]*LL<<endl;
        printf("%.2lf\n",fabs(ans));
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/huyuncong/article/details/12953377


  1. I go through some of your put up and I uncovered a good deal of expertise from it. Many thanks for posting this sort of exciting posts

  2. #include <cstdio>

    int main() {
    //answer must be odd
    int n, u, d;
    while(scanf("%d%d%d",&n,&u,&d)==3 && n>0) {
    if(n<=u) { puts("1"); continue; }
    n-=u; u-=d; n+=u-1; n/=u;
    n<<=1, ++n;
    printf("%dn",n);
    }
    return 0;
    }

  3. 这道题这里的解法最坏情况似乎应该是指数的。回溯的时候
    O(n) = O(n-1) + O(n-2) + ….
    O(n-1) = O(n-2) + O(n-3)+ …
    O(n) – O(n-1) = O(n-1)
    O(n) = 2O(n-1)