Beyond the Void
BYVoid
NOI 2009 變換序列
本文正體字版由OpenCC轉換

問題簡述

對於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

相關日誌