Instantaneous Transference
| Time Limit: 5000MS | Memory Limit: 65536K |
| Total Submissions: 3722 | Accepted: 788 |
Description
It was long ago when we played the game Red Alert. There is a magic function for the game objects which is called instantaneous transfer. When an object uses this magic function, it will be transferred to the specified point immediately, regardless of how far it is.
Now there is a mining area, and you are driving an ore-miner truck. Your mission is to take the maximum ores in the field.
The ore area is a rectangle region which is composed by n × m small squares, some of the squares have numbers of ores, while some do not. The ores can't be regenerated after taken.
The starting position of the ore-miner truck is the northwest corner of the field. It must move to the eastern or southern adjacent square, while it can not move to the northern or western adjacent square. And some squares have magic power that can instantaneously transfer the truck to a certain square specified. However, as the captain of the ore-miner truck, you can decide whether to use this magic power or to stay still. One magic power square will never lose its magic power; you can use the magic power whenever you get there.
Input
The first line of the input is an integer T which indicates the number of test cases.
For each of the test case, the first will be two integers N, M (2 ≤ N, M ≤ 40).
The next N lines will describe the map of the mine field. Each of the N lines will be a string that contains M characters. Each character will be an integer X (0 ≤ X ≤ 9) or a '*' or a '#'. The integer X indicates that square has X units of ores, which your truck could get them all. The '*' indicates this square has a magic power which can transfer truck within an instant. The '#' indicates this square is full of rock and the truck can't move on this square. You can assume that the starting position of the truck will never be a '#' square.
As the map indicates, there are K '*' on the map. Then there follows K lines after the map. The next K lines describe the specified target coordinates for the squares with '*', in the order from north to south then west to east. (the original point is the northwest corner, the coordinate is formatted as north-south, west-east, all from 0 to N - 1,M - 1).
Output
For each test case output the maximum units of ores you can take.
Sample Input
1
2 2
11
1*
0 0
Sample Output
3 Source
South Central China 2008 hosted by NUDT
这道题类似于矩阵取数，但是仔细考虑，因为只能朝右下走，因此不会有环。但是这一道题虽然是走右下，但是可以传送到上面，因此会有环。
处理方法是Tarjan强连通缩点，变成有向无环图再做，可以动规，我是求最长路。
做题之前没有统筹，有一半是离散化了的，有一半没有。。。（其实就是所有的二维数组都是没有离散的）
像这种矩阵里的离散还是很方便的，就把二维坐标映射成一维的点就行了。
具体处理强连通缩点，新的点的权值就是强连通分量里所有点权值累加。重新建图，枚举每一条边，判断两个端点所在的强连通分量是否是同一个，并且是否已经连过边，不是且没有则连一条边，然后就可以找最长路了。
1、对于这种多组数据的题，一定要注意初始化必须完整，不要漏了某一个初始化。
2、这道题的坑爹处，就是传送到#处。另外缩点的时候，只从不是#的地方开始搜索。
3、求最长路不要用Dijkstra，被坑了一天，对比一下：
代码有点长，355行，但是还是比较工整的，比起以前来。其中的Dijkstra和DFS都是不用的。
#include <cstdio>
#include <queue>
long n=0;long m=0;
long map[50][50];
struct node
{
long x;
long y;
};
node transto[50][50];
node transfrom[1800];
long DFN[1800];
long LOW[1800];
long TIME = 0;
long size[1800];
long Stack[1800];
bool InStack[1800];
long Belong[1800];
long top = 0;
long Bcnt = 0;
long maxlength = 0;
long destination = 0;
bool connected[1800][1800];
long K = 0;
long dist[1800];
bool vis[1800];
const long MOD = 3600;
long que[MOD];
#define DFN(a,b) (DFN[(a-1)*m+b])
#define LOW(a,b) (LOW[(a-1)*m+b])
#define vis(a,b) (vis[(a-1)*m+b])
#define POS(a,b) ((a-1)*m+b)
#define overrange(a,b) (map[a][b]==-2||a<1||a>n||b<1||b>m)
#define MIN(a,b) (a<b?a:b)
#define MAX(a,b) (a>b?a:b)
#define GETX(a) ((a-1)/m+1)
#define GETY(a) ((a-1)%m+1)
using std::pair;
using std::make_pair;
using std::priority_queue;
priority_queue<pair<long,long> > heap;
struct edge
{
long ind;
edge* nxt;
};
edge* head[1800];
void Init()
{
for (long i=1;i<n+1;i++)
for (long j=1;j<m+1;j++)
{
transto[i][j].x = transto[i][j].y = 0;
DFN(i,j) = LOW(i,j) = 0;
Belong[POS(i,j)] = 0;
InStack[POS(i,j)] = false;
}
for (long i=1;i<Bcnt+1;i++)
{
size[i] = 0;
head[i] = 0;
vis[i] = false;
for (long j=1;j<Bcnt+1;j++)
{
connected[i][j] = false;
}
}
for (long i=1;i<K+1;i++)
{
transfrom[i].x = transfrom[i].y = 0;
}
maxlength = 0;
destination = 0;
Bcnt = 0;top = 0;
TIME = 0;K = 0;
scanf("%ld%ld",&n,&m);
for (long i=1;i<n+1;i++)
{
scanf("\n");
for (long j=1;j<m+1;j++)
{
char tmp;
scanf("%c",&tmp);
if (tmp == '#')
map[i][j] = -2;
else if (tmp == '*')
{
map[i][j] = -1;
K++;
transfrom[K].x = i;
transfrom[K].y = j;
}
else map[i][j] = tmp-'0';
}
}
for (long i=1;i<K+1;i++)
{
long x;long y;
scanf("%ld%ld",&x,&y);
x++;y++;
long xf = transfrom[i].x;
long yf = transfrom[i].y;
transto[xf][yf].x = x;
transto[xf][yf].y = y;
}
}
void insert(long a,long b)
{
edge* ne = new edge;
ne->ind = b;
ne->nxt = head[a];
head[a] = ne;
}
void tarjan(long x,long y)
{
DFN(x,y) = LOW(x,y) = ++TIME;
Stack[++top] = POS(x,y);
InStack[POS(x,y)] = true;
if (map[x][y] == -1)
{
long nx = transto[x][y].x;
long ny = transto[x][y].y;
if (!overrange(nx,ny))
{
if (!DFN(nx,ny))
{
tarjan(nx,ny);
LOW(x,y) = MIN(LOW(x,y),LOW(nx,ny));
}
else if (InStack[POS(nx,ny)])
{
LOW(x,y) = MIN(LOW(x,y),DFN(nx,ny));
}
}
}
if (map[x][y] > -2)
{
long nx = x+1;
long ny = y;
if (!overrange(nx,ny))
{
if (!DFN(nx,ny))
{
tarjan(nx,ny);
LOW(x,y) = MIN(LOW(x,y),LOW(nx,ny));
}
else if (InStack[POS(nx,ny)])
{
LOW(x,y) = MIN(LOW(x,y),DFN(nx,ny));
}
}
nx = x;
ny = y+1;
if (!overrange(nx,ny))
{
if (!DFN(nx,ny))
{
tarjan(nx,ny);
LOW(x,y) = MIN(LOW(x,y),LOW(nx,ny));
}
else if (InStack[POS(nx,ny)])
{
LOW(x,y) = MIN(LOW(x,y),DFN(nx,ny));
}
}
}
if (DFN(x,y) == LOW(x,y))
{
++Bcnt;
long v;
do
{
v = Stack[top--];
if (map[GETX(v)][GETY(v)]>-1)
size[Bcnt] += map[GETX(v)][GETY(v)];
InStack[v] = false;
Belong[v] = Bcnt;
}while (POS(x,y) != v);
}
}
void dfs(long u,long dis)
{
if (dis > maxlength)
{
maxlength = dis;
destination = u;
}
for (edge* nxt=head[u];nxt;nxt=nxt->nxt)
{
dfs(nxt->ind,dis+size[nxt->ind]);
}
}
void dijkstra()
{
for (long i=0;i<Bcnt+1;i++)
dist[i] = -0x7f7f7f7f;
long Start = Belong[POS(1,1)];
dist[Start] = size[Start];
heap.push(make_pair(0,Start));
while (!heap.empty())
{
while (!heap.empty())
heap.pop();
if (heap.empty()) break;
long u = heap.top().second;
heap.pop();
for (edge* nxt=head[u];nxt;nxt=nxt->nxt)
{
long v = nxt->ind;
if (dist[v]<dist[u]+size[v])
{
dist[v]=dist[u]+size[v];
if (!vis[v])
{
heap.push(make_pair(dist[v],v));
}
}
}
}
}
void SPFA()
{
for (long i=1;i<Bcnt+1;i++)
dist[i] = -0x7f7f7f7f;
dist[Belong[POS(1,1)]] = 0;
long l = 0;
long r = 0;
que[++r] = Belong[POS(1,1)];
while (l!=r)
{
l = (l+1)%MOD;
long u = que[l];
vis[u] = false;
for (edge* nxt=head[u];nxt;nxt=nxt->nxt)
{
long v= nxt->ind;
if (dist[v]<dist[u]+size[v])
{
dist[v] = dist[u]+size[v];
if (!vis[v])
{
r = (r+1)%MOD;
que[r] = v;
}
}
}
}
}
void rebuild()
{
for (long i=1;i<n+1;i++)
{
for (long j=1;j<m+1;j++)
{
long nx = i+1;
long ny = j;
long B1 = Belong[POS(i,j)];
long B2 = Belong[POS(nx,ny)];
#ifdef Debug
if (B1 == 0 || B2 == 0)
printf("%ld,%ld %ld,%ld\n",i,j,nx,ny);
#endif
if (!overrange(nx,ny) && B1!=B2)
if (!connected[B1][B2])
{
connected[B1][B2]=true;
insert(B1,B2);
}
nx = i;
ny = j+1;
B1 = Belong[POS(i,j)];
B2 = Belong[POS(nx,ny)];
#ifdef Debug
if (B1 == 0 || B2 == 0)
printf("%ld,%ld %ld,%ld\n",i,j,nx,ny);
#endif
if (!overrange(nx,ny) && B1!=B2)
if (!connected[B1][B2])
{
connected[B1][B2]=true;
insert(B1,B2);
}
}
}
for (long i=1;i<K+1;i++)
{
long fx = transfrom[i].x;
long fy = transfrom[i].y;
long tx = transto[fx][fy].x;
long ty = transto[fx][fy].y;
long f = Belong[POS(fx,fy)];
long t = Belong[POS(tx,ty)];
#ifdef Debug
if (f == 0 || t == 0)
printf("%ld,%ld %ld,%ld\n",fx,fy,tx,ty);
#endif
if (!overrange(tx,ty)&&!connected[f][t] && f!=t)
{
connected[f][t] = true;
insert(f,t);
}
}
}
int main()
{
freopen("Instantaneous_Transference.in","r",stdin);
freopen("Instantaneous_Transference.out","w",stdout);
long TIMES;
scanf("%ld",&TIMES);
while (TIMES--)
{
Init();
for (long i=1;i<n+1;i++)
{
for (long j=1;j<m+1;j++)
{
if (!DFN(i,j) && map[i][j]>-2)
{
tarjan(i,j);
}
}
}
rebuild();
maxlength = 0;
destination = 0;
//long Start = Belong[POS(1,1)];
//dfs(Start,size[Start]);
//dijkstra();
SPFA();
for (long i=1;i<Bcnt+1;i++)
maxlength = MAX(maxlength,dist[i]);
printf("%ld\n",maxlength+size[Belong[POS(1,1)]]);
}
return 0;
}
![DB2表压缩功能[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)