Beyond the Void
BYVoid
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分。
参考程序
```cpp /* * Problem: NOI2009 transform * Author: Guo Jiabao * Time: 2009.9.17 18:37 * State: Solved * Memo: 贪心 */ #include #include #include #include #include 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; }


上次修改时间 2017-05-26

相关日志