| Time Limit: 2000MS | Memory Limit: 65536K | |
| Total Submissions: 13748 | Accepted: 6700 |
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).
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 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
90
Source
Northeastern Europe 2002, Far-Eastern Subregion
翻译：
大学网络由N台电脑组成。系统管理员收集有关节点之间流量的信息，并仔细将网络分为两个子网，以最大限度地减少部件之间的流量。
一位心怀不满的计算机科学系学生Vasya在被大学开除后决定报复。他侵入了大学网络，并决定重新分配计算机以最大化两个子网络之间的流量。
不幸的是，他发现计算这种最坏的细分是他作为一个学生未能解决的那些问题之一。
所以他问你，一个更成功的CS学生，帮助他。交通数据以矩阵C的形式给出，其中Cij是第i个和第j个节点之间发送的数据量（Cij = Cji，Cii = 0）。目标是将网络节点分成两个不相关的子集A和B，以便使ΣCij（i∈A，j∈B）的和最大。
第一行输入包含许多节点N（2 <= N <= 20）。以下N行包含N个空格分隔的整数，分别代表流量矩阵C（0 <= Cij <= 10000）。
输出文件必须包含一个整数 - 子网之间的最大流量。
输出必须包含一个整数 - 子网之间的最大流量。
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int n,ans; int mp[25][25]; bool flag[25],A=1,B; void dfs(int pos,int now){ if(pos>n){ if(now>ans) ans=now; return ; } int sum=0; flag[pos]=A; for(int i=1;i<pos;i++) if(flag[i]==B) sum+=mp[pos][i]; dfs(pos+1,now+sum); sum=0;flag[pos]=B; for(int j=1;j<pos;j++) if(flag[j]==A) sum+=mp[pos][j]; dfs(pos+1,now+sum); } int main(){ while(scanf("%d",&n)!=EOF){ for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&mp[i][j]); ans=0; dfs(1,0); printf("%d ",ans); } }