题解 P4049 [JSOI2007]合金

· · 题解

1h 内没有做出来感觉还是挺亏的，要放真实省选就爆炸了（

还是不该在网络流和 dp 上面绕太久……

凭借初中数学的直觉，比较容易发现的是原题其实等价于一个二维平面问题，因为在三维之和确定的情况下，一二维确定第三维就确定了，所以直接扔掉第三维。

接着比较好发现的是复合两个点得到的点一定在两点的连线上，复合三个点（三点不共线）得到的点一定在构成的三角形内。

由此发现如果选定一个可以构成规则多边形的点集，那么这个多边形内部的点集肯定都可以被构造出来，所以问题转化成了找一个最小的材料点集构成的凸包囊括所有用户点。

然后我就开始了网络流和 dp 的奇妙冒险。

这里我们不妨先观察，可以先对凸包的边进行定向，使得所有点都在边的左边或者右边。

然后对于每条边判断是否能将所有点都割到左边/右边去，如果可以那么就将这条边权置为 1 否则置为无穷大，最后我们跑 Floyd 找最小环即可。

这里选左边右边都无妨，体现在答案上只是顺时针和逆时针的走法，不影响图形本身。

我该说我想不到的理由是我不会 Floyd 找最小环吗 

#include "bits/stdc++.h"
using namespace std;
const int Len = 5e2 + 5 , Inf = 1e9;
int n,m;
struct point
{
    double x,y;
    point(){x = 0.0 , y = 0.0;}
    point(double X,double Y){x = X , y = Y;}
    point operator - (const point &Ano) const
    {
        return point(x - Ano.x , y - Ano.y);
    }
    double operator ^ (const point &Ano) const
    {
        return x * Ano.y - y * Ano.x;
    }
}p[Len],t[Len];
int mp[Len][Len];
double fw;
int aside(point a,point b,point c)
{
    double mul = (b - a) ^ (c - a);
    if(mul > 0) return 1;
    if(mul < 0) return 0;
    double minx = min(a.x , b.x) , maxx = max(a.x , b.x) , miny = min(a.y , b.y) , maxy = max(a.y , b.y);
    return (minx <= c.x) && (c.x <= maxx) && (miny <= c.y) && (c.y <= maxy);
}
int main()
{
    scanf("%d %d",&m,&n);
    for(int i = 1 ; i <= m ; i ++) 
    {
        scanf("%lf %lf %lf",&p[i].x,&p[i].y,&fw);
        p[i].x *= 1000.0 , p[i].y *= 1000.0;
    }
    for(int i = 1 ; i <= n ; i ++) 
    {
        scanf("%lf %lf %lf",&t[i].x,&t[i].y,&fw);
        t[i].x *= 1000.0 , t[i].y *= 1000.0;
    }
    for(int i = 1 ; i <= m ; i ++)
        for(int j = 1 ; j <= m ; j ++) mp[i][j] = Inf;
    for(int i = 1 ; i <= m ; i ++)
        for(int j = 1 ; j <= m ; j ++)
        {
            bool flaw = 1;
            for(int k = 1 ; k <= n ; k ++) if(!aside(p[i] , p[j] , t[k])){flaw = 0;break;}
            if(flaw) mp[i][j] = 1;
            else mp[i][j] = Inf;
        }
    int Minn = Inf;
    for(int k = 1 ; k <= m ; k ++)
        for(int i = 1 ; i <= m ; i ++)
            for(int j = 1 ; j <= m ; j ++) mp[i][j] = min(mp[i][j] , mp[i][k] + mp[k][j]);
    for(int i = 1 ; i <= m ; i ++) Minn = min(Minn , mp[i][i]);
    if(Minn > m) puts("-1");
    else printf("%d\n",Minn);
    return 0;
}