http://poj.org/problem?id=3592
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <queue> 5 #define maxn 300000 6 using namespace std; 7 8 const int inf=-1<<30; 9 int e,head[maxn],belong[maxn],stack1[maxn],top,dfn[maxn],low[maxn],bcc_clock,bcnt,n,m,num1[100][100],num,gg[maxn],point[maxn],cc[maxn],ee,head1[maxn],dis[maxn],cnt[maxn],temp; 10 bool vis[maxn],visi[maxn]; 11 int dir[2][2]= {{0,1},{1,0}}; 12 struct node 13 { 14 int u,v,next; 15 } p[maxn]; 16 struct node1 17 { 18 int u,v,w,next; 19 } pp[maxn]; 20 char g[50][50]; 21 22 void add(int u,int v) 23 { 24 p[e].u=u; 25 p[e].v=v; 26 p[e].next=head[u]; 27 head[u]=e++; 28 } 29 30 void addnode(int u,int v,int w) 31 { 32 pp[ee].v=v; 33 pp[ee].u=u; 34 pp[ee].w=w; 35 pp[ee].next=head1[u]; 36 head1[u]=ee++; 37 } 38 39 void tarjan(int u) 40 { 41 vis[u]=true; 42 dfn[u]=low[u]=++bcc_clock; 43 stack1[++top]=u; 44 for(int i=head[u]; i!=-1; i=p[i].next) 45 { 46 int v=p[i].v; 47 if(!dfn[v]) 48 { 49 tarjan(v); 50 low[u]=min(low[u],low[v]); 51 } 52 else if(vis[v]) 53 low[u]=min(low[u],dfn[v]); 54 } 55 if(dfn[u]==low[u]) 56 { 57 bcnt++; 58 int j; 59 do 60 { 61 j=stack1[top--]; 62 vis[j]=false; 63 belong[j]=bcnt; 64 } 65 while(j!=u); 66 } 67 } 68 69 void init() 70 { 71 72 memset(dfn,0,sizeof(dfn)); 73 memset(low,0,sizeof(low)); 74 memset(belong,0,sizeof(belong)); 75 memset(cc,0,sizeof(cc)); 76 memset(vis,false,sizeof(vis)); 77 } 78 79 void del() 80 { 81 init(); 82 for(int i=0; i<n*m; i++) 83 { 84 if(!dfn[i]) 85 { 86 tarjan(i); 87 } 88 } 89 } 90 91 bool ralex(int u,int v,int c) 92 { 93 if(dis[v]<dis[u]+c) 94 { 95 dis[v]=dis[u]+c; 96 return true; 97 } 98 return false; 99 } 100 101 102 103 bool spfa(int src) 104 { 105 memset(visi,false,sizeof(visi)); 106 memset(cnt,0,sizeof(cnt)); 107 visi[src]=true; 108 for(int i=0; i<=bcnt; i++) 109 { 110 dis[i]=inf; 111 } 112 queue<int>q; 113 q.push(src); 114 dis[src]=0; 115 while(!q.empty()) 116 { 117 int u=q.front(); 118 q.pop(); 119 visi[u]=false; 120 for(int i=head1[u]; i!=-1; i=pp[i].next) 121 { 122 if(ralex(u,pp[i].v,pp[i].w)&&!visi[pp[i].v]) 123 { 124 if((++cnt[pp[i].v])>n*m) return false; 125 q.push(pp[i].v); 126 visi[pp[i].v]=true; 127 } 128 } 129 } 130 temp=0; 131 for(int i=1; i<bcnt+1; i++) 132 { 133 temp=max(temp,dis[i]); 134 } 135 return true; 136 } 137 int main() 138 { 139 int t; 140 scanf("%d",&t); 141 while(t--) 142 { 143 scanf("%d%d",&n,&m); 144 num=0; 145 int cn=0; 146 memset(head1,-1,sizeof(head1)); 147 memset(head,-1,sizeof(head)); 148 e=0,top=0,bcnt=0,bcc_clock=0,ee=0; 149 getchar(); 150 for(int i=0; i<n; i++) 151 { 152 scanf("%s",g[i]); 153 } 154 for(int i=0; i<n; i++) 155 { 156 for(int j=0; j<m; j++) 157 { 158 int k=i*m+j; 159 if(g[i][j]=='#') 160 { 161 gg[k]=-1; 162 continue; 163 } 164 else 165 { 166 if(g[i][j]=='*') 167 { 168 point[cn++]=k; 169 gg[k]=0; 170 } 171 else if(g[i][j]>='0'&&g[i][j]<='9') 172 { 173 gg[k]=g[i][j]-'0'; 174 } 175 for(int c=0; c<2; c++) 176 { 177 int xx=i+dir[c][0]; 178 int yy=j+dir[c][1]; 179 if(xx<n&&yy<m) 180 { 181 if(g[xx][yy]!='#') 182 { 183 add(k,xx*m+yy); 184 } 185 } 186 } 187 188 } 189 } 190 } 191 for(int i=0; i<cn; i++) 192 { 193 int x,y; 194 scanf("%d%d",&x,&y); 195 if(g[x][y]!='#') 196 { 197 add(point[i],x*m+y); 198 } 199 } 200 del(); 201 for(int i=0; i<n*m; i++) 202 { 203 cc[belong[i]]+=gg[i]; 204 } 205 addnode(0,belong[0],cc[belong[0]]); 206 for(int i=0; i<n*m; i++) 207 { 208 for(int j=head[i]; j!=-1; j=p[j].next) 209 { 210 int v=p[j].v; 211 if(belong[i]!=belong[v]) 212 { 213 addnode(belong[i],belong[v],cc[belong[v]]); 214 } 215 } 216 } 217 spfa(0); 218 printf("%d ",temp); 219 } 220 return 0; 221 }