CS106B Assignment4

Foreword

记录2022 winter的CS106B Assignment4

Debugging Pratice

可视化汉诺塔过程并调试一个broken的排列程序

其实就是一个地方把+=改成+就好了

Matchmaker

Perfect match

大概就是有若干个人，每个人都有几个心仪的匹配者，问是否有完美匹配使得每个人都匹配到一个自己的心仪者

递归去解决小问题，对当前问题挑一个人，枚举他和谁配对，然后摘出这两个人对子问题看是否有完美匹配

如果最后的子问题是空集，就说明找到了

bool hasPerfectMatching(const Map<string, Set<string>>& possibleLinks, Set<Pair>& matching) {
    if (possibleLinks.isEmpty()) {
        return true;
    }
    string person = possibleLinks.firstKey();
    for (auto another : possibleLinks[person]) {
        if (!possibleLinks.containsKey(another)) {
            continue;
        }
        bool ok = true;
        for (auto x : matching) {
            if (another == x.first() || another == x.second()) {
                ok = false;
                break;
            }
        }
        if (ok) {
            Pair newPair = {person, another};
            auto subPossibleLinks = possibleLinks;
            Set<Pair> subMatching;
            subMatching = matching + newPair;
            subPossibleLinks.remove(person);
            subPossibleLinks.remove(another);
            if (hasPerfectMatching(subPossibleLinks, subMatching)) {
                matching = subMatching;
                return true;
            }
        }
    }
    return false;
}

Maximum weight match

赋上边权，求最大权的匹配，不要求是完美匹配

用惯了STL好难习惯斯坦福这个库

void maximumWeightMatchingAux(const Map<string, Map<string, int>>& possibleLinks, const Set<string>& people, Set<Pair>& res, const Set<Pair>& matching, int& maxValue, int value) {
    if (people.size() <= 1) {
        if (value > maxValue) {
            maxValue = value;
            res = matching;
        }
        return;
    }
    string person = people.first();
    for (auto another : possibleLinks[person]) {
        if (people.contains(another)) {
            Pair partner(person, another);
            maximumWeightMatchingAux(possibleLinks, people - person - another, res, matching + partner, maxValue, value + possibleLinks[person][another]);
        }
    }
    maximumWeightMatchingAux(possibleLinks, people - person, res, matching, maxValue, value);
    return;
}

Set<Pair> maximumWeightMatching(const Map<string, Map<string, int>>& possibleLinks) {
    Set<Pair> res;
    Set<string> people;
    for (auto person : possibleLinks) {
        people.add(person);
    }
    int maxValue = 0;
    maximumWeightMatchingAux(possibleLinks, people, res, {}, maxValue, 0);
    return res;
}

Disater Planning

几座城市由道路连接起来，选几座城市放应急物资使得灾难来临时每个城市都是安全的

一个城市是安全的当且仅当这座城市自身或邻居有应急物资

限制选择城市的个数，问有没有这样的合法方案

bool canBeMadeDisasterReadyAux(const Map<string, Set<string>>& roadNetwork, int numCities, Set<string>& supplyLocations, Set<string>& unsafe) {
    if (numCities == 0) {
        return unsafe.isEmpty();
    }
    if (unsafe.isEmpty()) {
        return true;
    }
    auto city = unsafe.first();
    Set<string> tmp = unsafe - city - roadNetwork[city];
    if (canBeMadeDisasterReadyAux(roadNetwork, numCities - 1, supplyLocations, tmp)) {
        supplyLocations.add(city);
        return true;
    }
    for (auto neigh : roadNetwork[city]) {
        tmp = unsafe - neigh - roadNetwork[neigh];
        if (canBeMadeDisasterReadyAux(roadNetwork, numCities - 1, supplyLocations, tmp)) {
            supplyLocations.add(neigh);
            return true;
        }
    }
    return false;
}

bool canBeMadeDisasterReady(const Map<string, Set<string>>& roadNetwork,
                            int numCities,
                            Set<string>& supplyLocations) {
    if (numCities < 0) {
        error("numCities should be greater than zero.");
    }
    Set<string> unsafe;
    for (auto city : roadNetwork) {
        unsafe.add(city);
    }
    return canBeMadeDisasterReadyAux(roadNetwork, numCities, supplyLocations, unsafe);
}

效果