题意：给出一个N*M的矩形，每个小矩形里有的有一定数量的矿物，有的有传输的功能，有的不能通过，每个小矩形里的矿物只能采集一次，问你最多能过采集多少的矿物。
思路：强连通分支+spfa，先求出强连通分支，在强连通分支中，所以点都是可达的，然后进行缩点，将每一个连通分支看做一个点，而这个点的矿物容量就是这个强连通分支中所有点的和，然后在用一下spfa求最大的矿物量。
PS：因为没注意一个循环的长度，导致我查了一个下午加一个晚上，泪~~，细心！细心啊！
代码：
View Code
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <iostream> #include <algorithm> #include <queue> #include <math.h> #define N 2004 #define M 50 #define T 200020 using namespace std ; struct node { int u ; int v ; int val ; int next ; }p[T] , d[T] ; int head1[N] , head2[N] ; int dfn[N] , low[N] ; int dis[N] , vist[N] ; int belong[N] , sum[N] , valx[N] ; int st[N] , q[N] , f[N] ; int n , m , cnt , num1 , num2 , res , index , all ; int top ; void add( int x , int y ) { p[num1].u = x ; p[num1].v = y ; p[num1].next = head1[x] ; head1[x] = num1++ ; } void add2( int x , int y , int c ) { d[num2].u = x ; d[num2].v = y ; d[num2].val = c ; d[num2].next = head2[x] ; head2[x] = num2++ ; } int min( int x , int y ) { return x < y ? x : y ; } void dfs( int x ) { int y , u ; dfn[x] = low[x] = index++ ; st[top++] = x ; f[x] = 1; for ( y = head1[x] ; y != -1 ; y = p[y].next ) { u = p[y].v ; if ( !dfn[u] ) { dfs( u ) ; low[x] = min( low[x] , low[u] ); } else if ( f[u] ) low[x] = min( low[x] , dfn[u] ) ; } if ( dfn[x] == low[x] ) { res++ ; do { y = st[--top] ; f[y] = 0 ; belong[y] = res ; }while( y != x ) ; } } void Tarjan() { int i ; memset( dfn , 0 , sizeof( dfn )); memset( low , 0 , sizeof( low )); memset( st , 0 , sizeof ( st )); memset( f , 0 , sizeof ( f )) ; top = 0 ;index = 1 ;res = 0 ; for ( i = 0 ; i < all ; i++ ) if ( !dfn[i] ) dfs( i ); memset( sum , 0 , sizeof ( sum )) ; for ( i = 0 ; i < all ; i++ ) sum[belong[i]] += valx[i] ; } void slove( int s ) { int x , y ; int len = res + 1 ; memset( q , 0 , sizeof( q )); for( x = 0 ; x < len ; x++ ) { dis[x] = -1 ; vist[x] = 0 ; } dis[s] = 0 ; //vist[s] = 1 ; int head = 0 ; int tail = 0 ; q[head++] = s ; while( head != tail ) { x = q[tail++] ; vist[x] = 0 ; if ( tail == N ) tail = 0 ; for ( y = head2[x] ; y != -1 ; y = d[y].next ) { int v = d[y].v ; if ( dis[v] < dis[x] + d[y].val ) { dis[v] = dis[x] + d[y].val ; if( !vist[v] ) { vist[v] = 1 ; q[head++] = v ; if ( head == N ) head = 0 ; } } } } } int spfa() { int i , j ; num2 = 2 ; memset( head2 , -1 , sizeof( head2 )) ; add2( 0 , belong[0] , sum[belong[0]] ) ; for ( i = 0 ; i < all ; i++ ) { for ( j = head1[i] ; j != -1 ; j = p[j].next ) { int v = p[j].v ; if ( belong[i] != belong[v] ) add2( belong[i] , belong[v] , sum[belong[v]] ); } } slove( 0 ); int maxx = 0 ; for ( i = 1 ; i <= res ; i++ ) if ( dis[i] > maxx ) maxx = dis[i] ; return maxx ; } void work() { int i , j , r , c , k ; char str[M][M] ; int data[M][M] , pos[N] ; int dir[2][2] = {{-1, 0} , {0 ,-1}} ; all = 0 ; num1 = 2 ;k = 0 ; memset( head1 , -1 , sizeof ( head1 )); scanf( "%d%d" , &n , &m ) ; for ( i = 0 ; i < n ; i++ ) { scanf ( "%s" , str[i] ); for ( j = 0 ; j < m ; j++ ) { if ( str[i][j] == '#' ) continue ; data[i][j] = all++ ; if ( str[i][j] >= '0' && str[i][j] <= '9') { valx[data[i][j]] = str[i][j] - '0' ; } else { valx[data[i][j]] = 0 ; } if ( str[i][j] == '*' ) { pos[k++] = data[i][j] ; } for ( int xx = 0 ; xx < 2 ; xx++ ) { r = i + dir[xx][0] ; c = j + dir[xx][1] ; if( r >= 0 && c >= 0 ) { if ( str[r][c] == '#' ) continue ; add( data[r][c] , data[i][j] ); } } } } for ( i = 0 ; i < k ; i++ ) { scanf ( "%d%d" , &r , &c ) ; if ( str[r][c] == '#' ) continue ; add( pos[i] , data[r][c] ); } Tarjan(); int ans = spfa( ); printf ( "%d\n" , ans ); } int main() { int cas ; scanf( "%d" , &cas ); while ( cas-- ) { work(); } return 0 ; }