之前几天想着补些算法的知识，学了一下最小树形图的朱刘算法，不是特别理解，备了份模板以备不时之需，想不到多校冷不丁的出了个最小树形图，没看出来只能表示对算法不太理解吧,用模板写了一下，然后就过了。－ －0
之前听到是最小树形图的时候觉得恍然大悟，非常裸，但是后来想想也不是特别裸，其实关键就是要想清楚要加回流的边，贴一份代码吧－ －0
#pragma warning(disable:4996)
#include<cstdio>
#include<set>
#include<cstring>
#include<iostream>
#include<stdlib.h>
#include<vector>
#include<map>
#include<algorithm>
#include<queue>
#include<cmath>
#include<functional>
#include<string>
using namespace std; #define maxn 550 int n, m;
int a[55]; struct Edge{
int u, v, w;
Edge(int ui, int vi, int wi) :u(ui), v(vi), w(wi){}
Edge(){}
}; vector<Edge> E;
vector<int> vid[55]; int in[maxn]; // minimum pre edge weight
int pre[maxn]; // pre vertex
int vis[maxn]; // vis array
int id[maxn]; // mark down the id
int nv; // nv is the number of vertex after shrinking int directed_mst(int root,int vertex_num)
{
int ret = 0; int nv = vertex_num;
while (1){
for (int i = 0; i < nv; ++i) in[i] = 1e9;
for (int i = 0; i < E.size(); ++i){
int u = E[i].u, v = E[i].v;
if (E[i].w < in[v] && u != v){
in[v] = E[i].w;
pre[v] = u;
}
}
for (int i = 0; i < nv; ++i){
if (i == root) continue;
if (in[i]>1e8) return -1;
}
int cnt = 0;
memset(id, -1, sizeof(id));
memset(vis, -1, sizeof(vis));
in[root] = 0; for (int i = 0; i < nv; ++i){
ret += in[i];
int v = i; while (vis[v] != i&&id[v] == -1 && v != root){
vis[v] = i;
v = pre[v];
}
// v!=root means we find a circle,id[v]==-1 guarantee that it's not shrinked.
if (v != root&&id[v] == -1){
for (int u = pre[v]; u != v; u = pre[u]){
id[u] = cnt;
}
id[v] = cnt++;
}
}
if (cnt == 0) break;
for (int i = 0; i < nv; ++i){
if (id[i] == -1) id[i] = cnt++;
}
// change the cost of edge for each (u,v,w)->(u,v,w-in[v])
for (int i = 0; i < E.size(); ++i){
int v = E[i].v;
E[i].u = id[E[i].u];
E[i].v = id[E[i].v];
if (E[i].u != E[i].v) E[i].w -= in[v];
}
// mark down the new root
root = id[root];
// mark down the new vertex number
nv = cnt;
}
return ret;
} int main()
{
while (cin >> n >> m){
if (n == 0 && m == 0) break;
int tot = 0;
for (int i = 1; i <= n; ++i) {
vid[i].clear();
scanf("%d", a + i);
for (int j = 0; j <= a[i]; ++j){
vid[i].push_back(++tot);
}
}
++tot;
E.clear();
for (int i = 1; i <= n; ++i){
for (int j = 0; j < vid[i].size(); ++j){
for (int k = j + 1; k < vid[i].size(); ++k){
E.push_back(Edge(vid[i][k], vid[i][j], 0));
}
}
}
int ci, l1, di, l2, wi;
for (int i = 0; i < m; ++i){
scanf("%d%d%d%d%d", &ci, &l1, &di, &l2, &wi);
E.push_back(Edge(vid[ci][l1], vid[di][l2], wi));
}
for (int i = 1; i <= n; ++i){
E.push_back(Edge(0, vid[i][0], 0));
}
int ans = directed_mst(0,tot);
printf("%d\n", ans);
}
return 0;
}