algorithm - 为什么我一直在为 UVa 10511 的此解决方案获取 WA

Question

我正在尝试解决这个问题，我想我已经找到了正确答案，但我不断收到法官的 WA(错误答案)回复。

http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1452

提炼出来的问题是，给定党和人之间的 1 - * 关系，人和俱乐部之间的 1 - * 关系。找到个人与俱乐部之间的 1 - 1 关系，使得对于与俱乐部相关的所有人，属于任何一方的人数少于俱乐部人数的一半。

例如，假设我们有

Person1 属于 Party1 和 Club1, Club2

Person2属于Party2和Club2、Club3

Person3 属于 Party3 和 Club3，Club1

有两种分配方式。

人 1 俱乐部 1

人 2 俱乐部 2

人 3 俱乐部 3

和

人 1 俱乐部 2

人 2 俱乐部 3

人 3 俱乐部 1

我的想法是将此问题建模为最大流问题，如下所示:

为简单起见，假设有两个派对、四个人和三个俱乐部。

0是主源

1、2是代表双方的节点

3,4,5,6是代表四个人的节点

7、8、9是代表三个俱乐部的节点。

10是主接收器

master source 连接到每一方，容量 = (3 + 1)/2 - 1 = 1。这表示 1 方最多只能有 1 人代表理事会(否则 2 将等于或超过一半)

对于每个派对人对，都有一个容量为 1 的链接。这表示每个人只有 1 个派对，并且使用了先前分配的号码中的一个座位。

对于每个人的俱乐部对，有一个容量为 1 的链接。这代表每个人只能代表一个俱乐部。

最后但并非最不重要的一点是，所有俱乐部都会以容量 1 下沉。

如果上图的最大流量等于俱乐部的数量 - 则存在分配。

我可以证明设计是正确的如下:

=>

如果存在最大流量，则每个俱乐部节点必须发送值为 1 的流量，这意味着每个俱乐部节点只有一个人代表它。该表示尊重政党参与的约束，因为它在一个政党中最多有那么多人代表政党节点流。

<=

如果存在表示，则按上述方式构建流，从而存在流。流量最大，因为最大可能流量受连接到汇点的边限制。

所以上面的论点或实现一定有问题。

事不宜迟，这是我的源代码:

#include "stdafx.h"

// http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1452

// #define LOG

#include "UVa10511.h"

#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <queue>

using namespace std;

int UVa10511_assign_person_number(map<string, int>& person_numbers, map<int, string>& person_namings, string person_name);
int UVa10511_assign_party_number(map<string, int>& party_numbers, map<int, string>& party_namings, string party_name);
int UVa10511_assign_club_number(map<string, int>& club_numbers, map<int, string>& club_namings, string club_name);
int UVa10511_Edmonds_Karps(vector<vector<int>>& capacities, vector<vector<int>>& adjacency_list, int src, int dst);

