首页 > 代码库 > poj 2531 Network Saboteur

poj 2531 Network Saboteur

http://poj.org/problem?id=2531

 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             else37                 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 }
View Code