NOI 2009 變換序列

問題簡述

對於0,1,…,N-1的N個整數,給定一個距離序列D0,D1,…,DN-1,定義一個變換序列T0,T1,…,TN-1使得每個i,Ti的環上距離等於Di。一個合法的變換序列應是0,1,…,N-1的一個排列,任務是要求出字典序最小的那個變換序列。

問題建模

抽象成圖論模型,建立一個二分圖,X集合每個頂點代表0,1,…,N-1的N個整數,Y集合每個頂點爲對應的N個整數。X集合的第i個頂點向其環上距離爲Di的Y集合中的兩個頂點連一條邊。樣例建圖後如圖1所示。

image

圖 1

解法1 嘗試完美匹配

算法描述
顯然一個變換序列,就是二分圖的一個完美匹配,關鍵在於如何保證字典序最小。求字典序最小解得一般方法就是嘗試枚舉,並轉爲化判定性問題。 於是方法就是,以此確定X集合每個頂點的對應點,首先嚐試讓其對應序號較小的頂點,然後判斷剩下的圖是否存在一個完美匹配(用匈牙利算法求最大匹配,判斷最大匹配數是否等於X集合剩餘頂點數)。如果存在,那麼當前頂點對應點就是序號較小的頂點,否則就是另一個頂點。最初應先判斷是否存在完美匹配,如果不存在,那麼該情況無解。
算法證明
假設還存在一個比當前方法求得的解T字典序更小的解V,那麼對於0<=i<=N-1一定有Vi<=Ti,並且存在一個j使得Vj<Tj。因爲Vj<Tj,所以X集合頂點j一定是對應的序號較大的頂點Tj,而Vj則是序號較小的頂點。由於如果j對應了Vj,剩餘的頂點不存在完美匹配,所以V不是合法解,因而不存在一個比當前方法求得的解T字典序更小的解V,T是字典序最小的解。
複雜度分析
該圖的邊數是O(N)的,所以匈牙利算法的時間複雜度爲O(N2)。由於對於每個點都要進行一次匈牙利算法,所以該算法的時間複雜度爲O(N3)。在實際的測試數據中能拿到70分。
參考程序
/*
* Problem: NOI2009 DAY1 transform
* Author: Guo Jiabao
* Time: 2009.7.27 10:20
* State: Done
* Memo: 二分圖匹配 + 暴力判斷
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>

using namespace std;

const int MAXN=20003,MAXM=MAXN*2;

struct edge
{
    edge *next;
    int t;
}*V[MAXN],ES[MAXM];

FILE *fi,*fo;
int N,EC;
int mat[MAXN],S[MAXN][2],T[MAXN];
bool vis[MAXN],lock[MAXN];

inline void addedge(int a,int b)
{
    ES[++EC].next = V[a];
    V[a] = ES+EC;
    V[a]->t = b;
}

void init()
{
    int i,t1,t2,d;
    fi = fopen("transform.in","r");
    fo = fopen("transform.out","w");
    fscanf(fi,"%d",&N);
    EC = 0;
    for (i=1;i<=N;i++)
    {
        fscanf(fi,"%d",&d);
        t1 = i + d;
        if (t1>N) t1-=N;
        t2 = i - d;
        if (t2<1) t2+=N;
        if (t1 < t2)
            S[i][0] = t1,S[i][1] = t2;
        else
            S[i][0] = t2,S[i][1] = t1;
        addedge(i,S[i][1]+N);
        addedge(i,S[i][0]+N);
    }
}

bool aug(int i)
{
    for (edge *e=V[i];e;e=e->next)
    {
        int j = e->t;
        if (!vis[j] && !lock[j])
        {
            vis[j] = true;
            if (!mat[j] || aug(mat[j]))
            {
                mat[j] = i;
                return true;
            }
        }
    }
    return false;
}

bool hungary()
{
    memset(mat,0,sizeof(mat));
    for (int i=1;i<=N;i++)
    {
        if (lock[i]) continue;
        memset(vis,0,sizeof(vis));
        if (!aug(i))
            return false;
    }
    return true;
}

bool solve()
{
    int i,j;
    if (!hungary())
        return false;
    for (i=1;i<=N;i++)
    {
        lock[i] = true;
        for (j=0;j<=1;j++)
        {
            if (!lock[S[i][j]+N])
            {
                lock[S[i][j]+N] = true;
                if (hungary())
                {
                    T[i] = S[i][j];
                    break;
                }
                lock[S[i][j]+N] = false;
            }
        }
    }
    return true;
}

void print(bool win)
{
    if (win)
    {
        int i;
        for (i=1;i<N;i++)
            fprintf(fo,"%d ",T[i] - 1);
        fprintf(fo,"%d\n",T[i] - 1);
    }
    else
        fprintf(fo,"No Answer\n");
    fclose(fi);
    fclose(fo);
}

int main()
{
    init();
    print(solve());
    return 0;
}

解法2 調整匹配

算法描述
首先求一個任意完美匹配,然後在此基礎上,不斷尋找增廣迴路,以改進當前解,直到最優解。 具體方法爲,依次斷每個頂點的對應。如果當前頂點對應的點是序號較小頂點,可以直接取得,否則嘗試修正。修正的方法是強制將當前頂點對應到序號較小頂點,這必然導致X集合中另一個頂點失配,此時從該頂點開始嘗試找一條增廣路,如果存在則修正成功,否則修正失敗,撤回操作。
算法證明
證明類似與解法1,不同在於每次無重新判斷,只要修正保證合法,每時總是完美匹配。
複雜度分析
首先求一個完美匹配的時間複雜度爲O(N2),接下來要嘗試修正N次,每次修正時時間爲 O(N),所以總時間複雜度爲O(N2)。由於算法常數較小,在實際的測試數據中拿到了100分。
參考程序
/* 
 * Problem: NOI2009 transform
 * Author: Guo Jiabao
 * Time: 2009.9.17 15:10
 * State: Solved
 * Memo: 二分圖匹配 + 修正
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
const int MAXN=20001,MAXM=MAXN*4;

struct edge
{
    edge *next;
    int t;
}*V[MAXN],ES[MAXM];

int N,EC,Current;
int S[MAXN][2],mat[MAXN];
bool vis[MAXN];

inline void addedge(int a,int b)
{
    ES[++EC].next = V[a]; V[a] = ES + EC;
    V[a]->t = b;
}

void init()
{
    freopen("transform.in","r",stdin);
    freopen("transform.out","w",stdout);
    scanf("%d",&N);
    int i,d,t1,t2;
    for (i=1;i<=N;i++)
    {
        scanf("%d",&d);
        t1 = i + d;
        if (t1>N) t1-=N;
        t2 = i - d;
        if (t2<1) t2+=N;
        if (t1 < t2)
            S[i][0] = t1,S[i][1] = t2;
        else
            S[i][0] = t2,S[i][1] = t1;
        addedge(i,S[i][0]+=N);
        addedge(i,S[i][1]+=N);
    }
}

bool augment(int i)
{
    if (i <= Current)
        return false;
    for (edge *e=V[i];e;e=e->next)
    {
        int j = e->t;
        if (!vis[j])
        {
            vis[j] = true;
            if (!mat[j] || augment(mat[j]))
            {
                mat[j] = i;
                mat[i] = j;
                return true;
            }
        }
    }
    return false;
}

void hungary()
{
    Current = 0;
    int cnt = 0;
    for (int i=1;i<=N;i++)
    {
        memset(vis,0,sizeof(vis));
        if (augment(i))
            cnt++;
    }
    if (cnt < N)
    {
        printf("No Answer\n");
        exit(0);
    }
}

void fix()
{
    for (int i=1;i<=N;i++)
    {
        if (mat[i] != S[i][0])
        {
            Current = i;
            memset(vis,0,sizeof(vis));

            int t = mat[ S[i][0] ];

            mat[ S[i][1] ] = 0;
            mat[ S[i][0] ] = i;
            vis[ S[i][0] ] = true;

            if (augment(t))
            {
                mat[i] = S[i][0];
            }
            else
            {
                mat[ S[i][1] ] = i;
                mat[ S[i][0] ] = t;
            }
        }
    }
}

void solve()
{
    hungary();
    fix();
}

void print()
{
    int i;
    for (i=1;i<N;i++)
        printf("%d ",mat[i] - N - 1);
    printf("%d\n",mat[i] - N - 1);
}

int main()
{
    init();
    solve();
    print();
    return 0;
}

解法3 倒序匹配

算法描述
這個方法很神奇,只用求一次完美匹配,要從X集合最後一個頂點到第一個頂點的順序求每個頂點出發的增廣路,求增廣路的過程中應優先選擇序號較小點。
算法證明
實現簡單的方法往往證明並不容易,該算法運用了貪心的思想。首先我們可以發現,有一些可以直接確定的匹配,這些就是度爲1的頂點,必須與其唯一的對應點對應。樣例如圖2所示,(1,2),(4,3)一定存在於任意一個解中(如果有解的話)。這樣的話,我們就可以把已經確定的頂點去除,刪除後如果又發現了剩餘度爲1的頂點,那麼繼續去除,直到不存在爲止。 image 圖 2 剩下的頂點中,X集合頂點個數一定與Y集合頂點個數相等。X集合每個頂點的度都是2,所以Y集合中的所有頂點度也都是2。於是剩下的頂點構成了若干個互不連同的環,每個頂點屬於且只屬於一個環,我們只需在此圖上求字典序最小的匹配即可。每個環的匹配只有兩種方式,如果我們從環上X集合中序號最小的頂點貪心的選擇與序號較小的點匹配,那麼該環上的匹配就是字典序最小。樣例如圖3。 image 圖 3 由於事先不知道那些頂點在環上,哪些可以直接確定。從X集合每個頂點倒序查找增廣路,就可以保證最後的最優,也就是字典序儘量小。因爲如果一個頂點在環上,找到的一定是環上較優的匹配方式,而不在環上的點也可以被後來的增廣而修正。
複雜度分析
求一次完美匹配的時間複雜度爲O(N2),在實際的測試數據中拿到了100分。
參考程序
/* 
 * Problem: NOI2009 transform
 * Author: Guo Jiabao
 * Time: 2009.9.17 15:29
 * State: Solved
 * Memo: 二分圖匹配
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
const int MAXN=20001,MAXM=MAXN*4;

struct edge
{
    edge *next;
    int t;
}*V[MAXN],ES[MAXM];

int N,EC;
int S[MAXN][2],mat[MAXN];
bool vis[MAXN];

inline void addedge(int a,int b)
{
    ES[++EC].next = V[a]; V[a] = ES + EC;
    V[a]->t = b;
}

void init()
{
    freopen("transform.in","r",stdin);
    freopen("transform.out","w",stdout);
    scanf("%d",&N);
    int i,d,t1,t2;
    for (i=1;i<=N;i++)
    {
        scanf("%d",&d);
        t1 = i + d;
        if (t1>N) t1-=N;
        t2 = i - d;
        if (t2<1) t2+=N;
        if (t1 < t2)
            S[i][0] = t1,S[i][1] = t2;
        else
            S[i][0] = t2,S[i][1] = t1;
        addedge(i,S[i][1]+=N);
        addedge(i,S[i][0]+=N);
    }
}

bool augment(int i)
{
    for (edge *e=V[i];e;e=e->next)
    {
        int j = e->t;
        if (!vis[j])
        {
            vis[j] = true;
            if (!mat[j] || augment(mat[j]))
            {
                mat[j] = i;
                mat[i] = j;
                return true;
            }
        }
    }
    return false;
}

void solve()
{
    int cnt = 0;
    for (int i=N;i>=1;i--)
    {
        memset(vis,0,sizeof(vis));
        if (augment(i))
            cnt++;
    }
    if (cnt < N)
    {
        printf("No Answer\n");
        exit(0);
    }
}

void print()
{
    int i;
    for (i=1;i<N;i++)
        printf("%d ",mat[i] - N - 1);
    printf("%d\n",mat[i] - N - 1);
}

int main()
{
    init();
    solve();
    print();
    return 0;
}

解法4 貪心

算法描述
按照解法3證明中的描述,我們可以預處理所有已經確定的匹配,並在圖中刪去。對於剩下的每個環,只需從序號最小的點開始深度優先搜索,並進行匹配即可。

算法證明
證明同解法3。

複雜度分析
預處理的時間複雜度爲O(N),深度優先搜索的時間複雜度爲O(N),所以總時間複雜度爲O(N)。在實際的測試數據中拿到了100分。

參考程序

/* 
 * Problem: NOI2009 transform
 * Author: Guo Jiabao
 * Time: 2009.9.17 18:37
 * State: Solved
 * Memo: 貪心
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
const int MAXN=20001,MAXM=MAXN*4;

struct edge
{
    edge *next;
    int t;
}*V[MAXN],ES[MAXM];

int N,EC,Stack[MAXN];
int S[MAXN][2],deg[MAXN],mat[MAXN];
bool nuked[MAXN];

inline void addedge(int a,int b)
{
    ES[++EC].next = V[a]; V[a] = ES + EC;
    V[a]->t = b;
    ES[++EC].next = V[b]; V[b] = ES + EC;
    V[b]->t = a;
    ++deg[b];
    mat[b] = a;
}

void init()
{
    freopen("transform.in","r",stdin);
    freopen("transform.out","w",stdout);
    scanf("%d",&N);
    int i,d,t1,t2;
    for (i=1;i<=N;++i)
    {
        scanf("%d",&d);
        t1 = i + d;
        if (t1>N) t1-=N;
        t2 = i - d;
        if (t2<1) t2+=N;
        if (t1 < t2)
            S[i][0] = t1,S[i][1] = t2;
        else
            S[i][0] = t2,S[i][1] = t1;
        addedge(i,S[i][1]+=N);
        addedge(i,S[i][0]+=N);
        deg[i] = 2;
    }
}

inline void Match(int i,int j)
{
    mat[i] = j;
    mat[j] = i;
}

void dfsMatch(int i,bool s)
{
    nuked[i] = true;
    int j;
    for (edge *e=V[i];e;e=e->next)
    {
        j = e->t;
        if (!nuked[j])
        {
            dfsMatch(j,!s);
            if (s)
                Match(i,j);
            break;
        }
    }
}

void noAnswer()
{
    printf("No Answer\n");
    exit(0);
}

void cut()
{
    int Stop = 0,i,j;
    for (i=1;i<=N;++i)
    {
        if (deg[i+N] == 0)
            noAnswer();
        else if (deg[i+N] == 1)
            Stack[++Stop] = i+N;
    }
    while (Stop)
    {
        i = Stack[Stop--];
        nuked[i] = true;
        for (edge *e=V[i];e;e=e->next)
        {
            j = e->t;
            if (!nuked[j])
                break;
        }
        Match(i,j);
        i = j;
        nuked[i] = true;
        for (edge *e=V[i];e;e=e->next)
        {
            j = e->t;
            if (!nuked[j])
            {
                deg[j]--;
                if (deg[j] == 0)
                    noAnswer();
                else if (deg[j] == 1)
                    Stack[++Stop] = j;
            }
        }
    }
}

void solve()
{
    cut();
    for (int i=1;i<=N;i++)
    {
        if (!nuked[i])
        {
            dfsMatch(i,true);
        }
    }
}

void print()
{
    int i;
    for (i=1;i<N;i++)
        printf("%d ",mat[i] - N - 1);
    printf("%d\n",mat[i] - N - 1);
}

int main()
{
    init();
    solve();
    print();
    return 0;
}

相關日誌