HDU 2828 Lamp 二分图的最大匹配模型题

http://acm.hdu.edu.cn/showproblem.php?pid=2828

给定n个灯，m个开关，使得每栈灯亮，前提是控制这栈灯的开关的状态是其中一个。（题目应该都看得懂）

其实我想了挺久的，比赛的时候还想不出。但是直觉就告诉我是二分图匹配，虽然网上说什么精确覆盖。

不懂。

我的做法是：

m个开关，则有2 * m种状态，以1号顶点表示1号灯是开得，1 + m号顶点表示1号灯是关的。

那么，进行一次二分匹配，模板需要改一下，

1、如果第i号灯需要第j个开关是ON的状态，但是第j个开关的ON的状态已经被人选了，那么，就可以默认第i号灯是true的了。

2、如果你想选第j个开关是OFF的状态，那么就要询问下第j个开关的ON的状态是否被别人选了，如果是，就进行套路，就是找增广路。

3、记得修改match[i]，这里卡了我wa，不知道怎么说，看看代码吧。

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <assert.h>

#define IOS ios::sync_with_stdio(false)

using namespace std;

#define inf (0x3f3f3f3f)

typedef long long int LL;

#include <iostream>

#include <sstream>

#include <vector>

#include <set>

#include <map>

#include <queue>

#include <string>

#include <bitset>

int n, m;

const int maxn =  * ;

struct Edge {

    int u, v, tonext;

}e[maxn * ];

int num, first[maxn];

void add(int u, int v) {

    ++num;

    e[num].u = u, e[num].v = v, e[num].tonext = first[u];

    first[u] = num;

}

bool book[maxn * ];

int match[maxn * ];

bool dfs(int u) {

    for (int i = first[u]; i; i = e[i].tonext) {

        int v = e[i].v;

        if (book[v] == false) {

            book[v] = true;

            if (v > m) book[v - m] = true;

            else book[v + m] = true;

            if (match[v]) return true;

            if (v > m) {

                if (match[v - m] ==  || dfs(match[v - m])) {

                    match[v - m] = ;

                    match[v] = u;

                    return true;

                }

            } else {

                if (match[v + m] ==  || dfs(match[v + m])) {

                    match[v + m] = ; //dfs那里的要清空

                    match[v] = u;

                    return true;

                }

            }

        }

    }

    return false;

}

int hungary() {

    int ans = ;

    for (int i = ; i <= n; ++i) {

        memset(book, false, sizeof book);

        if (dfs(i)) ans++;

    }

    return ans;

}

void init() {

    memset(first, , sizeof first);

    memset(match, , sizeof match);

    num = ;

}

void work() {

    init();

    for (int i = ; i <= n; ++i) {

        int k;

        scanf("%d", &k);

        while (k--) {

            int id;

            char op[];

            scanf("%d%s", &id, op);

            if (op[] == 'N') {

                add(i, id);

            } else {

                add(i, id + m);

            }

        }

    }

    int res = hungary();

    if (res != n) {

        cout << "-1" << endl;

        return;

    }

//    for (int i = 1; i <= n; ++i) {

//        cout << match[i] << " ";

//    }

//    cout << endl;

    for (int i = ; i <= m - ; ++i) {

        if (match[i]) {

            printf("ON ");

        } else {

            printf("OFF ");

        }

    }

    if (match[m]) {

        printf("ON");

    } else printf("OFF");

    printf("\n");

}

int main() {

#ifdef local

    freopen("data.txt", "r", stdin);

//    freopen("data.txt", "w", stdout);

#endif

    while (scanf("%d%d", &n, &m) != EOF) work();

    return ;

}

巴特西

HDU 2828 Lamp 二分图的最大匹配模型题

最新文章

热门文章

巴特西

HDU 2828 Lamp 二分图的最大匹配 模型题

最新文章

热门文章

HDU 2828 Lamp 二分图的最大匹配模型题