int UVa10511()
{
    string line;
    int number_of_test_cases;
    cin >> number_of_test_cases;
    getline(cin, line); // consume the blank link after the number of test cases    
    getline(cin, line); // consume the blank link before the first test case
    for (int test_case = 0; test_case < number_of_test_cases; test_case++)
    {
        map<string, int> person_numbers;
        map<int, string> person_namings;
        map<string, int> party_numbers;
        map<int, string> party_namings;
        map<string, int> club_numbers;
        map<int, string> club_namings;

        vector<pair<int, int>> party_members;
        vector<pair<int, int>> person_clubs;

        while(getline(cin, line) && line != "" && line != " ")
        {
            string person_name;
            string party_name;
            string club_name;
            stringstream sin(line);
            sin >> person_name >> party_name;

            int person_id = UVa10511_assign_person_number(person_numbers, person_namings, person_name);
            int party_id = UVa10511_assign_party_number(party_numbers, party_namings, party_name);
            party_members.push_back(pair<int, int>(party_id, person_id));
            while(sin >> club_name)
            {
                int club_id = UVa10511_assign_club_number(club_numbers, club_namings, club_name);
                person_clubs.push_back(pair<int, int>(person_id, club_id));
            }   
        }

        int number_of_parties = party_numbers.size();
        int number_of_persons = person_numbers.size();
        int number_of_clubs = club_numbers.size();

        int number_of_nodes =
            /* master source */ 1 +
            /* parties       */ number_of_parties +
            /* person        */ number_of_persons +
            /* clubs         */ number_of_clubs +
            /* master sink   */ 1;

        vector<vector<int>> capacities;
        vector<vector<int>> adjacency_list;

        capacities.resize(number_of_nodes);
        adjacency_list.resize(number_of_nodes);

        for (int src = 0; src < number_of_nodes; src++)
        {
            capacities[src].resize(number_of_nodes);
            for (int dst = 0; dst < number_of_nodes; dst++)
            {
                capacities[src][dst] = 0;
            }
        }

        int max_party_participants = (number_of_clubs - 1) / 2; // Floor intended, not equal or more than half

        for (int p = 0; p < number_of_parties; p++)
        {
            int party_node = p + 1;
            capacities[0][party_node] = max_party_participants;
            adjacency_list[0].push_back(party_node);
            adjacency_list[party_node].push_back(0);
        }

        int person_node_start = 1 + number_of_parties;

        for (vector<pair<int, int>>::iterator pmi = party_members.begin(); pmi != party_members.end(); pmi++)
        {
            int party_id = pmi->first;
            int person_id = pmi->second;

            int party_node = party_id + 1;
            int person_node = person_node_start + person_id;

            capacities[party_node][person_node] = 1;
            adjacency_list[party_node].push_back(person_node);
            adjacency_list[person_node].push_back(party_node);
        }

        int club_node_start = 1 + number_of_parties + number_of_persons;
        for (vector<pair<int, int>>::iterator pci = person_clubs.begin(); pci != person_clubs.end(); pci++)
        {
            int person_id = pci->first;
            int club_id = pci->second;

            int person_node = person_node_start + person_id;
            int club_node = club_node_start + club_id;

            capacities[person_node][club_node] = 1;
            adjacency_list[person_node].push_back(club_node);
            adjacency_list[club_node].push_back(person_node);
        }

        for (int c = 0; c < number_of_clubs; c++)
        {
            int club_node = club_node_start + c;
            capacities[club_node][number_of_nodes - 1] = 1;
            adjacency_list[club_node].push_back(number_of_nodes - 1);
            adjacency_list[number_of_nodes - 1].push_back(club_node);
        }

#ifdef LOG
        cout << "digraph {" << endl;
        for (int src = 0; src < number_of_nodes; src++)
        {
            for (vector<int>::iterator di = adjacency_list[src].begin(); di != adjacency_list[src].end(); di++)
            {
                int dst = *di;
                cout << src << "->" << dst << " [label=\"" << capacities[src][dst] << "\"];" << endl;
            }
        }
        cout << "}" << endl;
#endif

        int total_flow = UVa10511_Edmonds_Karps(capacities, adjacency_list, 0, number_of_nodes - 1);

        if (test_case > 0)
        {
            cout << endl;
        }

        if (total_flow == number_of_clubs)
        {

            for (vector<pair<int, int>>::iterator pci = person_clubs.begin(); pci != person_clubs.end(); pci++)
            {
                int person_id = pci->first;
                int club_id = pci->second;

                int person_node = person_node_start + person_id;
                int club_node = club_node_start + club_id;

                if (capacities[person_node][club_node] == 0)
                {
                    cout << person_namings[person_id] << " " << club_namings[club_id] << endl;
                }
            }
        }
        else
        {
            cout << "Impossible." << endl;
        }
    }

    return 0;
}

int UVa10511_assign_party_number(map<string, int>& party_numbers, map<int, string>& party_namings, string party_name)
{
    int party_number;
    map<string, int>::iterator probe = party_numbers.find(party_name);
    if (probe == party_numbers.end())
    {
        party_number = party_numbers.size();
        party_numbers.insert(pair<string, int>(party_name, party_number));
        party_namings.insert(pair<int, string>(party_number, party_name));
    }
    else
    {
        party_number = probe->second;
    }

    return party_number;
}

int UVa10511_assign_person_number(map<string, int>& person_numbers, map<int, string>& person_namings, string person_name)
{
    int person_number;
    map<string, int>::iterator probe = person_numbers.find(person_name);
    if (probe == person_numbers.end())
    {
        person_number = person_numbers.size();
        person_numbers.insert(pair<string, int>(person_name, person_number));
        person_namings.insert(pair<int, string>(person_number, person_name));
    }
    else
    {
        person_number = probe->second;
    }

    return person_number;
}

int UVa10511_assign_club_number(map<string, int>& club_numbers, map<int, string>& club_namings, string club_name)
{
    int club_number;
    map<string, int>::iterator probe = club_numbers.find(club_name);
    if (probe == club_numbers.end())
    {
        club_number = club_numbers.size();
        club_numbers.insert(pair<string, int>(club_name, club_number));
        club_namings.insert(pair<int, string>(club_number, club_name));
    }
    else
    {
        club_number = probe->second;
    }

    return club_number;
}

