「二分图模板」距离序列

发布于 2018-11-27  314 次阅读


题目描述

已知序列 $S={0,1,\cdots ,n-1}$,序列里有 $n$ 个数,从 $0$ 到 $n-1$。定义两个数 $x,y$ 的距离 $D(x,y) = min{|x-y|,N-|x-y|}$.
定义序列 S 的一个排列 T ,那么这两个序列的距离序列 $Q(S,T) = {D(S_0,T_0),D(S_1,T_1),\cdots,D(S_{n-1},T_{n-1}}$
现在知道距离序列,求出可能的 $T$ 中字典序最小的那个。
其中 $n \leq 10^4$。

题解

我们首先考虑建出一张二分图 $G$,边 $x,y$ 存在的意义是 $T$ 的第 $x$ 个元素可以放置 $y$.
那么我们建完这张二分图后,如果最大匹配数为 $n$,那么就存在解。
我们考虑如何输出字典序最小的解。
具体来说记录每个点匹配到了哪个点,每次优先遍历编号大的点,这样最后得到的序列就是字典序最小的了。
时间复杂度 $O(n^2)$

代码

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define Re register
#define LL long long
#define U unsigned
#define FOR(i,a,b) for(Re int i = a;i <= b;++i)
#define ROF(i,a,b) for(Re int i = a;i >= b;--i)
#define CLR(i,a) memset(i,a,sizeof(i))
#define BR printf("--------------------\n")
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 10000+5;

struct Node{
    struct Edge *firstEdge;
    Node *pre,*suf;bool vis;
    int num;
}node[MAXN];

struct Edge{
    Node *s,*t;
    Edge *next;
}pool[MAXN<<1],*frog = pool;

Edge *New(Node *s,Node *t){
    Edge *ret = ++frog;
    *ret = (Edge){s,t,s->firstEdge};
    return ret;
}

inline void add(int u,int v){
    node[u].firstEdge = New(&node[u],&node[v]);
}

int N,d[MAXN];

bool dfs(Node *v){
    //DEBUG(v->num);
    for(Edge *e = v->firstEdge;e;e = e->next){
        //DEBUG(e->t->num);
        if(e->t->vis) continue;
        e->t->vis = true;
        if(!e->t->pre || dfs(e->t->pre)){
            e->t->pre = v;
            v->suf = e->t;
            return true;
        }
    }
    return false;
}

inline int solve(){
    int cnt = 0;
    ROF(i,N-1,0){
        FOR(j,0,N) node[j].vis = false;
        cnt += dfs(&node[i]);
    }
    return cnt;
}

int main(){
    scanf("%d",&N);
    FOR(i,0,N-1) scanf("%d",d+i);
    FOR(i,0,N-1){
        ROF(j,N-1,0){
            if(std::min(std::abs(i-j),N-std::abs(i-j)) == d[i]){
                add(i,j);
                //printf("%d %d\n",i,j);
            }
        }
    }
    FOR(i,0,N) node[i].num = i;
    if(solve() == N){
        FOR(i,0,N-1) printf("%d%c",node[i].suf->num,(i == N-1) ? '\n' : ' ');
    }
    else{
        puts("No Answer");
    }
    return 0;
}

一个OIer。