最小树形图-hdu4966

https://vjudge.net/contest/311526#problem/G

大意:给定n(50)门属性，每门属性有a[i](500)个级别,同时有M(2000)门课程,参加j号课程需要c属性达到d

,这样就可以把你的e属性提升成f,同时花费g元钱,问要把属性升满要多少钱

分析:第一眼看到这题，有种网络流的感觉，于是欻欻欻开始写，还好隔壁xmk大佬的提示“你可以试试网络，

流，然后就开始自闭了，这题是最小树形图“，于是就开始写最小树形图，但最小树形图不是所有点都必须可到达吗

但这题可以使属性i达到a[i]，但不一定要经过a[i]-1呀，于是这题我开始迷糊了，感觉像是自己遇到了一个NP难问题，

后来没办法开始搜博客，看到别人的建图方法里面有a[i]-j  ->  a[i]-j-1这种操作，顿悟，好像也是，让低属性的点由

高属性的点到达，这样不仅解决了最小树形图需要把点流完的冲突，还解决了level5不能学习level4课程的问题，

太菜了

最后给个代码吧，可以给大家当模板

/////////////////////////////////////////Info/////////////////////////////////////////////////
//Problem:
//Date:
//Skill:
//Bug:
/////////////////////////////////////////Definations/////////////////////////////////////////////////
//循环控制
#define CLR(a) memset((a),0,sizeof(a))
#define F(i,a,b) for(int i=a;i<=int(b);++i)
#define F2(i,a,b) for(int i=a;i>=int(b);--i)
#define RE(i,n)  for(int i=0;i<int(n);i++)
#define RE2(i,n) for(int i=1;i<=int(n);i++)
//简化敲击
#define PII pair<int,int>
#define PDD pair<double,double>
#define PLL pair<long long ,long long>
#define PB push_back
#define MODY(n) (n%=mod)<0?n+=mod:n
#define MODED(n) ((n)<0?(n)%mod+mod:(n)%mod)
#define x first
#define y second
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const long long llinf = 0x3f3f3f3f3f3f3f3f;
////////////////////////////////////////Options//////////////////////////////////////////////////////
#define stdcpph
#define CPP_IO

#ifdef stdcpph
#include<bits/stdc++.h>
#else
#include<ctype.h>
#include<string.h>
#include<math.h>
#include<vector>
#include<map>
#include<algorithm>
#include<functional>
#ifdef CPP_IO
#include<iostream>
#include<iomanip>
#include<string>
#else
#include<stdio.h>
#endif
#endif
////////////////////////////////////////Basic Functions//////////////////////////////////////////////
template<typename INint> inline void IN(INint &x)
{
	x = 0; int f = 1; char c; cin.get(c);
	while (c<'0' || c>'9') { if (c == '-')f = -1; cin.get(c); }
	while (c >= '0'&&c <= '9') { x = x * 10 + c - '0'; cin.get(c); }
	x *= f;
}
template<typename INint> inline void OUT(INint x)
{
	if (x > 9)OUT(x / 10); cout.put(x % 10 + '0');
}
////////////////////////////////////////Added Functions//////////////////////////////////////////////
const int maxn = int(30000);
const int maxe = int(40000);
int N, M;
int a[maxn];
int c[maxn], L1[maxn], d[maxn], L2[maxn], money[maxn];

int cor[55][550],nid(0);
int eid(0);

struct Edge
{
	int f, t, v;
	bool operator<(Edge ri)const
	{
		return v < ri.v;
	}
}es[maxe], pre[maxn];
int root=1, cnt, id[maxn];
bool instk[maxn], vis[maxn];
void dfs(int u) {
	if (u == root) return;
	instk[u] = vis[u] = 1;
	if (!vis[pre[u].f])dfs(pre[u].f);
	else if (instk[pre[u].f])
	{
		id[u] = ++cnt;
		for (int j = pre[u].f; j != u; j = pre[j].f)id[j] = cnt;
	}
	instk[u] = 0;
	if (!id[u]) id[u] = ++cnt;
}
//tn个顶点,tm条边,在es和pre中都存储为[1,n]
int solve(int tn, int tm,int setroot)
{
	root = setroot;
	int ans = 0;
	while (1) {
		for (int i = 1; i <= tn; ++i) pre[i].v = inf;
		for (int i = 1; i <= tm; ++i)pre[es[i].t] = min(pre[es[i].t], es[i]);
		memset(id + 1, 0, tn << 2), memset(vis + 1, 0, tn), id[root] = cnt = 1;
		for (int i = 1; i <= tn; ++i) if (i != root) {
			if (pre[i].v == inf)return -1; else ans += pre[i].v;
			if (!vis[i]) dfs(i);
		}
		if (cnt == tn) break;
		int mm = 0;
		for (int i = 1; i <= tm; ++i)if (id[es[i].f] != id[es[i].t])
			es[++mm] = { id[es[i].f],id[es[i].t],es[i].v - pre[es[i].t].v };
		tm = mm, tn = cnt, root = id[root];
	}
	return ans;
}
////////////////////////////////////////////Code/////////////////////////////////////////////////////
int main()
{
	//freopen("C:\\Users\\VULCAN\\Desktop\\data.in", "r", stdin);
	int T(1), cas(0);
#ifdef CPP_IO// CPP_IO
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	//cin >> T;
#else
	//IN(T);
#endif 
	/////////////////////////////////////////////////////////////////////////////////////////////////
	while (++cas, T--,cin>>N>>M,N||M)
	{
		nid = eid = 0;
		F(i, 1, N)cin >> a[i];
		F(i, 1, M)
		{
			cin >> c[i] >> L1[i] >> d[i] >> L2[i]>>money[i];
		}
		F(i, 1, N)cor[i][0] = nid = 1;
		F(i, 1, N)
		{
			F(j, 1, a[i])
			{
				cor[i][j] = ++nid;
			}
		}
		F(i, 1, N)
		{
			F(j, 1, a[i])
			{
				es[++eid] = { cor[i][j],cor[i][j - 1],0 };
			}
		}
		F(i, 1, M)
		{
			es[++eid] = { cor[c[i]][L1[i]],cor[d[i]][L2[i]],money[i] };
		}
		int ans = solve(nid, eid,1);
		cout << ans << endl;

	}
	///////////////////////////////////////////////////////////////////////////////////////////////////
	return 0;
}
//What to Debug
/*
-1.最好把全部warning都X掉,否则:https://vjudge.net/solution/19887176
0.看看自己是否有可能需要快读，禁endl
1.数组越界，爆int,浮点精度(查看精度是否达到题目要求,看有没有浮点数比较:eps)，取模操作，初始化数组，边缘数据,输出格式(cas)
2.通读代码，代码无逻辑错误
3.读题，找到题意理解失误或算法错误
4.放弃
*/