【Live Archive】6395 SurelyYouCongest【最短路+最大流】

本文主要是介绍【Live Archive】6395 SurelyYouCongest【最短路+最大流】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门：【Live Archive】6395 SurelyYouCongest

题目分析：我们只要从点1开始做一次最短路预处理，然后对于给定的源点们，对于最短路图构成一个层次图，然后由于每一层都是互不影响的，所以我们对每一层暴力跑网络流就好了。

$my~~code:$

#include <stdio.h>
#include <string.h>
#include <set>
#include <map>
#include <math.h>
#include <vector>
#include <algorithm>
using namespace std ;typedef long long LL ;#define clr( a , x ) memset ( a , x , sizeof a )
#define cpy( a , x ) memcpy ( a , x , sizeof a )const int MAXN = 25005 ;
const int MAXE = 1000005 ;
const int INF = 0x3f3f3f3f ;struct Edge {int v , c , n ;Edge () {}Edge ( int v , int c , int n ) : v ( v ) , c ( c ) , n ( n ) {}
} ;struct Path {Edge E[MAXE] ;int H[MAXN] , cntE ;int d[MAXN] ;int vis[MAXN] ;int Q[MAXN] , head , tail ;void init () {cntE = 0 ;clr ( H , -1 ) ;}void addedge ( int u , int v , int c ) {E[cntE] = Edge ( v , c , H[u] ) ;H[u] = cntE ++ ;}void spfa () {head = tail = 0 ;clr ( d , INF ) ;clr ( vis , 0 ) ;Q[tail ++] = 1 ;d[1] = 0 ;while ( head != tail ) {int u = Q[head ++] ;vis[u] = 0 ;if ( head == MAXN ) head = 0 ;for ( int i = H[u] ; ~i ; i = E[i].n ) {int v = E[i].v ;if ( d[v] > d[u] + E[i].c ) {d[v] = d[u] + E[i].c ;if ( !vis[v] ) {vis[v] = 1 ;Q[tail ++] = v ;if ( tail == MAXN ) tail = 0 ;}}}}}
} ;struct Flow {Edge E[MAXE] ;int H[MAXN] , cntE ;int d[MAXN] , cur[MAXN] , pre[MAXN] , gap[MAXN] ;int Q[MAXN] , head , tail ;int s , t , nv ;int flow ;void init () {cntE = 0 ;clr ( H , -1 ) ;}void addedge ( int u , int v , int c ) {E[cntE] = Edge ( v , c , H[u] ) ;H[u] = cntE ++ ;E[cntE] = Edge ( u , 0 , H[v] ) ;H[v] = cntE ++ ;}void rev_bfs () {head = tail = 0 ;clr ( d , -1 ) ;clr ( gap , 0 ) ;d[t] = 0 ;gap[0] = 1 ;Q[tail ++] = t ;while ( head != tail ) {int u = Q[head ++] ;for ( int i = H[u] ; ~i ; i = E[i].n ) {int v = E[i].v ;if ( d[v] == -1 ) {d[v] = d[u] + 1 ;Q[tail ++] = v ;gap[d[v]] ++ ;}}}}int isap () {cpy ( cur , H ) ;rev_bfs () ;flow = 0 ;int u = pre[s] = s , i ;while ( d[s] < nv ) {if ( u == t ) {int f = INF ;for ( i = s ; i != t ; i = E[cur[i]].v ) {if ( f > E[cur[i]].c ) {f = E[cur[i]].c ;u = i ;}}for ( i = s ; i != t ; i = E[cur[i]].v ) {E[cur[i]].c -= f ;E[cur[i] ^ 1].c += f ;}flow += f ;}for ( i = cur[u] ; ~i ; i = E[i].n ) {if ( E[i].c && d[u] == d[E[i].v] + 1 ) break ;}if ( ~i ) {cur[u] = i ;pre[E[i].v] = u ;u = E[i].v ;} else {if ( 0 == -- gap[d[u]] ) break ;int minv = nv ;for ( i = H[u] ; ~i ; i = E[i].n ) {int v = E[i].v ;if ( E[i].c && minv > d[v] ) {minv = d[v] ;cur[u] = i ;}}d[u] = minv + 1 ;gap[d[u]] ++ ;u = pre[u] ;}}return flow ;}
} ;struct Node {int x , idx ;Node () {}Node ( int x , int idx ) : x ( x ) , idx ( idx ) {}bool operator < ( const Node& a ) const {return x < a.x ;}
} ;Node a[MAXN] ;
Path p ;
Flow f ;
int n , m , q ;
int vis[MAXE] ;void dfs ( int u ) {for ( int i = p.H[u] ; ~i ; i = p.E[i].n ) {int v = p.E[i].v ;if ( vis[i] || p.d[v] > p.d[u] ) continue ;if ( p.d[u] == p.d[v] + p.E[i].c ) {vis[i] = 1 ;f.addedge ( u , v , 1 ) ;dfs ( v ) ;}}
}void solve () {int u , v , c ;p.init () ;f.s = 0 , f.t = n + 1 , f.nv = f.t + 1 ;for ( int i = 1 ; i <= m ; ++ i ) {scanf ( "%d%d%d" , &u , &v , &c ) ;p.addedge ( u , v , c ) ;p.addedge ( v , u , c ) ;}p.spfa () ;for ( int i = 1 ; i <= q ; ++ i ) {scanf ( "%d" , &u ) ;a[i] = Node ( p.d[u] , u ) ;}sort ( a + 1 , a + q + 1 ) ;int ans = 0 ;for ( int i = 1 ; i <= q ; ++ i ) {f.init () ;f.addedge ( 1 , f.t , INF ) ;f.addedge ( f.s , a[i].idx , 1 ) ;clr ( vis , 0 ) ;dfs ( a[i].idx ) ;while ( i < q && a[i].x == a[i + 1].x ) {++ i ;f.addedge ( f.s , a[i].idx , 1 ) ;dfs ( a[i].idx ) ;}ans += f.isap () ;}printf ( "%d\n" , ans ) ;
}int main () {while ( ~scanf ( "%d%d%d" , &n , &m , &q ) ) solve () ;return 0 ;
}