传送门：【HDU】4411 Arrest

题目分析：题目的意思一开始没看懂= =。。。题意大致为：派出至多K个警队遵守先灭小的再灭老的的原则将N个城市的帮派全端了（要灭编号大的必须要先灭编号小的）。且一个警队可以一次端多个城市。

首先floyd预处理出所有点对之间的最短路，题目保证两点之间一定可达。令G[i][j]为i到j的最短路。

题目要求的必须先灭i才能灭i+1总可以通过合理的警队剿灭顺序做到（比如警队1灭了帮派1，警队2灭了帮派2然后回家，然后警队1再灭了帮派3再回家）。于是本题转化成K路径覆盖问题。首先每个点都必须被走到，那么将一个点 i 拆成两个点i、i+n，然后建边( i , i + n , 1 , -M )，其中M为比最大的路径长度还大的一个数，目的是为了一定将点i取到，这里设为100000(100000>99*1000)。容量为1表示只能被剿灭一次。

然后设立源点s，汇点t，源点向0建边( s , 0 , K , 0 )表示至多能派K个警队。0向1~n建边( 0 , i , 1 , G[ 0 ][ i ] )表示一支警队从0出发到i（为什么容量设为1？因为只用一支警队去剿灭帮派i，而且如果有别的警队要去剿灭别的帮派必须要经过i的话，那么最短路上其实已经算上0~i的最短路了，所以没必要重复添加，并且正好和上面的建图对应）。

1~n向汇点建边( i + n , t , 1 , G[ i ][ 0 ] )表示警队抓完帮派i回家(0)了。

然后对所有的点i，向所有的j( j > i )建边( i + n , j , 1 , G[ i ][ j ] )表示抓完帮派i要去抓帮派j了（因为只能抓了小的才能抓大的，所以只能是小的向大的建边）。

最后，由于当费用最小的时候并不是最大流（不是所有的警察都一定要用到），所以建边( 0 , t , K , 0 )表示用不到的警察直接不出门了。

代码如下：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;#define REP( i , a , b ) for ( int i = ( a ) ; i <  ( b ) ; ++ i )
#define FOR( i , a , b ) for ( int i = ( a ) ; i <= ( b ) ; ++ i )
#define REV( i , a , b ) for ( int i = ( a ) ; i <= ( b ) ; -- i )
#define travel( e , H , u ) for ( Edge* e = H[u] ; e ; e = e -> next )
#define CLR( a , x ) memset ( a , x , sizeof a )
#define cPY( a , x ) memcpy ( a , x , sizeof a )const int M = 100000 ;
const int MAXN = 205 ;
const int MAXE = 20000 ;
const int INF = 0x3f3f3f3f ;struct Edge {int v , c , w , n ;Edge () {}Edge ( int v , int c , int w , int n ) : v ( v ) , c ( c ) , w ( w ) , n ( n ) {}
} ;struct Net {Edge E[MAXE] ;int H[MAXN] , cntE ;int d[MAXN] , cap[MAXN] , cur[MAXN] ;int Q[MAXN] , head , tail ;bool vis[MAXN] ;int s , t ;int flow , cost ;int n , m , K ;int G[105][105] ;void init () {cntE = 0 ;CLR ( H , -1 ) ;}void addedge ( int u , int v , int c , int w ) {E[cntE] = Edge ( v , c ,  w , H[u] ) ;H[u] = cntE ++ ;E[cntE] = Edge ( u , 0 , -w , H[v] ) ;H[v] = cntE ++ ;}bool spfa () {CLR ( d , INF ) ;CLR ( vis , 0 ) ;head = tail = 0 ;cap[s] = INF ;cur[s] = -1 ;d[s] = 0 ;Q[tail ++] = s ;while ( head != tail ) {int u = Q[head ++] ;if ( head == MAXN ) head = 0 ;vis[u] = 0 ;for ( int i = H[u] ; ~i ; i = E[i].n ) {int v = E[i].v , c = E[i].c , w = E[i].w ;if ( c && d[v] > d[u] + w ) {d[v] = d[u] + w ;cap[v] = min ( c , cap[u] ) ;cur[v] = i ;if ( !vis[v] ) {vis[v] = 1 ;if ( d[v] < d[Q[head]] ) {if ( head == 0 ) head = MAXN ;Q[-- head] = v ;} else {Q[tail ++] = v ;if ( tail == MAXN ) tail = 0 ;}}}}}if ( d[t] == INF ) return 0 ;flow += cap[t] ;cost += cap[t] * d[t] ;for ( int i = cur[t] ; ~i ; i = cur[E[i ^ 1].v] ) {E[i].c -= cap[t] ;E[i ^ 1].c += cap[t] ;}return 1 ;}int MCMF () {flow = cost = 0 ;while ( spfa () ) ;return cost ;}void solve () {int u , v , c , w ;init () ;CLR ( G , INF ) ;s = n << 1 | 1 ;t = s + 1 ;while ( m -- ) {scanf ( "%d%d%d" , &u , &v , &w ) ;G[u][v] = G[v][u] = min ( G[u][v] , w ) ;}FOR ( k , 0 , n ) FOR ( i , 0 , n ) FOR ( j , 0 , n ) G[i][j] = min ( G[i][j] , G[i][k] + G[k][j] ) ;FOR ( i , 1 , n ) addedge ( i , i + n , 1 , -M ) ;FOR ( i , 1 , n ) addedge ( 0 , i , 1 , G[0][i] ) ;FOR ( i , 1 , n ) addedge ( i + n , t , 1 , G[i][0] ) ;FOR ( i , 1 , n ) FOR ( j , i + 1 , n ) addedge ( i + n , j , 1 , G[i][j] ) ;addedge ( s , 0 , K , 0 ) ;addedge ( 0 , t , K , 0 ) ;printf ( "%d\n" , MCMF () + M * n ) ;}
} e ;int main () {while ( ~scanf ( "%d%d%d" , &e.n , &e.m , &e.K ) && ( e.n || e.m || e.K ) ) e.solve () ;return 0 ;
}