题解 P6663 【[POI 2019] Układ scalony】

Computer1828 · 2020-08-04 13:27:19 · 题解

这翻译什么鬼&一血&严重拉低AC率

题目翻译：

有 n\cdot m 个点排成 n 行 m 列，坐标 (i,j) 表示的是第 i 行第 j 列的点。如果两个点 A(x_1,y_1) B(x_2,y_2) 的距离 \left\vert x_2-x_1 \right\vert + \left\vert y_2-y_1\right\vert = 1 ，则 A 和 B 之间有边权为 1 的边相连。给定整数 k ，构造一个这个图的生成树，使生成树的直径恰好为 k 。

首先考虑合法的 k 的范围是多少。

不难发现，当 n 为奇数时， k\in [n+m-2,nm-1] ；当 n 为偶数时， k\in [n+m-1,nm-1] 。这里分类讨论特判一下即可。

然后考虑怎么构造一个直径长度为 k 的生成树。可以分类讨论一下。

以下的图中每个格子代表一个点，左上角的格子的坐标是 (1,1) ，右下角的格子的坐标是 (n,m) ，相邻的格子之间有一条边权为 1 的边，红色粗线表示的是生成树的边。

当 n 为奇数时，可以先构造出 k = n+m-2 的情况：

然后构造出 k = nm-1 的情况：

思考一下是如何从左边构造出右边的（以下是 n = 5,m = 4,k = 9 的情况）：

也就是说，先构造出一条主干 A ，然后以主干的端点为起点，继续构造（假设后来构造的叫主干 B ），直到主干 A 的长度加上主干 B 的长度 = k 为止。对于其它不在主干 A 或主干 B 上的点，沿竖直方向连接到主干 A 上。

当 n 为偶数时，仿照上面的做法就行了（以下是 n = 4,m = 4,k = 10 的情况）:

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,k;
bool flag;
int f[1005][1005];
inline void add(int x1,int y1,int x2,int y2){
    if(flag) swap(x1,y1),swap(x2,y2);
    printf("%d %d %d %d\n",x1,y1,x2,y2);
}
inline void dosth1(){
    if(k<n+m-2 || k>=n*m){
        printf("NIE\n");
        return ;
    } 
    printf("TAK\n");
    k -= n+m-2;
    for(int i = 1;i<=n/2;++i) add(i,1,i+1,1);
    for(int i = 1;i<m;++i) add(n/2+1,i,n/2+1,i+1);
    for(int i = 1;i<=n/2;++i) add(i+n/2+1,m,i+n/2,m);
    for(int i = 1;i<=n/2;++i) for(int j = 2;j<=m;++j) f[i][j] = 1;
    for(int i = 1;i<=n/2;++i) for(int j = 1;j<m;++j) f[i+n/2+1][j] = -1;
    for(int i = 1;i<=n/2 && k;++i){
        if(i%2 == 1){
            for(int j = 2;j<=m && k;++j){
                if(j == 2){
                    if(i == 1) add(i,j,i,j-1);
                    else add(i,j,i-1,j);
                }else add(i,j,i,j-1);
                f[i][j] = 0,k--;
            }
        }else{
            for(int j = m;j>=2 && k;--j){
                if(j == m) add(i,j,i-1,j);
                else add(i,j,i,j+1);
                f[i][j] = 0,k--;
            }
        }
    }
    for(int i = n;i>n/2+1 && k;--i){
        if(i%2 == 1){
            for(int j = m-1;j>=1 && k;--j){
                if(j == m-1){
                    if(i == n) add(i,j,i,j+1);
                    else add(i,j,i+1,j);
                }else add(i,j,i,j+1);
                f[i][j] = 0,k--;
            }
        }else{
            for(int j = 1;j<m && k;++j){
                if(j == 1) add(i,j,i+1,j);
                else add(i,j,i,j-1);
                f[i][j] = 0,k--;
            }
        }
    }
    for(int i = 1;i<=n;++i) for(int j = 1;j<=m;++j) if(f[i][j]) add(i,j,i+f[i][j],j);
}

inline void dosth2(){
    if(n == 2) swap(n,m),flag = true;
    if(k<n+m-1 || k>=n*m){
        printf("NIE\n");
        return ;
    } 
    printf("TAK\n");
    k -= n+m-2;
    for(int i = 1;i<n/2;++i) add(i,1,i+1,1);
    for(int i = 1;i<m;++i) add(n/2,i,n/2,i+1);
    for(int i = 1;i<=n/2;++i) add(i+n/2-1,m,i+n/2,m);
    for(int i = 1;i<n/2;++i) for(int j = 2;j<=m;++j) f[i][j] = 1;
    for(int i = 1;i<=n/2;++i) for(int j = 1;j<m;++j) f[i+n/2][j] = -1;
    for(int i = 1;i<n/2 && k;++i){
        if(i%2 == 1){
            for(int j = 2;j<=m && k;++j){
                if(j == 2){
                    if(i == 1) add(i,j,i,j-1);
                    else add(i,j,i-1,j);
                }else add(i,j,i,j-1);
                f[i][j] = 0,k--;
            }
        }else{
            for(int j = m;j>=2 && k;--j){
                if(j == m) add(i,j,i-1,j);
                else add(i,j,i,j+1);
                f[i][j] = 0,k--;
            }
        }
    }
    for(int i = n;i>n/2 && k;--i){
        if(i%2 == 1){
            for(int j = 1;j<m && k;++j){
                if(j == 1) add(i,j,i+1,j);
                else add(i,j,i,j-1);
                f[i][j] = 0,k--;
            } 
        }else{
            for(int j = m-1;j>=1 && k;--j){
                if(j == m-1){
                    if(i == n) add(i,j,i,j+1);
                    else add(i,j,i+1,j);
                }else add(i,j,i,j+1);
                f[i][j] = 0,k--;
            }
        }
    }
    for(int i = 1;i<=n;++i) for(int j = 1;j<=m;++j) if(f[i][j]) add(i,j,i+f[i][j],j);
}
int main(){
    scanf("%d%d%d",&n,&m,&k);
    if(m%2 == 1) swap(n,m),flag = true;
    if(n%2 == 1) dosth1();
    else dosth2();
    return 0;
}

其实代码可以写得更短，并不需要冗杂的分类讨论，但是不分类讨论的写法的细节过于复杂，不便在此赘述。