传送门：【HDU】3072 Intelligence System

题目大意：
给你一副有向图，其中每条边都有一个权值，现在你的目的是选择一些边使得图连通并且权和最小，其中，如果选择后使得一些点强连通，则在强连通分量上的边权值为0。

题目分析：首先强连通缩点，因为一个强连通内的边不计入权和内，所以就不用管了，然后根据题意，我们可以为每个点贪心的选择一条权值最小的边作为入边（因为缩点以后是一个DAG图，所以没有入度的点就不用选择了），最后所有选择的边的权和就是答案。

PS：因为将continue 打成 return。。导致我错的飞起来QUQ
代码如下：

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std ;

#define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define REP( i , n ) for ( int i = 0 ; i < n ; ++ i )
#define CLEAR( a , x ) memset ( a , x , sizeof a )

const int MAXN = 50005 ;
const int MAXE = 100005 ;
const int MAXQ = 100005 ;
const int MAXM = 105 ;
const int INF = 0x3f3f3f3f ;

struct Edge {
	int v , n , w ;
	Edge ( int v = 0 , int n = 0 , int w = 0 ) : v ( v ) , n ( n ) , w ( w ) {}
} ;

struct SCC {
	Edge edge[MAXE] ;
	int adj[MAXN] , cntE ;
	int Dfn[MAXN] , Low[MAXN] ;
	int dfs_clock , scc_cnt ;
	int S[MAXN] , top ;
	bool ins[MAXN] ;
	int scc[MAXN] ;
	
	void init () {
		top = 0 ;
		cntE = 0 ;
		scc_cnt = 0 ;
		dfs_clock = 0 ;
		CLEAR ( Dfn , 0 ) ;
		CLEAR ( ins , 0 ) ;
		CLEAR ( adj , -1 ) ;
	}
	
	void addedge ( int u , int v , int w ) {
		edge[cntE] = Edge ( v , adj[u] , w ) ;
		adj[u] = cntE ++ ;
	}
	
	void Tarjan ( int u ) {
		Dfn[u] = Low[u] = ++ dfs_clock ;
		ins[u] = true ;
		S[top ++] = u ;
		for ( int i = adj[u] ; ~i ; i = edge[i].n ) {
			int v = edge[i].v ;
			if ( !Dfn[v] ) {
				Tarjan ( v ) ;
				Low[u] = min ( Low[u] , Low[v] ) ;
			}
			else if ( ins[v] )
				Low[u] = min ( Low[u] , Dfn[v] ) ;
		}
		if ( Dfn[u] == Low[u] ) {
			++ scc_cnt ;
			while ( 1 ) {
				int v = S[-- top] ;
				scc[v] = scc_cnt ;
				ins[v] = 0 ;
				if ( v == u )
					break ;
			}
		}
	}
	
	void find_SCC ( int n ) {
		REP ( i , n )
			if( !Dfn[i] )
				Tarjan ( i ) ;
	}
} ;

SCC C ;
int cost[MAXM] ;

void work () {
	int n , m ;
	int u , v , w ;
	while ( ~scanf ( "%d%d" , &n , &m ) ) {
		C.init () ;
		while ( m -- ) {
			scanf ( "%d%d%d" , &u , &v , &w ) ;
			C.addedge ( u , v , w ) ;
		}
		C.find_SCC ( n ) ;
		if ( C.scc_cnt == 1 ) {
			printf ( "0\n" ) ;
			continue ;
		}
		CLEAR ( cost , INF ) ;
		REP ( u , n )
			for ( int i = C.adj[u] ; ~i ; i = C.edge[i].n ) {
				int v = C.edge[i].v ;
				if ( C.scc[u] != C.scc[v] )
					cost[C.scc[v]] = min ( cost[C.scc[v]] , C.edge[i].w ) ;
			}
		int ans = 0 ;
		REPF ( i , 1 , C.scc_cnt )
			if ( cost[i] != INF )
				ans += cost[i] ;
		printf ( "%d\n" , ans ) ;
	}
}
	

int main () {
	work () ;
	return 0 ;
}