F. Not Splitting（思维转换 + 最短路）

题目链接

题解：
https://blog.csdn.net/qq_42106422/article/details/122572577?spm=1001.2101.3001.6661.1&utm_medium=distribute.pc_relevant_t0.none-task-blog-2%7Edefault%7ECTRLIST%7ERate-1.pc_relevant_default&depth_1-utm_source=distribute.pc_relevant_t0.none-task-blog-2%7Edefault%7ECTRLIST%7ERate-1.pc_relevant_default&utm_relevant_index=1

太强了！！！！！

分析一下：
题目说了切割线是中心对称图形，所以我们把切割线分成两部分看，
则切割线就转换成从一个边界沿边走到图的中心点，然后在180度翻转一下切割线；

然后考虑题目中说的最小破坏数，显然要让总破坏数最小，也就是两部分切割数的和最小；
我们线考虑一部分的情况(从一个边界走到中心点)，最小代价问题，我们考虑往最短路的方向去想！！！

考虑这样建图：
原图中线的格子看成点，然后边看成边，如果两个格子相关，则这两个点的边权是1，否则是0；
那么我们问题就转换成从一个边界走到中心的最小价值，这就可以用dijk来跑；

但是这样就有很多边界，我们定义(0 0)为超级源点（因为从0 0可以用0的代价走到任意边界）；
所以从超级源点跑dijk就行

下面考虑对称的那边要怎么处理？
由于是中心对称的，所以我们走一条边时，必然会走其中心对称的那条边；
所以我们可以直接把其中心对称的边的代价直接加到当前边中。

这样的话我们跑的最短路(从0 0到中心点)就等价于原问题了！！！

此外这个题的建图方式 和 写法挺特别的！

其实也可以把二维的点转换成一维的点，然后转换成常规的dijk，不过有点复杂了

int n,k;
int dis[maxn][maxn];
int h[maxn][maxn];  //竖边的权值
int v[maxn][maxn];  //横边的权值

void dijk()
{
    memset(dis,inf,sizeof dis);
    dis[0][0] = 0;

    priority_queue<PIII,vector<PIII>,greater<PIII>> q;  //第一个是距离，第二个是点
    q.push({0,{0,0}});

    while(q.size())
    {
        auto p = q.top();
        q.pop();

        int w = p.first;
        int x = p.second.first;
        int y = p.second.second;

        //往上走
        if( x > 0 && w + h[ x - 1 ][ y ] < dis[ x - 1 ][ y ] )
        {
            dis[ x - 1 ][ y ] = w + h[ x - 1 ][ y ] ;
            q.push( {dis[x-1][y],{x-1,y}} ) ;
        }

        // 向下走
        if( x < k && w + h[ x ][ y ] < dis[ x + 1 ][ y ] )
        {
            dis[ x + 1 ][ y ] = w + h[ x ][ y ] ;
            q.push( { dis[x+1][y], {x+1 , y }} ) ;
        }

        // 向左走
        if( y > 0 && w + v[ x ][ y - 1 ] < dis[ x ][ y - 1 ] )
        {
            dis[ x ][ y - 1 ] = w + v[ x ][ y - 1 ] ;
            q.push( {dis[ x ][ y - 1 ],{x , y - 1 }} ) ;
        }

        // 向右走
        if( y < k && w + v[ x ][ y ] < dis[ x ][ y + 1 ] )
        {
            dis[ x ][ y + 1 ] = w + v[ x ][ y ] ;
            q.push( {dis[ x ][ y + 1 ],{ x , y + 1 }} ) ;
        }
    }

}

void solve()
{
    memset(h,0,sizeof h);
    memset(v,0,sizeof v);

    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        int x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;

        x1--, y1--, x2--, y2--; //退格成点,起点是(0,0)

        if(x1 == x2)    //竖边
        {
            if(y1 > y2) swap(y1,y2);

            h[x1][y2] ++;
            h[k-x1-1][k-y2] ++; // 旋转180°后的权重也加进去
        }
        else    //横边
        {
            if(x1 > x2) swap(x1,x2);

            v[x2][y1] ++;
            v[k-x2][k-y2-1] ++;
        }
    }

    dijk();

    cout<<n-dis[k/2][k/2]<<endl;
}

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        solve();    
    }

    return 0;
}