首页 > 代码库 > BZOJ 1027 合金(凸包-最小环)

BZOJ 1027 合金(凸包-最小环)

题目链接:http://61.187.179.132/JudgeOnline/problem.php?id=1027

题意:三种合金的材料若干种。需求合金若干种。每种需求合金可以由材料合金混合得到。问最少需要多少种材料能够混合出所有需要的合金?

思路:对于两种材料合金ab,若能够得到需 求合金p,那么p必在线段ab上。这里由于三种合金的和为1,只要二维就够了,也就是是一个二维的问题。那么问题转化成,在平面上,找出最少的点包含所有 的需求合金对应的点(答案为1和2特判一下就行)。两两枚举材料合金xy,若所有需求合金对应的点均在xy左侧,则令g[x][y]=1,否则g[x] [y]=INF。然后再g上求最小环就是答案。因为最小环包含了所有需求合金。

 

struct point {    double x,y,z;        void get()    {        RD(x,y,z);    }        point operator-(point a)    {        a.x=x-a.x;        a.y=y-a.y;        return a;    }        double operator*(point a)    {        return y*a.x-x*a.y;    }        double operator^(point a)    {        return x*a.x+y*a.y;    }};point a[N],b[N];int g[N][N],f[N][N],n,m;int sgn(double x){    if(x>EPS) return 1;    if(x<-EPS) return -1;    return 0;}int OK(point a){    int i;    FOR1(i,m)    {        if(sgn(a.x-b[i].x)||sgn(a.y-b[i].y))        {            return 0;        }    }    return 1;}int OK(point p,point q){    int i;    FOR1(i,m)    {        if(sgn((q-p)*(b[i]-p))<0) return 0;    }    return 1;}int check(point p,point q){    int i;    FOR1(i,m)    {        if(sgn((q-p)*(b[i]-p))!=0) return 0;        if(sgn((q-p)^(b[i]-p))<0) return 0;        if(sgn((p-q)^(b[i]-q))<0) return 0;    }    return 1;}int main(){    RD(n,m);    int i;    FOR1(i,n) a[i].get();    FOR1(i,m) b[i].get();    FOR1(i,n) if(OK(a[i]))    {        puts("1");        return 0;    }    int j,k;    FOR1(i,n) FOR1(j,n) if(i!=j&&check(a[i],a[j]))    {        puts("2");        return 0;    }        FOR1(i,n) FOR1(j,n)     {        if(i!=j&&OK(a[i],a[j]))        {            g[i][j]=1;        }        else g[i][j]=INF;        f[i][j]=g[i][j];    }    int ans=INF;    FOR1(k,n)    {        FOR1(i,n) if(i!=k) FOR1(j,n) if(i!=j&&k!=j)        {            ans=min(ans,g[i][j]+f[j][k]+f[k][i]);        }        FOR1(i,n) FOR1(j,n)         {            g[i][j]=min(g[i][j],g[i][k]+g[k][j]);        }    }    if(ans==INF) puts("-1");    else PR(ans);}