【代码源】每日一题 农田划分

2022.05.12

题目链接：农田划分 - 题目 - Daimayuan Online Judge 

题目描述

约翰是一个农场主，他的农场有n块田，编号从 1到 n，这 n块田通过 m条双向道路相连(数据保证这n块田都是联通的)，我们假设第 i 块田会产生 2^i kg 的收益，现在约翰想把农田的工作全部交给自己的两个孩子，划分方式必须满足以下规则:

1.每一块田都需要恰好被分给一个孩子.

2.分给两个孩子的农田必须是联通的.就是说对于任意一个孩子在划分给自己的任意一块田，都可以不经过另外一个孩子的田，到达自己的任意一块田.

3.划分给两个孩子的收益必须尽可能的相等，如果无法相等，年长的孩子会得到大的那一份.

对于第 i 块田，如果你要把它分给年长的孩子，请输出A,否则输出B.

题目输入

第一行输入两个整数分别代表 n,m 接下来 m 行，每个两个整数 u,v，代表这两块农田通过一条双向道路直接相连，数据保证没有重边和自环

题目输出

输出一个字符串，代表答案

样例输入1

3 2
1 3
3 2

样例输出1

ABA

样例输入2

6 6
3 5
2 6
1 3
3 6
5 1
4 6

样例输出2

BABABA

数据范围

2≤n≤3e5,1≤m≤3e5

分析：

题目要求将n块田均分为两部分，并且每部分需要联通。

对每块田地的收益分析，对第 i 块田地收益为2^i，前（1~i-1)块的和最多也是2^i-1，也就是说即使你拿了 1~i-1 块也没有拿第i块一块的收益大，也就是编号越大，收益越大。所以对于n块地，要想分的均匀，第n块一定是给A的，在满足联通的情况下分给B的越多越好，而且编号越大越好，所以n-1一定分配给A。

所以，只需要将与n-1相连的田地分配给B其余全部分给A（并查集）。 

详见代码：

#include <bits/stdc++.h>
using namespace std;
int n, m;
int far[300009];
inline int find(int x) //查找
{
    return (far[x] == x) ? x : far[x] = find(far[x]);
}
inline void unionn(int x, int y) //合并
{
    x = find(x);
    y = find(y);
    if (x != y)
    {
        if (x < y) //为了使与n-1联通的编号的父亲为n-1，所以将编号小的合并到编号大的上
            swap(x, y);
        far[y] = far[x]; //将y的父亲变为x的父亲
    }
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        far[i] = i; //并查集初始化
    while (m--)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        if (x == n || y == n) // B的田地不能通过A中的田地来达到联通
                              // 题目保证了连通性，不与B联通则一定会和A联通
            continue;
        else
            unionn(x, y); //合并
    }
    for (int i = 1; i <= n; i++)
        if (find(i) == n - 1) //与B联通则分配给B
            cout << "B";
        else
            cout << "A";
}