首页 > ACM题库 > HDU-杭电 > HDU 3225-Flowers Placement-分治-[解题报告]HOJ
2014
03-07

HDU 3225-Flowers Placement-分治-[解题报告]HOJ

Flowers Placement

问题描述 :

Bytetown has a long tradition in organizing an international flower exhibition. Professor Feuerbach, a true flower lover, visited the exhibition this year. He was pleased by the most beautiful flowers and other plants around the world roses, orchids, magnolias, cactuses. All flowers were nicely placed.

The flower placement that was the most appealing to him was composed of many kinds of flowers placed in a rectangular grid, such that each row of the grid contained each kind of flowers exactly once and each column of the grid contained each kind of flowers at most once.

Professor Feuerbach is a good mathematician and soon he realized that the number of columns of the grid has to be the same as the number of different kinds of flowers in the placement. The different kinds of flowers are represented by numbers 1, 2…, N, where N is the number of different kinds of flowers. Soon he encountered a new problem. He would like to add one row of flowers to the placement without violating the rules stated above. (Note that he may not modify the existing rows and therefore he may not use any new kinds of flowers in the new rows.) It’s quite easy, but he wants to know the K-th lexicographically valid placement.

输入:

The input data set describes about 100 flower placements. In the first line the number of placements is given.

Each flower placement description begins with three positive integers N (1≤N≤200), M (0≤M≤N), K (1≤K≤200) representing the number of columns and rows of the grid. The following M lines contain N integers each representing the kinds of flowers in one row of the placement.

输出:

The input data set describes about 100 flower placements. In the first line the number of placements is given.

Each flower placement description begins with three positive integers N (1≤N≤200), M (0≤M≤N), K (1≤K≤200) representing the number of columns and rows of the grid. The following M lines contain N integers each representing the kinds of flowers in one row of the placement.

样例输入:

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

很明显是要找一个第k字典序的完备二分匹配方案。

但是二分匹配却不能保证字典序。

然后很容易想到搜索,第K次满足条件是,就是答案。不过,这种做法显然会超时。所以想到剪枝。

搜索到第 a 个位置时,若第a+1——n能够构成完备匹配,则搜索,不能,则剪枝。

这里需要维护一个完备匹配,所以一开始就进行一次匹配。因为搜索每次只需要更改一个匹配,所以在进行匈牙利算法找增广路的时候,只需要为一个结点寻找增广路。

#include <iostream>
#include <cstdio>
#include <algorithm>
#define maxn 300005
#define lson num<<1,s,mid
#define rson num<<1|1,mid+1,e
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
#define N 205
bool vis[N];
vector<int> g[N];
int maps[N];  //始终保存完备匹配的方案。
int ans[205];
int top,tot;
int n,m,k;
int use[205];
int save[205];
int find(int k,int st)  //找 从st+1——n是否能构成完备匹配
{
    if(k<=st) return 0;
    for(int i=0;i<g[k].size();i++)
    {
        int boy=g[k][i];
        if(!vis[boy])
        {
            vis[boy]=1;
            if(maps[boy]==0||find(maps[boy],st))
            {
                maps[boy]=k;
                return 1;
            }
        }
    }
    return 0;
}
bool isok(int now,int flo)   //假设now位置放flo花
{
    if(maps[flo]==now) return true;
    int j;
    for(int i=1;i<=n;i++)
    {
        save[i]=maps[i];
        vis[i]=0;
        if(maps[i]==now) j=i;   //找到上一次完备匹配now位置放的花
    }
    int t=maps[flo];
                    //断开匹配
    maps[flo]=now;    //修改匹配
    maps[j]=0;
    if(find(t,now)) return true;    //从now+1——n之间再次为t找一个匹配
    else                            //没找到,则回溯
    {

        for(int i=1;i<=n;i++)
            maps[i]=save[i];
    }
    return false;
}
bool dfs(int now)
{
    if(now==n+1)
    {
        if(++tot==k) return true;
        return false;
    }
    for(int i=0;i<g[now].size();i++)
    {
        int flo=g[now][i];
        if(!use[flo]&&isok(now,flo))
        {
            use[flo]=1;
            ans[now]=flo;
            if(dfs(now+1)) return true;;
            use[flo]=0;
        }
    }
    return false;
}
int a[205][205];
int main()
{
    int cas;
    scanf("%d",&cas);
    int x;
    int ca=1;
    while(cas--)
    {
        for(int i=0;i<=n;i++) g[i].clear();
        memset(vis,0,sizeof(vis));
        memset(a,0,sizeof(a));

        memset(maps,0,sizeof(maps));
        scanf("%d%d%d",&n,&m,&k);
        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=n;j++)
            {
                scanf("%d",&x);
                a[j][x]=1;
            }
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(!a[i][j]) g[i].push_back(j);
            }
        }
        int Ans=0;
        for(int i=1;i<=n;i++)
        {
            memset(vis,0,sizeof(vis));
            Ans+=find(i,-1);
        }
        if(Ans!=n)
        {
            printf("Case #%d: -1\n",ca++);
            continue;
        }
        tot=0;
        memset(use,0,sizeof(use));
        if(dfs(1))
        {
            printf("Case #%d:",ca++);
            for(int i=1;i<=n;i++)
            {
                printf(" %d",ans[i]);
            }
        }
        else printf("Case #%d: -1",ca++);
        puts("");
    }
    return 0;
}

参考:http://blog.csdn.net/t1019256391/article/details/12848997