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

BZOJ 1027 合金（凸包-最小环）

2024-07-09 00:19:17   225人阅读

题目链接：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);}

 

 

 


联系
我们