poj 1636 Prison rearrangement

  1 #include <iostream>
  2 #include <cstring>
  3 #include <cstdio>
  4 using namespace std;
  5 const int SIZE = 205;
  6 int m;
  7 int r;
  8 //map[i][j]表示i和j是否会冲突
  9 int map[SIZE][SIZE];
 10 //A组里的人数
 11 int aSize;
 12 //b组里的人数
 13 int bSize;
 14 //dp[i][j] 表示用A组的i个人换B组的j个人是否可行
 15 bool dp[SIZE][SIZE];
 16 //visited[0][i] 表示用A组中的点i是否被访问过
 17 //visited[1][i] 表示用B组中的点i是否被访问过
 18 bool visited[2][SIZE];
 19 void Init()
 20 {
 21     memset( map, 0, sizeof(map) );
 22     memset( visited, 0, sizeof(visited) );
 23     memset( dp, 0, sizeof(dp) );
 24 }
 25 void Input()
 26 {
 27     cin >> m >> r;
 28     for( int i=0; i<r; i++ )
 29     {
 30         int a, b;
 31         cin >> a >> b;
 32         map[a][b] = 1;
 33     }
 34 }
 35 //side=0  表示当前正在搜索A组
 36 //side=1  表示当前正在搜索B组
 37 //id 表示当前正在搜索的编号
 38 void DFS( int side, int id )
 39 {
 40     visited[side][id] = true;
 41     //如果当前搜索的是A组
 42     if( side == 0 )
 43     {
 44         //记录A组中的元素个数
 45         aSize++;
 46         for( int i=1; i<=m; i++ )
 47         {
 48             //搜索的是B组中对应的点
 49             if( map[id][i] && !visited[1][i] )//看一组的 id ，是否有和二组的 i ，相连的不，并且二组的没有被标记；
 50             {
 51                 DFS( 1, i ); //搜寻一组中是否有与二组相连的数；
 52             }
 53         }
 54     }
 55     else
 56     {
 57         bSize++;
 58         for( int j=1; j<=m; j++ )
 59         {
 60             if( map[j][id] && !visited[0][j] )
 61             {
 62                 DFS( 0, j );
 63             }
 64         }
 65     }
 66 }
 67 //利用二维背包计算
 68 void Knapsack()
 69 {
 70     dp[0][0] = true;
 71     for( int x=m/2; x>=aSize-1; x-- )
 72     {
 73         for( int y=m/2; y>=bSize-1; y-- )
 74         {
 75             if( dp[x][y] || dp[x - aSize][y - bSize] )
 76             {
 77                // printf("%d %d\n",x,y);
 78                 dp[x][y] = true;
 79             }
 80         }
 81     }
 82 }
 83 void Output()
 84 {
 85     for( int i=m/2; i>=0; i-- )
 86     {
 87         if( dp[i][i] )                         // dp[i][i]; 表示各方都拿出来 i 个人，进行交换；
 88         {
 89             cout << i << endl;
 90             break;
 91         }
 92     }
 93 }
 94 int main()
 95 {
 96     int caseNum;
 97     cin >> caseNum;
 98     while( caseNum-- )
 99     {
100         Init();
101         Input();
102         for( int i=1; i<=m; i++ )
103         {
104             //跳过已经处理过的节点
105             if( visited[0][i] ) continue;
106             //计算A、B中的人数
107             aSize = 0;
108             bSize = 0;
109             DFS( 0, i );    //  搜索一次，就出现两组不相容的团体；
110             //利用二维背包计算
111             Knapsack();
112         }
113         for( int i=1; i<=m; i++ )
114         {
115             if( visited[1][i] ) continue;
116             aSize = 0;
117             bSize = 0;
118             DFS( 1, i );
119             Knapsack();
120         }
121         Output();
122     }
123     return 0;
124 }