bank.cpp

银行家算法。银行客户系统常用的一个算法。。此代码效率不高

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std ;
struct Node
{
       vector<int>allocation;
       vector<int>need ;
       bool flag ; 
};

vector<int>available , path ,request;
Node node[103] ;
int n , m ; //n -- 进程数, m -- 资源数
bool leap ;

bool check(Node a)
{
     int i ; 
     for ( i = 0 ; i < m ; i ++)
         if(available[i] < a.need[i])
              return true ;
     return false ;
} 
void solve(int num)
{
     int i , j ; 
     if( num == n )
     {
         leap = true ;
         for ( i = 0 ; i < n ; i ++)
             printf("P%d ",path[i]) ;
         printf("\n");
         return ;
     }
     for ( i = 0 ; i < n ; i ++)
     {
         if(node[i].flag ) continue ;
         if(check(node[i])) continue ;
         node[i].flag = true ;
         for ( j = 0 ; j < m ; j ++)
             available[j] += node[i].allocation[j];
         path.push_back(i) ; 
         solve( num + 1 ) ; 
         node[i].flag = false ;
         for ( j = 0 ; j < m ; j ++)
             available[j] -= node[i].allocation[j]; 
         path.pop_back() ;
     }
     return ;
}
int main()
{
    while ( 2 == scanf("%d%d",&n,&m))
    {
          int i , j , temp ; 
          for ( i = 0 ; i < n ; i ++)
          {
              node[i].allocation.clear() ;
              node[i].need.clear() ;
              node[i].flag = false ; 
          }
          for ( i = 0 ; i < n ; i ++)
          {
              for ( j = 0 ; j < m ; j ++)
              {
                  scanf("%d",&temp) ; 
                  node[i].allocation.push_back(temp) ;
              }
              for ( j = 0 ; j < m ; j ++)
              {
                  scanf("%d",&temp) ; 
                  node[i].need.push_back(temp);
              }
          }
          available.clear() ; 
          path.clear() ; 
          leap = false ;
          for ( i = 0 ;  i < m ; i ++)
          {
              scanf("%d",&temp) ; 
              available.push_back(temp) ;
          }
          char str[10];
          scanf("%s",str) ;
          if( str[0] == 'Y')
          {
              int ID ; 
              scanf("%d",&ID) ; 
              request.clear() ;
              for ( i = 0 ; i < m ; i ++)
              {
                  scanf("%d",&temp ) ;
                  request.push_back(temp) ;
              }
              for ( i = 0 ; i < m ; i ++)
              {
                  if(request[i] > node[ID].need[i])
                                break ; 
              }
              if( i < m ) 
              {
                  printf("Error!\n");
                  continue ;
              }
              for ( i = 0 ; i < m ; i ++)
              {
                  if(request[i] > available[i])
                                break ; 
              }
              if( i < m ) 
              {
                  printf("Waiting!\n");
                  continue ;
              }
              for ( i = 0 ; i < m ; i ++ )
                  node[ID].allocation[i] += request[i] ;
              for ( i = 0 ; i < m ; i ++ )
                  node[ID].need[i] -= request[i] ;
              for ( i = 0 ; i < m ; i ++ )
                  available[i] -= request[i] ;
          }
          solve(0 ) ; 
          if(!leap && str[0] == 'N') printf("Not safety!\n");
          if(!leap && str[0] == 'Y') printf("Rrefuse!\n");
    }
    return 0 ; 
}

/*
5 3 
0 1 0 7 4 3 
2 0 0 1 2 2
3 0 2 6 0 0 
2 1 1 0 1 1
0 0 2 4 3 1
3 3 2 
5 3 
0 1 0 7 4 3 
3 0 2 0 2 0
3 0 2 6 0 0 
2 1 1 0 1 1
0 0 2 4 3 1
2 3 0 
*/