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=)