本文主要是介绍spoj1421 - Goods(循环节)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
暑假个人赛第二场D - Goods
题意：给定一个乱序的排列，要求重排成1~n的顺序，且调换方式为：
每次只能两个数字对换，每轮可以对换任意多次，但每轮中每个数字只能对换一次，
问需要几轮才能达到最终要求。
思路：找出所有的循环节，
若循环节长度为1，则不需要交换
若循环节长度为2，很明显的一轮就可以搞定，
若循环节的长度>2的话，就需要2轮了，
每找
出一个循环节就进行一轮的交换，（把循环节第一个和最后一个交换，第二个和倒数第二个交换，。。。。）
至于为什么只需两次，可以在纸上模拟一下置换过程，按上述置换方法一次交换后，一个循环节变成了(n-1)/2个长度为2的循环节，
可以一次并行交换。
参照chierush大神解法： http://www.cnblogs.com/Chierush/p/3210631.html代码如下：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define M 5005
int n, a[M], f[M], t[M], vis[M], len, ans, dp[M][2];
int is_ok()
{for(int i = 0; i < n; i++)if(i!=a[i])return 0;return 1;
}
void dfs(int i)
{t[++len] = a[i];if(vis[a[i]]) return;vis[a[i]] = 1;dfs(a[i]);
}
void solve()
{ans = 0;memset(vis,0,sizeof(vis));for(int i = 1; i <= n; i++)if(vis[i]==0){len = 0;vis[i] = 1;dfs(i);if(len>=2){for(int l = 1, r = len; l < r; l++, r--){dp[ans][0] = t[l];dp[ans][1] = t[r];ans++;swap(a[f[t[l]]], a[f[t[r]]]);swap(f[t[l]], f[t[r]]);}}}
}
int main ()
{scanf("%d",&n);for(int i = 1; i <= n; i++){scanf("%d",&a[i]);f[a[i]] = i;}if(is_ok()) printf("0\n");else{solve();if(is_ok())printf("1\n");elseprintf("2\n");printf("%d",ans);for(int i = 0; i < ans; i++)printf(" %d-%d",dp[i][0], dp[i][1]);printf("\n");solve();if(ans){printf("%d",ans);for(int i = 0; i < ans; i++)printf(" %d-%d\n",dp[i][0], dp[i][1]);printf("\n");}}return 0;
}
这篇关于spoj1421 - Goods(循环节)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
