http://poj.org/problem?id=3592
题意：给出一个n*m的矩阵，左上角代表起始点，每个格子都有一定价值的金矿，其中‘#’代表岩石不可达，‘*’代表时空门可以到达指定格子，求出可以获得的最大价值。
思路：时空门的存在可能会使得图中出现环，所以先对强连通分量进行缩点，然后对于缩点后的连通分量建立有向无环图，spfa求到起始点的最长路。
1 #include <stdio.h> 2 #include <iostream> 3 #include <string.h> 4 #include <queue> 5 #include <stack> 6 using namespace std; 7 const int N=2020; 8 const int INF=-1<<28; 9 struct node 10 { 11 int u,v,w; 12 int next; 13 } edge1[N*2],edge2[N*2];//edge1[]存的是原始图的边，edge2[]存的是缩点后的边 14 int low[N],dfn[N],sccno[N];//sccno[i]表示点i所属于的连通分量的编号 15 int dis[N],head1[N],head2[N],val[N];//val[]存储每个连通分量的价值 16 int n,m,scc_cnt,cnt,dfs_clock; 17 bool vis[N]; 18 stack<int>S; 19 20 void init() 21 { 22 cnt = 0; 23 scc_cnt = 0; 24 dfs_clock = 0; 25 memset(val,0,sizeof(val)); 26 memset(low,0,sizeof(low)); 27 memset(dfn,0,sizeof(dfn)); 28 memset(sccno,0,sizeof(sccno)); 29 memset(head1,-1,sizeof(head1)); 30 memset(head2,-1,sizeof(head2)); 31 32 } 33 void add(int u,int v,int w,node *edge,int *head) 34 { 35 edge[cnt].u = u; 36 edge[cnt].v = v; 37 edge[cnt].w = w; 38 edge[cnt].next = head[u]; 39 head[u] = cnt++; 40 } 41 void Tarjan(int u)//求强连通分量 42 { 43 low[u]=dfn[u]=++dfs_clock; 44 S.push(u); 45 for (int i = head1[u]; i!=-1; i=edge1[i].next) 46 { 47 int v = edge1[i].v; 48 if (!dfn[v]) 49 { 50 Tarjan(v); 51 low[u]=min(low[u],low[v]); 52 } 53 else if (!sccno[v]) 54 { 55 low[u]=min(low[u],dfn[v]); 56 } 57 } 58 if (low[u]==dfn[u]) 59 { 60 ++scc_cnt; 61 while(1) 62 { 63 int v = S.top(); 64 S.pop(); 65 sccno[v] = scc_cnt; 66 if (v==u) 67 break; 68 } 69 } 70 } 71 void spfa(int s)//求缩点后的最长路 72 { 73 for (int i = 0; i <= n*m; i++) 74 { 75 dis[i]=INF; 76 vis[i]=false; 77 } 78 dis[s] = 0; 79 queue<int>q; 80 q.push(s); 81 vis[s] = true; 82 while(!q.empty()) 83 { 84 int u = q.front(); 85 q.pop(); 86 vis[u]=false; 87 for (int i = head2[u]; i!=-1; i=edge2[i].next) 88 { 89 int v = edge2[i].v; 90 int w = edge2[i].w; 91 if (dis[v] < dis[u]+w) 92 { 93 dis[v] = dis[u]+w; 94 if (!vis[v]) 95 { 96 q.push(v); 97 vis[v]=true; 98 } 99 } 100 101 } 102 } 103 } 104 int main() 105 { 106 int t; 107 char map[102][102]; 108 scanf("%d",&t); 109 while(t--) 110 { 111 scanf("%d%d",&n,&m); 112 init(); 113 for(int i = 0; i < n; i++) 114 { 115 scanf("%s",map[i]); 116 } 117 for (int i = 0; i < n; i++) 118 { 119 for (int j = 0; j < m; j++) 120 { 121 if (map[i][j]!='#') 122 { 123 if(i) add((i-1)*m+j,i*m+j,0,edge1,head1); 124 if(j) add(i*m+j-1,i*m+j,0,edge1,head1); 125 if (map[i][j]=='*') 126 { 127 int x,y; 128 scanf("%d%d",&x,&y); 129 if(map[x][y]!='#') 130 add(i*m+j,x*m+y,0,edge1,head1); 131 } 132 } 133 } 134 } 135 for (int i = 0; i < n; i++) 136 { 137 if (!dfn[i]) 138 Tarjan(i); 139 } 140 for (int i = 0; i < n; i++) 141 { 142 for (int j = 0; j < m; j++) 143 { 144 if(map[i][j]!='*'&&map[i][j]!='#') 145 { 146 int num = sccno[i*m+j]; 147 val[num]+=map[i][j]-'0';//记录每个连通分量的价值 148 } 149 } 150 } 151 for (int u = 0; u < n*m; u++) 152 { 153 for (int j = head1[u]; j!=-1; j=edge1[j].next) 154 { 155 int v = edge1[j].v; 156 if(sccno[u]!=sccno[v]) 157 { 158 add(sccno[u],sccno[v],val[sccno[v]],edge2,head2); 159 }//对缩点后的连通分量建立有向图 160 } 161 } 162 spfa(sccno[0]);//求出每个点到起始点的价值 163 int max=-1; 164 for (int i = 1; i <= scc_cnt; i++) 165 { 166 if (max < dis[i]) 167 max = dis[i];//求出到原点的最大价值 168 } 169 int ans = max+val[sccno[0]];//总最大价值=到原点的最大价值+原点的价值 170 printf("%d ",ans); 171 } 172 return 0; 173 }