UVa 1459 - Flowers Placement

#图论 #二分图完美匹配 #暴力
Published on 2015-12-24

题目地址

描述

一共有 n(n≤200)n(n\le200) 种花，现在给出 m(1≤m≤n)m(1\le m\le n) 行 nn 列的花的摆放方式，要求每行每列的任意的两盆花的种类不同。问如果新添加一行，所有的合理摆放方法中，字典序为 kk 的摆放方法是什么？如果存在至少 kk 中合理方案，输出方案，否则输出 −1-1。

样例输入

2
3 2 2
3 2 1
1 3 2
4 2 2
1 4 3 2
2 1 4 3

样例输出

Case # 1: -1
Case # 2: 4 3 2 1

附加输入

7
3 2 2
3 2 1
1 3 2

3 2 1
3 2 1
1 3 2

4 2 2
1 4 3 2
2 1 4 3

4 2 1
1 4 3 2
2 1 4 3

4 2 3
1 4 3 2
2 1 4 3

7 1 4
1 2 3 4 5 6 7

7 1 10
1 2 3 4 5 6 7

附加输出

Case # 1: -1
Case # 2: 2 1 3
Case # 3: 4 3 2 1
Case # 4: 3 2 1 4
Case # 5: -1
Case # 6: 2 1 4 5 6 7 3
Case # 7: 2 1 4 7 6 3 5

分析

由于每行每列的不能相同，对于最后一列的每个位置，它能放的花的种类是固定的（根据这一列每一行的摆放方法），我们一定可以通过搜索的方式求出字典序为 kk 的可行解。于是确定搜索为算法主体。
然而纯搜状态太多，有太多不可能的状态，于是我们必须优化。我们从前往后放置花，在 pos\mathrm{pos} 列放置花的时候，如果当前的放置导致 pos\mathrm{pos} 后面的位置与剩余的花无法形成完美匹配，就剪掉。
不过要注意每次求完美匹配要在上次的完美匹配之上进行，最开始要求一次完美匹配，如果没有直接输出 −1-1。

代码

//  Created by Sengxian on 12/24/15.
//  Copyright (c) 2015年 Sengxian. All rights reserved.
//  Uva 1549 暴力+完美匹配剪枝
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <vector>
#include <stack>
#include <numeric>
#include <queue>
using namespace std;
const int maxn = 200 + 3, maxk = 200 + 3;
int n, m, k;
vector<int> G[maxn];
bool vis[maxn][maxn], used[maxn];
int cnt, ans[maxn], match[maxn];
bool s[maxn], t[maxn];

bool Match(int u) {
    s[u] = true;
    for (int i = 0; i < G[u].size(); ++i) {
        int v = G[u][i];
        if(used[v] || t[v]) continue;
        t[v] = true;
        if(match[v] == -1 || Match(match[v])) {
            match[v] = u;
            return true;
        }
    }
    return false;
}

bool go() {
    fill(match, match + n, -1);
    for(int i = 0; i < n; ++i) {
        fill(s, s + n, false);
        fill(t, t + n, false);
        if(!Match(i)) return false;
    }
    return true;
}

int a[maxn];
//在原有匹配的基础上修改，避免时间的浪费！
inline bool judge(int pos, int flower) {
    if (match[flower] == pos) return true; //如果这朵花本来就在这个位子上，自然可以放置
    for (int i = 0; i < n; ++i) {
        s[i] = t[i] = false;
        a[i] = match[i];  //保留之前的信息
        if (match[i] == pos) match[i] = -1; //原来 pos 列放的花空了
    }

    int oripos = match[flower]; //原来这朵花的列为 oripos
    match[flower] = pos; //这朵花被放到 pos 列
    used[flower] = true; //固定这朵花的位置

    //如果空的列可以成功放花，则表明可行
    if (Match(oripos)) {
        return true;
    }else {
        //否则不可行，回溯到之前的完美匹配
        for (int i = 0; i < n; ++i) match[i] = a[i];
        used[flower] = false;
        return false;
    }
}

void dfs(int cur) {
    if (cnt == k) return;
    if (cur == n) {
        if (++cnt == k)
            for (int i = 0; i < n; ++i)
                printf("%d%c", ans[i] + 1, i + 1 == n ? '\n' : ' ');
        return;
    }
    for(int i = 0; i < G[cur].size(); ++i) {
        if(cnt == k) return;
        int v = G[cur][i];
        //对当前排列来一次检测，若防止此花放置后导致无法完美匹配，则剪掉
        if(!used[v] && judge(cur, v)) {
            used[v] = true;
            ans[cur] = v;
            dfs(cur + 1);
            used[v] = false;
        }
    }
}

inline int ReadInt() {
    int n = 0, ch = getchar();
    bool flag = false;
    while(ch < '0' || ch > '9') {
        if(ch == '-') flag = true;
        ch = getchar();
    }
    do {
        n = n * 10 + ch - '0';
        ch = getchar();
    }while(ch >= '0' && ch <= '9');
    return flag ? -n : n;
}

int main() {
    int caseNum = ReadInt();
    for (int t = 1; t <= caseNum; ++t) {
        printf("Case # %d: ", t);
        n = ReadInt(), m = ReadInt(), k = ReadInt();
        for (int i = 0; i < n; ++i) G[i].clear(), fill(vis[i], vis[i] + n, 0);
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j) vis[j][ReadInt() - 1] = true;
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                if (!vis[i][j]) G[i].push_back(j);
        fill(used, used + n, false);
        cnt = 0;
        if(go()) dfs(0);
        if(cnt < k) printf("-1\n");
    }
    return 0;
}
UVa 1327 - King's Quest