int UVa10511_Edmonds_Karps(vector<vector<int>>& capacities, vector<vector<int>>& adjacency_list, int src, int dst)
{
    int total_flow = 0;
    // Step 2: Edmonds Karp's
    vector<int> parents; // Allow back-tracking the path found from bfs
    int number_of_nodes = capacities.size();
    parents.resize(number_of_nodes); // avoid reallocation
    while (true)
    {
        // Step 2.1: Use BFS to find an augmenting flow
        queue<int> bfs_queue;
        for (int n = 0; n < number_of_nodes; n++)
        {
            parents[n] = -1; // indicating the node is not enqueued
        }

        parents[src] = -2; // indicating the node is enqueued but no actual parent because this is the root
        bfs_queue.push(src);
        while (bfs_queue.size() > 0)
        {
            int current = bfs_queue.front();
            bfs_queue.pop();
            for (vector<int>::iterator ni = adjacency_list[current].begin(); ni != adjacency_list[current].end(); ni++)
            {
                int neighbor = *ni;
                if (parents[neighbor] == -1 && capacities[current][neighbor] > 0)
                {
                    parents[neighbor] = current;
                    bfs_queue.push(neighbor);

                    if (neighbor == dst)
                    {
                        break;
                    }
                }
            }
            if (parents[dst] != -1)
            {
                break;
            }
        }

        if (parents[dst] == -1)
        {
            break;
        }
        else
        {
            // We have found an augmenting path, go through the path and find the max flow through this path
            int cur = dst;
            bool first = true;
            int max_flow_through_path = 0;
            while (true)
            {
                int src = parents[cur];
                if (src != -2)
                {
                    int dst = cur;
                    int available = capacities[src][dst];
#ifdef LOG
                    cout << src << "--" << available << "->" << dst << endl;
#endif
                    cur = parents[cur];
                    if (first)
                    {
                        max_flow_through_path = available;
                        first = false;
                    }
                    else
                    {
                        max_flow_through_path = min(max_flow_through_path, available);
                    }
                }
                else
                {
                    break;
                }
            }
#ifdef LOG
            cout << "flowing " << max_flow_through_path << endl << endl;
#endif
            total_flow += max_flow_through_path;
            // Flow the max flow through the augmenting path
            cur = dst;
            while (true)
            {
                int src = parents[cur];
                if (src != -2)
                {
                    capacities[src][cur] -= max_flow_through_path;
                    capacities[cur][src] += max_flow_through_path;
                    cur = parents[cur];
                }
                else
                {
                    break;
                }
            }
        }
    }

    return total_flow;
}

源码也贴在 https://github.com/cshung/Competition/blob/master/Competition/UVa10511.cpp

相同的 Edmonds Karps 程序用于通过一些其他 UVa 问题，所以我认为它应该没问题。

UVa820、UVa10480、UVa10779、UVa11506、UVa563 都被这个 Edmonds Karp 程序接受(这些代码也可以在 Git 存储库中找到)

我什至调试了 Edmond Karps 做出错误选择的案例，并为此测试案例使用了增广路径来修复它

1

Person1 Party1 Club1 Club2

Person2 Party2 Club3

Person3 Party3 Club1

由于我的 Edmond Karps 在邻接表顺序中使用 BFS，所以选择的路径是

Master Source -> Party1 -> Person1 -> Club1 -> Master Sink

Master Source -> Party2 -> Person2 -> Club3 -> Master Sink

Master Source -> Party3 -> Person3 -> Club1 -> Person1 -> Club2 -> Master Sink [这使用了反向边缘并证明通过反向边缘工作]

现在我真的卡住了，真的不知道出了什么问题，感谢任何帮助。

Answer 1

你这个问题的思路是正确的，是一个典型的使用最大流算法的问题。

我一遍又一遍地阅读你的代码，我找不到任何错误。然后我改变了你处理输入的方式，然后我得到了 UVA 的接受。

改一下代码

// you code 
cin >> number_of_test_cases;
getline(cin, line); // consume the blank link before the first test case
getline(cin, line); // consume the blank link before the first test case

//line 43
while(getline(cin, line) && line != "" && line != " ")

// change to
scanf("%d\n", &number_of_test_cases);

//line 43
// while(getline(cin, line) && line.length() > 0)

修改代码后，我得到了 uva 的接受。

希望得到您的回应。