首页 > 专题系列 > Java解POJ > POJ 2531 Network Saboteur [解题报告] Java
2013
11-11

POJ 2531 Network Saboteur [解题报告] Java

Network Saboteur

问题描述 :

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).

输入:

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 must contain a single integer — the maximum traffic between the subnetworks.

样例输入:

3
0 50 30
50 0 40
30 40 0

样例输出:

90

解题代码:

/* @author: */
import java.util.Scanner;
public class Main{

 int c[][]=new int[22][22];
  int result=0;
  int n;
 boolean sign[]=new boolean[22];
 int v[]=new int[22];

 int find(int k,int a,int r){
     int temp=0;
     if(a+r<=result) return result;
     if(k==n+1){
          if(a>result) result=a;
          return result;         
     }      
     sign[k]=false;
     for(int i=1;i< k;i++) if(sign[i]) temp+=c[k][i]; find(k+1,a+temp,r-v[k]);
     sign[k]=true; temp=0;
     for(int i=1;i< k;i++) if(!sign[i]) temp+=c[i][k]; find(k+1,a+temp,r-v[k]);
     return result;
}

 int init(){
     Scanner sc=new Scanner(System.in);  
     int sum=0;
      n=sc.nextInt();
     for(int i=1;i<=n;i++){
         for(int j=1;j<=n;j++){
              c[i][j]=sc.nextInt();
              v[i]+=c[i][j];
         }
         sum+=v[i];
     }
    return sum;
 }

public static void main(String args[]){
   Main m=new Main();
     int sum=m.init();
    
     System.out.printf("%d\n", m.find(1,0,sum));
   }
}

  1. int half(int *array,int len,int key)
    {
    int l=0,r=len;
    while(l<r)
    {
    int m=(l+r)>>1;
    if(key>array )l=m+1;
    else if(key<array )r=m;
    else return m;
    }
    return -1;
    }
    这种就能避免一些Bug
    l,m,r
    左边是l,m;右边就是m+1,r;