POJ 2531-Network Saboteur（N个点分成两部分）

一时失言乱红尘 2022-07-12 08:17 146阅读 0赞

Network Saboteur

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong>&nbsp;2000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong>&nbsp;65536K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong>&nbsp;12566</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong>&nbsp;6061</td> 
  </tr> 
 </tbody> 
</table>

Description

A university network is composed of N computers. System administrators gathered information on the traffic between nodes, and carefully divided the network into two subnetworks in order to minimize traffic between parts.  
A disgruntled computer science student Vasya, after being expelled from the university, decided to have his revenge. He hacked into the university network and decided to reassign computers to maximize the traffic between two subnetworks.  
Unfortunately, he found that calculating such worst subdivision is one of those problems he, being a student, failed to solve. So he asks you, a more successful CS student, to help him.  
The traffic data are given in the form of matrix C, where Cij is the amount of data sent between ith and jth nodes (Cij = Cji, Cii = 0). The goal is to divide the network nodes into the two disjointed subsets A and B so as to maximize the sum ∑Cij (i∈A,j∈B).

Input

The first line of input contains a number of nodes N (2 <= N <= 20). The following N lines, containing N space-separated integers each, represent the traffic matrix C (0 <= Cij <= 10000).  
Output file must contain a single integer -- the maximum traffic between the subnetworks.

Output

Output must contain a single integer -- the maximum traffic between the subnetworks.

Sample Input

3
    0 50 30
    50 0 40
    30 40 0

Sample Output

Source

[Northeastern Europe 2002][], Far-Eastern Subregion

## 题目意思： ##

有N台电脑，给出一个N\*N的邻接矩阵，表示i节点到j节点的流量是Cij，且Cij=Cji。将N个网络节点划分为两个不相交的子集A和B，计算最大的和ΣCij（i∈A，j∈B）。

## 解题思路： ##

暴力枚举+剪枝，借鉴了大神分组的方法。

剪枝：只需要枚举\[2^(n-1)\]-1次而不是n次。

n个不同物品分成两组的方法数是\[2^(n-1)\]-1，因为：

ΣC(i,n)=2^n，其中i∈\[0,n\]；

因为两组均不为空，且C(0,n)=C(n,n)=1，所以ΣC(i,n)=(2^n)-2，其中i∈\[1,n-1\]；

因为两组相互区别，所以方法数是ΣC(i,n)/2,，即\[2^(n-1)\]-1，其中i∈\[1,n-1\]。

#include<iostream>
    #include<cstdio>
    #include<iomanip>
    #include<cmath>
    #include<cstdlib>
    #include<cstring>
    #include<map>
    #include<algorithm>
    #include<vector>
    #include<queue>
    using namespace std;
    #define INF 0x3f3f3f3f
    #define MAXN 25
    int c[MAXN][MAXN];
    int vis[25];
    
    int main()
    {
    #ifdef ONLINE_JUDGE
    #else
        freopen("F:/cb/read.txt","r",stdin);
        //freopen("F:/cb/out.txt","w",stdout);
    #endif
        ios::sync_with_stdio(false);
        cin.tie(0);
        int n;
        while(cin>>n)
        {
            for(int i=0; i<n; i++)
                for(int j=0; j<n; j++)
                    cin>>c[i][j];;
            memset(vis,0,sizeof(vis));
            int ans=0;
            for(int i=0; i<(1<<(n-1)); i++)//枚举2^n-1次就可以将所有情况枚举出来
            {
                ++vis[0];
                for(int j=0; j<n; j++)//通过0,1的值将n个点分到两个部分
                {
                    if(vis[j]==2)
                    {
                        vis[j]=0;
                        ++vis[j+1];
                    }
                    else break;
                }
                int res=0;
                for(int j=0; j<n; j++)//求出总和
                    if(vis[j])//计算从所有的1的所有的0的和
                        for(int k=0; k<n; k++)
                            if(!vis[k]) res+=c[j][k];
                ans=max(ans,res);
            }
            cout<<ans<<endl;
        }
        return 0;
    }
    /*
    3
    0 50 30
    50 0 40
    30 40 0
    */

[Northeastern Europe 2002]: http://poj.org/searchproblem?field=source&key=Northeastern+Europe+2002