题目链接
题目大意:
将一个图的节点分为两部分,求两部分的通信距离最大.
解题思路:
竟然做了好几个小时,提交到POJ上超时,下面给出代码
首先我们将所有的点标记为0(即所有点放在一个集合里)，然后取出一个site标记为1(即将该点放在另一个集合里)，这是对于和site在一个集合里的点，我们减去他们两个之间的权值，对于不在一个集合里的点，我们加上他们之间的权值。最后的结果为最大值
#include <iostream> using namespace std; const int MAXSIZE = 25; int sum; int maxsum = 0; int n; int visit[MAXSIZE]; int C[MAXSIZE][MAXSIZE]; //void dfs1(int step) //{ // int temp = 0; // for(int i = 0; i < n; i++) // { // if(visit[i] == 1) // { // for(int j = 0; j < n; j++) // if(visit[j] == 0) // { // temp += C[i][j]; // } // } // } // // if(temp > maxsum) // { // maxsum = temp; // } // // // for(int i = step; i < n; i++) // { // { // visit[i] = 1; // dfs1(step+1); // visit[i] = 0; // } // } //} void dfs(int site, int sum) { int i = 0; visit[site] = 1; // int temp = sum; for(i = 0; i < n; i++) { if(visit[i] == 1) { temp -= C[site][i]; }else{ temp += C[site][i]; } } maxsum = max(maxsum, temp); for(i = site + 1; i < n; i++) { //if(temp > sum){ dfs(i, temp); visit[i] = 0; //} } } int main() { freopen("input.txt", "r", stdin); while(cin >> n) { //sum = 0; maxsum = 0; memset(visit, 0, sizeof(visit)); for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { cin >> C[i][j]; } } dfs(0, 0); cout << maxsum << endl; } return 0; }
