学步园

传送门：【HDU】4966 GGS-DDU

题目分析：最小树形图模板题。

瞎眼了瞎眼了！比赛的时候说上来先看G题（也就是这题的），然后。。。看了一会。。发现貌似好多单词看不懂的样子。。。就悄悄的不看了。。。T U T这模板题没看出来简直桑心。。不过既然赛后知道了还是做掉了。

首先对每个课程的每个等级，给他一个编号，为了方便就将所有课程的level 0的节点编号都设为0，同时让编号为0的点作为最小树形图的根。对于所有学科的所有等级，无条件向低等级建边，权值为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 CLR( a , x ) memset ( a , x , sizeof a )


const int MAXN = 505 ;
const int MAXE = 3005 ;
const int INF = 0x3f3f3f3f ;

struct Edge {
	int u , v , c ;
} ;

struct MST {
	Edge E[MAXE] ;
	int idx[MAXN] ;
	int vis[MAXN] ;
	int in[MAXN] ;
	int p[MAXN] ;
	int NV , NE ;
	int root ;
	
	void init () {
		NV = 0 ;
		NE = 0 ;
	}
	
	void addedge ( int u , int v , int c ) {
		E[NE].u = u ;
		E[NE].v = v ;
		E[NE].c = c ;
		++ NE ;
	}
	
	bool zhuliu ( int& res ) {
		res = 0 ;
		root = 0 ;
		while ( 1 ) {
			CLR ( in , INF ) ;
			REP ( i , 0 , NE ) {
				if ( E[i].u != E[i].v && in[E[i].v] > E[i].c ) {
					in[E[i].v] = E[i].c ;
					p[E[i].v] = E[i].u ;
				}
			}
			REP ( i , 0 , NV ) if ( i != root && in[i] == INF ) return 0 ;
			int cnt = 0 ; 
			in[root] = 0 ;
			CLR ( vis , -1 ) ;
			CLR ( idx , -1 ) ;
			REP ( i , 0 , NV ) {
				res += in[i] ;
				int v = i ;
				while ( vis[v] != i && idx[v] == -1 && v != root ) {
					vis[v] = i ;
					v = p[v] ;
				}
				if ( idx[v] == -1 && v != root ) {
					for ( int u = p[v] ; u != v ; u = p[u] ) idx[u] = cnt ;
					idx[v] = cnt ++ ;
				}
			}
			if ( !cnt ) break ;
			REP ( i , 0 , NV ) if ( idx[i] == -1 ) idx[i] = cnt ++ ;
			REP ( i , 0 , 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 -= in[v] ;
			}
			NV = cnt ;
			root = idx[root] ;
		}
		return 1 ;
	}
} T ;

int n , m ;
int num[MAXN] ;

void solve () {
	int u , v , Lu , Lv , c ;
	int res ;
	T.init () ;
	FOR ( i , 1 , n ) {
		scanf ( "%d" , &num[i] ) ;
		T.addedge ( num[i - 1] + 1 , 0 , 0 ) ;
		FOR ( j , 2 , num[i] ) T.addedge ( num[i - 1] + j , num[i - 1] + j - 1 , 0 ) ;
		num[i] += num[i - 1] ;
	}
	while ( m -- ) {
		scanf ( "%d%d%d%d%d" , &u , &Lu , &v , &Lv , &c ) ;
		u = !Lu ? 0 : num[u - 1] + Lu ;
		v = !Lv ? 0 : num[v - 1] + Lv ;
		T.addedge ( u , v , c ) ;
	}
	T.NV = num[n] + 1 ;
	if ( T.zhuliu ( res ) ) printf ( "%d\n" , res ) ;
	else printf ( "-1\n" ) ;
}

int main () {
	while ( ~scanf ( "%d%d" , &n , &m ) && ( n || m ) ) solve () ;
	return 0 ;
}