Instantaneous Transference
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 Source South Central China 2008 hosted by NUDT |
提示
題意：
很久很久以前我們還在玩紅色警戒。。。現在你有一輛遊戲中的卡車，你需要在地圖上收集盡可能多的礦石，地圖為n*m(2<=n<=40,2<=m<=40)的矩陣，地圖中有數字0~9，'#'，'*'組成，其中數字代表的是這一位置的礦石數，'#'代表的是牆壁，顧名思義牆是不可以走的，'*'表示傳送門（該位置無礦石），可以将礦車傳送到地圖中的某一點（包括牆），車隻能向下或向右走，以左上角為起點請求出礦石最大搜集量。
思路：
給地圖點編号，如：
0,1,2,3
4,5,6,7
...
在地圖上建立地圖每個點的邊，之後利用這些縮點，再建一個新圖，在新圖上跑一下最長路即可。
示例程式
Source Code
Problem: 3592 Code Length: 3673B
Memory: 776K Time: 0MS
Language: GCC Result: Accepted
#include <stdio.h>
#include <string.h>
struct
{
int v,next;
}w[2][4000];
int h[2][3200],numw[2],val[3200],sumval[3200],dfn[3200],low[3200],vis[3200],stack[80000],id[3200],count,deep,top;
void insert(int u,int v,int flag) //flag表示目前建立的是縮點前還是縮點後的圖（[0][]縮點前[1][]縮點後）
{
w[flag][numw[flag]].v=v;
w[flag][numw[flag]].next=h[flag][u];
h[flag][u]=numw[flag];
numw[flag]++;
}
void tarjan(int t)
{
int pos,i;
dfn[t]=deep;
low[t]=deep;
deep++;
vis[t]=1;
stack[top]=t;
top++;
for(i=h[0][t];i!=-1;i=w[0][i].next)
{
pos=w[0][i].v;
if(dfn[pos]==-1)
{
tarjan(pos);
if(low[t]>low[pos])
{
low[t]=low[pos];
}
}
else if(vis[pos]==1&&low[t]>dfn[pos])
{
low[t]=dfn[pos];
}
}
if(dfn[t]==low[t])
{
sumval[count]=0;
do
{
top--;
pos=stack[top];
sumval[count]=sumval[count]+val[pos]; //分量中每個點礦石數加和
id[pos]=count; //記錄每個點所屬于哪個分量
vis[pos]=0;
}while(t!=pos);
count++;
}
}
void bulid(int n)
{
int i,i1;
for(i=0;n>i;i++) //枚舉地圖中每個點
{
for(i1=h[0][i];i1!=-1;i1=w[0][i1].next)
{
if(id[i]!=id[w[0][i1].v]) //起點和終點不屬于同一個分量就建邊
{
insert(id[i],id[w[0][i1].v],1);
}
}
}
}
int spfa()
{
int v[3200],d[3200],q[80000],i,pos,f=0,top=0,max;
for(i=0;count>i;i++)
{
v[i]=0;
d[i]=0;
}
pos=id[0]; //從左上角開始
v[pos]=1;
d[pos]=sumval[pos];
q[top]=pos;
top++;
while(f<top)
{
v[q[f]]=0;
for(i=h[1][q[f]];i!=-1;i=w[1][i].next)
{
pos=w[1][i].v;
if(d[pos]<d[q[f]]+sumval[pos])
{
d[pos]=d[q[f]]+sumval[pos];
if(v[pos]==0)
{
q[top]=pos;
top++;
v[pos]=1;
}
}
}
f++;
}
max=d[0];
for(i=1;count>i;i++)
{
if(max<d[i])
{
max=d[i];
}
}
return max;
}
int main()
{
int t,i,i1,i2,n,m,x,y;
char map[40][41];
scanf("%d",&t);
for(i=1;t>=i;i++)
{
scanf("%d %d",&n,&m);
memset(h,-1,sizeof(h));
memset(dfn,-1,sizeof(dfn));
memset(low,-1,sizeof(low));
memset(vis,0,sizeof(vis));
numw[0]=0;
numw[1]=0;
count=0;
deep=0;
top=0;
for(i1=0;n>i1;i1++)
{
scanf("%s",map[i1]);
}
for(i1=0;n>i1;i1++)
{
for(i2=0;m>i2;i2++)
{
if(map[i1][i2]!='#')
{
if(i1+1<n&&map[i1+1][i2]!='#')
{
insert(i1*m+i2,(i1+1)*m+i2,0); //與下一行同列的點建立邊
}
if(i2+1<m&&map[i1][i2+1]!='#')
{
insert(i1*m+i2,i1*m+i2+1,0); //與同行下一列的點建立邊
}
if(map[i1][i2]!='*') //該點有礦石
{
val[i1*m+i2]=map[i1][i2]-'0';
}
else //傳送門，同樣要建立邊
{
val[i1*m+i2]=0;
scanf("%d %d",&x,&y);
if(map[x][y]!='#')
{
insert(i1*m+i2,x*m+y,0);
}
}
}
}
}
for(i1=0;n*m>i1;i1++)
{
if(dfn[i1]==-1) //Tarjan縮點
{
tarjan(i1);
}
}
bulid(n*m); //建立新圖
printf("%d\n",spfa());
}
return 0;
}
![POJ 1985 Cow Marathon（牛的鍛煉，樹的直徑）[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)