POJ 3592 Instantaneous Transference
起初从boat大牛那里听说了这题,挺有意思的,就做了做。
题意:一辆坦克从N*M矩阵的左上角出发,每次往右或往 下走一格,每格可以是'#'(表示不可以走),'*'表示传送门,或者是数字,表示在该格可以获得的值(只能取一次),传送门可以传送到指定位置,你可以选择被传送或者走相邻的格,问坦克可以获得的值的和最大为多少。
解析:第一次看应该是个DP,(如果无传送门且可以走K轮,可以用网络流),但是矩阵中有传送门的存在,有可能形成环,所以要转化成DAG(有向无环图),可以以格子的相邻关系建边,然后求SCC,缩点再构图,边权为指向的格子的值,后求最长路(可以搜索,可以DP)。
WA了好几次,传送门有可能传到'#'的格子,格子是'#'的时候也要向相邻格子建边,题目求的是坦克可以获得的最大值,而不是到右下角的值(上回做了道类似的网络流,惯性导致想当然了)。
最后贴个代码:
#include <iostream> #include <cstring> #include <cstdio> #include <queue> using namespace std; struct Edge { int v; int next; }buf[50000]; int head[2000],head2[2000],nE; bool instack[2200]; int dfn[2020],low[2020],idx,Bcnt; int stack[2020],top; int Belong[2020]; int ores[2200]; int Bores[2200]; int N,M; void addEdge(int u,int v) { buf[nE].v=v;buf[nE].next=head[u];head[u]=nE++; } void addEdge2(int u,int v) { buf[nE].v=v;buf[nE].next=head2[u];head2[u]=nE++; } void Tarjan(int cur) { dfn[cur]=low[cur]=++idx; stack[top++]=cur; instack[cur]=true; for(int i=head[cur];i!=-1;i=buf[i].next) { int v=buf[i].v; if(!dfn[v]) { Tarjan(v); if(low[cur]>low[v]) low[cur]=low[v]; } else if(instack[v]&&low[cur]>dfn[v]) { low[cur]=dfn[v]; } } if(dfn[cur]==low[cur]) { Bcnt++; Bores[Bcnt]=0; int j; do { j=stack[--top]; instack[j]=false; Belong[j]=Bcnt; Bores[Bcnt]+=ores[j]; }while(j!=cur); } } void Rebuld() { memset(head2,0xff,sizeof(head2)); for(int i=0;i<N*M;i++) for(int j=head[i];j!=-1;j=buf[j].next) { int v=buf[j].v; if(Belong[i]!=Belong[v]) addEdge2(Belong[i],Belong[v]); } } void go() { memset(dfn,0,sizeof(dfn)); memset(instack,false,sizeof(instack)); idx=Bcnt=top=0; for(int i=0;i<N*M;i++) if(!dfn[i]) Tarjan(i); Rebuld(); int dis[2020]; memset(dis,0,sizeof(dis)); dis[Belong[0]]=Bores[Belong[0]]; queue<int> que; que.push(Belong[0]); bool inq[2020]; memset(inq,false,sizeof(inq)); inq[Belong[0]]=true; while(!que.empty()) { int cur=que.front();que.pop(); inq[cur]=false; for(int i=head2[cur];i!=-1;i=buf[i].next) { int v=buf[i].v; if(dis[v]<dis[cur]+Bores[v]) { dis[v]=dis[cur]+Bores[v]; if(!inq[v]) { inq[v]=true; que.push(v); } } } } int ans=-1; for(int i=1;i<=Bcnt;i++) if(dis[i]>ans) ans=dis[i]; printf("%d\n",ans); } char map[45][45]; int main() { int T; scanf("%d",&T); while(T--) { memset(head,0xff,sizeof(head)); nE=0; scanf("%d%d",&N,&M); for(int i=0;i<N;i++) scanf("%s",map[i]); memset(ores,0,sizeof(ores)); for(int i=0,r,c;i<N;i++) for(int j=0;j<M;j++) if(map[i][j]!='#') { if(i+1<N&&map[i+1][j]!='#')addEdge(i*M+j,(i+1)*M+j); if(j+1<M&&map[i][j+1]!='#')addEdge(i*M+j,i*M+j+1); ores[i*M+j]=map[i][j]-'0'; if(map[i][j]=='*') { ores[i*M+j]=0; scanf("%d%d",&r,&c); if(map[r][c]!='#') addEdge(i*M+j,r*M+c); } } go(); } return 0; }
0MS