NOI 2009 变换序列

This post is written in Chinese. Please consider using Google Translate

问题简述

对于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;
}

Related posts