当前位置: 代码迷 >> 综合 >> poj2513Network Saboteur(dfs+简单减枝)
  详细解决方案

poj2513Network Saboteur(dfs+简单减枝)

热度:76   发布时间:2024-01-14 21:51:15.0
Network Saboteur
Time Limit: 2000MS   Memory Limit: 65536K
Total Submissions: 11199   Accepted: 5411

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

90
#include<stdio.h>
int map[25][25];
int vis[25];
int n;
int ans;
void dfs(int id,int data)
{vis[id]=1;//将id从0的集合里放到1的集合里面int sum=data;for(int i=1;i<=n;i++){if(!vis[i])sum+=map[i][id];//如果两者不是同一个集合的就相加elsesum-=map[i][id];//如果两者在同一个集合就消除以前不在同一个集合时相加的边}if(ans<sum)//更新最大值ans=sum;for(int i=id+1;i<=n;i++){if(sum>data)//简单的减枝,如果id的值放在这个集合里面已经使 这些权值的和减少,如果在从0里面拿边添加岂不是更小,所以sum值必须//比data大,依次为减枝条件{dfs(i,sum);vis[i]=0;//回溯}}}
int main()
{int i,j;while(~scanf("%d",&n)){for(i=1;i<=n;i++){for(j=1;j<=n;j++)scanf("%d",&map[i][j]);}ans=-1;dfs(1,0);printf("%d\n",ans);}
return 0;
}