POJ-2531 Network Saboteur 枚举||随机化

题意：给定一个完全图，现在要求将这个图划分成两个部分，求两个部分的点做笛卡尔积之后的点对的距离和最大值是多少。

解法一：由于给定的点最多只有20个，所以直接2^N*O(n)的时间复杂度枚举即可。

解法二：采用随机化算法，枚举某一个点，将这个点所属于的集合进行翻滚。

代码如下：

#include <cstdlib> #include <cstring> #include <cstdio> #include <iostream> using namespace std;int N, G[25][25];int cal(int x) {int A[25], B[25], ca = 0, cb = 0, ret = 0;for (int i = 0; i < N; ++i) {if (x & (1 << i)) {A[ca++] = i + 1;} else {B[cb++] = i + 1; }}for (int i = 0; i < ca; ++i) {for (int j = 0; j < cb; ++j) {ret += G[A[i]][B[j]];} }return ret; }int main() {int ret;while (scanf("%d", &N) == 1) {ret = 0;for (int i = 1; i <= N; ++i) {for (int j = 1; j <= N; ++j) {scanf("%d", &G[i][j]);}} // 对给定信息进行存储int mask = (1 << N) - 1;for (int i = 1; i < mask; ++i) {ret = max(ret, cal(i));}printf("%d\n", ret);}return 0; }

下面这个随机化代码G++过不了，不知道为什么。

#include <cstdlib> #include <cstdio> #include <cstring> #include <iostream> #include <ctime> #include <map> using namespace std; // 由于问题的规模相对较小 // 可以使用随机化算法来解决这个问题 int N, G[30][30];int randtime = 200000;int A[30];void MoveAToB(int x, int &t) {A[x] = 0;for (int i = 1; i <= N; ++i) {if (A[i]) t += G[x][i];else t -= G[x][i];} }void MoveBToA(int x, int &t) {A[x] = 1;for (int i = 1; i <= N; ++i) {if (!A[i]) t += G[x][i];else t -= G[x][i];} }int randpro() {int rd, ret = 0, t = 0;for (int i = 0; i < randtime; ++i) {rd = rand() % N + 1; // 得到一个点，这个点被if (A[rd]) { // 说明在A集合 MoveAToB(rd, t);} else { // 说明在B集合 MoveBToA(rd, t);}ret = max(ret, t);}return ret; }int main() {srand(time(NULL));while (scanf("%d", &N) == 1) {for (int i = 1; i <= N; ++i) {for (int j = 1; j <= N; ++j) {scanf("%d", &G[i][j]);}}for (int i = 1; i <= N; ++i) {A[i] = 1; // 先假设所有的元素都是属于第一个集合 }printf("%d\n", randpro());} return 0; }

 

 

转载于:https://www.cnblogs.com/Lyush/archive/2012/11/19/2777998.html

总结

以上是生活随笔为你收集整理的POJ-2531 Network Saboteur 枚举||随机化的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。