这题大意是一堆积木，抽掉某一块后会使得上面的积木崩溃（当上面的积木仅仅与抽去的部分相邻），问抽去哪块积木会使得崩塌的总积木数最多
这题做法是先将积木处理成图的节点，然后如果假设底下的积木i与上面的积木j直接相邻面为k，则将i与j连接条权值为k的边，然后针对每一块积木枚举求崩溃的总块数，这里用类似拓扑排序算法的处理，将每个节点底面与其他面的接触面数作为该节点的“入度”
1
# include <iostream>
2using namespace std;
3# include <cstdio>
4# include <map>
5# include <cstring>
6# include <vector>
7# include <queue>
8char g[101][101];
9int id[101][101];
10int n,m,c;
11# define max(a,b) ((a)>(b)?(a):(b))
12struct
13
{
14
int r,c,len;
15
}block[10001];
16int main()
17{
18 while(true)
19
{
20 scanf("%d%d",&n,&m);
21 if(!n&&!m) break;
22 for(int i=0;i<n;i++)
23 scanf("%s",g[i]);
24 c=0;
25 for(int i=0;i<n;i++)
26 for(int j=0;j<m;)
27 {
28 if(g[i][j]=='0')
29 {
30 j++;
31 continue;
32
}
33 block[c].r=i;
34 block[c].c=j;
35 block[c].len=g[i][j]-'0';
36 for(int k=j;k<block[c].len+j;k++)
37 id[i][k]=c;
38 j+=block[c++].len;
39 }
40 int degree[10001];
41 int res=0;
42 queue<int> q;
43 int stddegree[10001];
44 for(int i=0;i<c;i++)
45 {
46 stddegree[i]=block[i].len;
47 if(block[i].r+1!=n)
48 for(int j=block[i].c;j<block[i].c+block[i].len;j++)
49 if(g[block[i].r+1][j]=='0')
50 stddegree[i]--;
51 }
52 for(int i=0;i<c;i++)
53 {
54
55 int ans=0;
56 memcpy(degree,stddegree,sizeof(degree));
57 q.push(i);
58 while(!q.empty())
59 {
60 int top=q.front();
61 q.pop();
62 ans+=block[top].len;
63 if(block[top].r!=0)
64 for(int j=block[top].c;j<block[top].c+block[top].len;j++)
65 if(g[block[top].r-1][j])
66 {
67 degree[id[block[top].r-1][j]]--;
68 if(!degree[id[block[top].r-1][j]])
69 q.push(id[block[top].r-1][j]);
70 }
71 }
72 res=max(res,ans);
73 }
74 printf("%d\n",res);
75
76
77 }
78 return 0;
79}
80
81
82