poj 2531 Network Saboteur

 1 import java.util.*;
 2 import java.math.*;
 3 public class Main {
 4     public static int ans=0;
 5     public static void main(String []args)
 6     {
 7         Scanner cin=new Scanner(System.in);
 8         int n;
 9         while(cin.hasNext())
10         {
11             n=cin.nextInt();
12             ans=0;
13             int a[][]=new int [100][100];
14             boolean []vis=new boolean[1000];
15             for(int i=1; i<=n; i++)
16             {
17                 for(int j=1; j<=n; j++)
18                 {
19                     a[i][j]=cin.nextInt();
20                 }
21             }
22             dfs(1,0,vis,a,n);
23             System.out.println(ans);
24         }
25     }
26     public static void dfs(int num,int m1,boolean vis[],int a[][],int n)
27     {
28         vis[num]=true;
29         int tm=m1;
30         for(int i=1; i<=n; i++)
31         {
32             if(vis[i]==false)
33             {
34                 tm+=a[i][num];
35             }
36             else
37                 tm-=a[i][num];
38         }
39         if(tm>ans)
40         {
41             ans=tm;
42         }
43         for(int i=num+1; i<=n; i++)
44         {
45             if(tm>m1)
46             {
47                 dfs(i,tm,vis,a,n);
48                 vis[i]=false;
49             }
50         }
51     }
52 }