摘要
Title: 1684. 大型植被恢复
Tag: 构造
Memory Limit: 64 MB
Time Limit: 1000 ms

1684. 大型植被恢复

题意

长时间的干旱使得 Farmer John 的 N 块草地上牧草匮乏。
随着雨季即将到来，现在应当是重新种植的时候了。
在 Farmer John 的储物棚里有四个桶，每个桶里装着一种不同的草种。
他想要在每块草地上播种其中一种草。
作为一名奶农，Farmer John 想要确保他的每头奶牛都能得到丰富的食谱。
他的 M 头奶牛每一头都有两块喜爱的草地，他想要确保这两块草地种植不同种类的草，从而每头奶牛都可以选择两种草。
已知每块草地最多被 4 头奶牛喜爱。
请帮助 Farmer John 选择每块草地所种的草的种类，使得所有奶牛的营养需求都得到满足。
思路

一开始写了两版，但应该都不是正解
- 1.依次枚举两个地的牛是否有交集，无交集的依次赋值草的种类， $O(n^2m^2)$
- 2.先枚举草的种类，再枚举田地，判断草的种类的牛是否和田地的牛有交集， $O(4nm)$
- 3.先枚举互斥关系，再枚举草的种类，给最小的田地放最小的草种类，用邻接表可以少个n， $O(n^2)$

代码

$O(n^2m^2)$ 1327ms

'''
Author: NEFU AB-IN
Date: 2022-02-10 15:55:47
FilePath: \ACM\Acwing\1684.py
LastEditTime: 2022-02-10 16:30:00
'''

from collections import Counter

N = 160
a = [Counter() for _ in range(N)]
res = [0 for _ in range(N)]

if __name__ == "__main__":
    n, m = map(int, input().split())
    for i in range(m):
        x, y = map(int, input().split())
        a[x - 1][i] = 1  #第x块地被第i头牛青睐
        a[y - 1][i] = 1
    # print(a)
    tot = 1
    for i in range(n):  #枚举地
        if res[i] == 0:  #未分配则分配
            res[i] = tot
            tot += 1
        else:  #分配了就过
            continue
        for ii in range(i + 1, n):  #枚举其他地
            if res[ii]:  #分配了就过
                continue
            flag = 0
            for j in a[i].keys():  #枚举每个地的牛，看两个地有无交集
                if flag:
                    break
                for jj in a[ii].keys():  #枚举每个地的牛
                    if a[ii][j]:
                        flag = 1
                        break
            if flag == 0:  #无交集的话，就让ii地和i地一个种类
                res[ii] = res[i]
                for jj in a[ii].keys():  #并更新此种类
                    a[i][jj] = 1
    for i in range(n):
        print(res[i], end="")

$O(4nm)$ 1041ms

'''
Author: NEFU AB-IN
Date: 2022-02-10 16:33:26
FilePath: \ACM\Acwing\1684.1.py
LastEditTime: 2022-02-10 16:53:23
'''
from collections import Counter

N = 160
a = [Counter() for _ in range(N)]
b = [Counter() for _ in range(5)]
res = [0 for _ in range(N)]

if __name__ == "__main__":
    n, m = map(int, input().split())
    for i in range(m):
        x, y = map(int, input().split())
        a[x - 1][i] = 1  #第x块地被第i头牛青睐
        a[y - 1][i] = 1
    for i in range(1, 5):  #枚举草的种类
        for j in range(n):  #枚举地
            if res[j]:
                continue
            flag = 0
            for k in a[j].keys():
                if b[i][k]:
                    flag = 1
                    break
            if flag == 0:
                res[j] = i
                for k in a[j].keys():
                    b[i][k] = 1
    for i in range(n):
        print(res[i], end="")

$O(n^2)$ 1100ms

'''
Author: NEFU AB-IN
Date: 2022-02-10 17:15:09
FilePath: \ACM\Acwing\1684.2.py
LastEditTime: 2022-02-11 09:23:11
'''
from collections import Counter

N = 160
a = [Counter() for _ in range(N)]  #互斥关系
res = [0 for _ in range(N)]  #表示草地i的草地种类

if __name__ == "__main__":
    n, m = map(int, input().split())
    for i in range(m):
        x, y = map(int, input().split())
        a[x - 1][y - 1] = 1  #读入互斥关系
        a[y - 1][x - 1] = 1
    for i in range(n):  #枚举每个草地
        b = [0 for _ in range(5)]  #表示草地种类是否被用过
        for j in range(n):
            if a[i][j] == 1:  #如果j和i互斥，那么res[j]这个草地种类不能选
                b[res[j]] = 1
        for j in range(1, 5):  #给i放上最小的草地种类即可
            if b[j] == 0:
                res[i] = j
                break
    for i in range(n):
        print(res[i], end="")

1684. 大型植被恢复

题意

思路

代码