hdu 1198 Farm Irrigation

令人蛋疼的并查集……

我居然做了大量的枚举，居然过了，我越来越佩服自己了

这个题有些像一个叫做“水管工”的游戏。给你一个m*n的图，每个单位可以有11种选择，然后相邻两个图只有都和对方连接，才判断他们连接。然后找这里面有多少个连通图。

给大家一个一点也不高大上，但是一眼就能看懂的代码吧……

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 #include <algorithm>

 using namespace std;

 const int N = ;

 char mpc[N][N];                                         //第一次输入

 bool mp[N*N][N*N];                                      //整理单向连通

 bool mps[N*N][N*N];                                     //记录双向连通

 int fm[N*N];                                            //并查集父节点，不用多说了吧……

 int m, n;

 int sum;

 void change2(int k, int x, int y)                       //四个方向连通

 {

     switch(k)

     {

     case :

         if(x- >= ) mp[x*m+y][(x-)*m+y] = ; break;

     case :

         if(y- >= ) mp[x*m+y][x*m+y-] = ; break;

     case :

         if(x+ < n)mp[x*m+y][(x+)*m+y] = ; break;

     case :

         if(y+ < m) mp[x*m+y][x*m+y+] = ; break;

     }

 }

 void change(int x, int y)                               //11个图的连接方式

 {

     switch(mpc[x][y]-'A')

     {

     case :

         change2(, x, y);

         change2(, x, y);

         break;

     case :

         change2(, x, y);

         change2(, x, y);

         break;

     case :

         change2(, x, y);

         change2(, x, y);

         break;

     case :

         change2(, x, y);

         change2(, x, y);

         break;

     case :

         change2(, x, y);

         change2(, x, y);

         break;

     case :

         change2(, x, y);

         change2(, x, y);

         break;

     case :

         change2(, x, y);

         change2(, x, y);

         change2(, x, y);

         break;

     case :

         change2(, x, y);

         change2(, x, y);

         change2(, x, y);

         break;

     case :

         change2(, x, y);

         change2(, x, y);

         change2(, x, y);

         break;

     case :

         change2(, x, y);

         change2(, x, y);

         change2(, x, y);

         break;

     case :

         change2(, x, y);

         change2(, x, y);

         change2(, x, y);

         change2(, x, y);

         break;

     }

 }

 int fd(int x)                                               //寻找父节点

 {

     while(x != fm[x])

     {

         x = fm[x];

     }

     return x;

 }

 void link(int x, int fx)                                    //合并+压缩

 {

     int mx;

     while(x != fm[x])

     {

         mx = x;

         x = fm[x];

         fm[mx] = fx;

     }

     fm[x] = fx;

 }

 void jp(int x, int y)

 {

     int fx = fd(x);

     int fy = fd(y);

     if(fx != fy)

     {

         link(x, fx);

         link(y, fx);

         sum++;                                              //统计连接的点的个数

     }

 }

 int main()

 {

     //freopen("test.txt", "r", stdin);

     while(~scanf("%d%d", &n, &m) && n != - && m != -)

     {

         memset(mp, , sizeof(mp));

         memset(mps, , sizeof(mps));

         memset(mpc, , sizeof(mpc));

         for(int i = ; i < m*n; i++) fm[i] = i;

         for(int i = ; i < n; i++)

         {

             scanf("%s", mpc[i]);

             for(int j = ; j < m; j++)

             {

                 change(i, j);

             }

         }

         for(int i = ; i < n*m; i++)

         {

             for(int j = ; j < i ; j++)

             {

                 if(mp[i][j] && mp[j][i]) mps[i][j] = ;

             }

         }

         sum = ;

         for(int i = ; i < n*m; i++)

         {

             for(int j = ; j < i; j++)

             {

                 if(mps[i][j]) jp(i, j);

             }

         }

         //for(int i = 0; i < m*n; i++) if(fm[i] == i) sum++;

         printf("%d\n", n*m-sum);

     }

     return ;

 }

对了，这个题dfs也能做，只是我不想再写了……