本文主要是介绍【TOJ】2248 Channel Design 最小树形图——朱刘算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
传送门：【TOJ】2248 Channel Design
题目大意：大概意思是需要从水库（编号始终为1）引水到所有的农场（编号2~n），通过m条水管引水直接或间接的得到水（即有边(1,2),(2,3)，则说明3能间接的得到水），其中水管是单向的，且每条水管的铺设都需要一定的费用，问要从水库引水到所有的农场的最少花费。如果无解输出impossible。
题目分析：最小树形图模板题。
这次将代码好好的整理的一下，并加上了一些注释。
代码如下：
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;#define REP( i , n ) for ( int i = 0 ; i < n ; ++ i )
#define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define REPV( i , a , b ) for ( int i = a ; i >= b ; -- i )
#define clear( a , x ) memset ( a , x , sizeof a )const int MAXN = 105 ;
const int MAXE = 10005 ;
const int INF = 0x3f3f3f3f ;struct Edge {int u , v , c ;void input () {scanf ( "%d%d%d" , &u , &v , &c ) ;-- u ;//结点编号为实际编号-1-- v ;}
} ;struct MST {Edge E[MAXE] ;//边集int p[MAXN] ;//并查集&父亲int val[MAXN] ;//最小边权入边int color[MAXN] ;//染色int idx[MAXN] ;//缩点后编号int NV , NE ;//结点个数，边个数int root ;//根结点编号void input () {REP ( i , NE ) {E[i].input () ;if ( E[i].u == E[i].v )E[i].c = INF ;}}int find ( int x ) {//递归压缩路径足以return p[x] == x ? x : ( p[x] = find ( p[x] ) ) ;}int check () {//并查集检查根结点能否到达其他所有顶点//能 ：返回1//不能：返回0int u , v ;REP ( i , NV )p[i] = i ;REP ( i , NE ) {u = find ( E[i].u ) ;v = find ( E[i].v ) ;if ( u != v && v != root )//注意根结点不能并到别的结点上p[v] = u ;//反向合并，表示u能到达v}REP ( i , NV )if ( p[i] != root )//根结点不能到达结点ireturn 0 ;return 1 ;}int build () {int res = 0 ;while ( true ) {clear ( val , INF ) ;REP ( i , NE ) {int u = E[i].u ;int v = E[i].v ;if ( u != v && val[v] > E[i].c ) {//寻找不存在自环的最小入边p[v] = u ;//记录父亲val[v] = E[i].c ;}}int cnt = 1 ;clear ( idx , -1 ) ;clear ( color , 0 ) ;p[root] = root ;idx[root] = 0 ;//根结点的cnt值始终为0val[root] = 0 ;//根结点没有入边REP ( i , NV ) {res += val[i] ;//累加最小入边边权int v = i ;while ( color[v] != i && idx[v] == -1 && v != root ) {/*只可能找到一个环或者找到根*/color[v] = i ;//染色v = p[v] ;//往回走}if ( idx[v] == -1 && v != root ) {//找到一个环，并且该环未缩点，那么将环中的所有结点缩点，编号为cntfor ( int u = p[v] ; u != v ; u = p[u] )//既然是环则一定会出现u = vidx[u] = cnt ;idx[v] = cnt ++ ;}}if ( cnt == 1 )return res ;REP ( i , NV )if ( idx[i] == -1 )idx[i] = cnt ++ ;//不在环中的结点REP ( i , NE ) {int u = E[i].u ;int v = E[i].v ;//结点编号变为缩点后的编号E[i].u = idx[u] ;E[i].v = idx[v] ;if ( idx[u] != idx[v] )//如果不形成自环E[i].c -= val[v] ;//减去相应的权值/*这里不仅从环外到环内的边要减，其他的边也要减，目的是为了之后的之后的计算中不需要特殊判断去掉已经添加的边，对于不是环外到环内的边，E[i].c = E[i].c - val[v] = 0，以后的计算就算+0也不会影响结果。*/}NV = cnt ;//顶点个数变为缩点后的个数}return res ;//返回结果}void solve () {input () ;root = 0 ;//根为固定的编号为1的点（已经自减1）if ( !check () ) {//如果不能从根达到所有点printf ( "impossible\n" ) ;return ;}printf ( "%d\n" , build () ) ;}
} ;MST z ;int main () {while ( ~scanf ( "%d%d" , &z.NV , &z.NE ) && ( z.NV || z.NE ) )z.solve () ;return 0 ;
}这篇关于【TOJ】2248 Channel Design 最小树形图——朱刘算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
