转载

算法训练——GCJ-2008-R1A-B-Milkshakes

注意到每个customer最多只能有一种奶昔是”malted”的，这点是解决这题的关键。可以推出以下结论:

如果所有用户至少有两种喜欢的奶昔，那么必然有一种是”unmalted”，那只要保证所有奶昔种类都是”malted”就解决了。
如果有部分用户只喜欢一种奶昔，如果该奶昔是”unmalted”的，那么可以不用管它。
如果有用户喜欢一种奶昔，且”malted”，那么需要处理

算法描述:

针对分析，我们处理第三点，逻辑流程如下:

为了满足那部分用户，相应的奶昔我们只能做成”malted”
遍历所有customer:
1. 如果他们没有对于已经”malted”奶昔的偏好，跳过
2. 如果他们的偏好中也喜欢某一种”malted”奶昔，那么这个用户的偏好已经得到满足，可以从customer列表中剔除
3. 如果他们偏好中不喜欢该”malted”奶昔，把相应的奶昔从那些customer的偏好列表中删除，尝试用其它的奶昔去满足他们的需求
4. 处理的过程中如果发现某一个用户的偏好已经为空了，表示他的需求无法满足，直接返回”IMPOSSIBLE”
逻辑流程走到这里，表示必须做成”malted”的奶昔已经处理完毕，后续的逻辑可以不用考虑这种奶昔的存在，重新回到 1 循环。

主循环体退出的条件：客户列表为空或者已经不存在只偏好某一种”malted”奶昔的客户。

备注:因为每次循环都会减少总体奶昔的数量，所以上次还存在多种偏好的customer到了下次循环的时候偏好就有可能只剩一种了，这个是动态变化的。

代码：

写得稀碎的python:

with open("B-large-practice.in") as f:
    C = int(f.readline())
    for i in range(C):
        N = int(f.readline())
        M = int(f.readline())
        l = []
        for j in range(M):
            tmp = {}
            line = f.readline().strip().split()
            for k in range(int(line[0])):
                tmp[int(line[2 * k + 1])] = int(line[2 * k + 2])
            l.append(tmp)
        ans = {}
        # solution logic insert below
        possible = True
        while len(l) and possible:
            new_malted = None
            for c in l:
                if len(c) > 1:
                    continue
                if c[c.keys()[0]] == 1:
                    ans[c.keys()[0]] = 1
                    new_malted = c.keys()[0]
                    break
                elif c.keys()[0] in ans:
                    possible = False
                    break
            if new_malted is None:
                break

            del_list = []
            for c in l:
                if new_malted in c:
                    if c[new_malted]:
                        del_list.append(c)
                        continue
                    else:
                        del c[new_malted]
                        if len(c) == 0:
                            possible = False
                            break
            for c in del_list:
                l.remove(c)

        # output result
        res = "Case #{0}:".format(i + 1)
        if not possible:
            res += " IMPOSSIBLE"
        else:
            for i in range(N):
                if i + 1 in ans:
                    res += " 1"
                else:
                    res += " 0"
        print res