uva 196 Spreadsheet 拓扑排序。坑爹的一题

本文主要是介绍uva 196 Spreadsheet 拓扑排序。坑爹的一题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

uva 196 Spreadsheet

这题字符串处理上还是有点麻烦的，不过也还是可以处理

然后就是拓扑排序，一开始是用一个个删除度数0的点的方法，在POJ上过了 POJ数据果断水。。。在UVA上无限超时。坑爹啊。后来换成用DFS过了。不容易

PS:这题数据上是说要1 ～ 999 * 1 ～ 1800000多少的数据。。非常大。可是实际上只要开1000*1000的数组就可以过掉了。。又是坑爹

代码

#include <stdio.h>
#include <string.h>struct SB
{int num;int x[50];int y[50];int rx[55];int ry[55];int z;int zz;int du;int judge;
} map[1005][1005];int t;
int n, m;
int i, j, k;
int ii, jj;
char sb[2005];int dfs(int x, int y)
{int i;if (map[x][y].z == 0)return map[x][y].num;for (i = 0; i < map[x][y].z; i++)  map[x][y].num += dfs(map[x][y].x[i], map[x][y].y[i]);  map[x][y].z = 0;  return map[x][y].num;  
}
int main()
{scanf("%d", &t);while (t --){memset(map, 0, sizeof(map));memset(sb, 0, sizeof(sb));scanf ("%d%d", &m, &n);for (i = 1; i <= n; i ++){getchar();for (j = 1; j <= m; j ++){scanf("%s", sb);int l = strlen(sb);if (sb[0] != '=')  {int num = 0;int f = 0; if (sb[0] == '-') f = 1;  for (k = f; k < l; k ++)  num = num * 10 + sb[k] - '0';  map[i][j].num = num;  if (f == 1) map[i][j].num = -map[i][j].num;    } else  {int column = 0; int row = 0; int pos = 1;  map[i][j].num = 0;  while (pos < l)  {while ((sb[pos] >= 'A') && (sb[pos] <= 'Z')){column = column * 26 + sb[pos]-'A'+1; ++pos;}  while ((pos < l) && (sb[pos] >= '0') && (sb[pos] <= '9')){row = row * 10 + sb[pos] - '0';++ pos;}map[i][j].x[map[i][j].z] = row;map[i][j].y[map[i][j].z] = column;map[i][j].du ++;map[row][column].rx[map[row][column].zz] = i;map[row][column].ry[map[row][column].zz] = j;map[row][column].zz ++;map[i][j].z ++;row = 0; column = 0; ++ pos;  }  }}}for(i = 1; i <= n; i++)  for(j = 1; j <= m; j++)  {if(map[i][j].z) dfs(i, j);}for (i = 1; i <= n; i ++){for (j = 1; j < m; j ++){printf("%d ", map[i][j].num);}printf("%d\n", map[i][m].num);}}return 0;
}

这篇关于uva 196 Spreadsheet 拓扑排序。坑爹的一题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！