问题简述
对于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所示。
图 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的顶点，那么继续去除，直到不存在为止。
图 2
剩下的顶点中，X集合顶点个数一定与Y集合顶点个数相等。X集合每个顶点的度都是2，所以Y集合中的所有顶点度也都是2。于是剩下的顶点构成了若干个互不连同的环，每个顶点属于且只属于一个环，我们只需在此图上求字典序最小的匹配即可。每个环的匹配只有两种方式，如果我们从环上X集合中序号最小的顶点贪心的选择与序号较小的点匹配，那么该环上的匹配就是字典序最小。样例如图3。
图 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: 贪心 */ #includestruct 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