Description:

带权有向无环图上求最小花费不重复路径覆盖 $+$ 从各个出发点出发的费用。

$1\le N\le 800$ $1\le M \le 15000$

Solution:

对于一般的最小不重复路径覆盖，一般将每个点拆成两个点 $u$ 和 $u'$ 并连边 $(u,u')$ ，对于边 $(u,v)$ 连边 $(u,v')$ ，则 $最小不重复路径覆盖=N-拆点二分图最大匹配$ ，用网络流求解时，如果对于点 $u$ ， $u'$ 到汇点有流量，则说明它在不重复最小路径覆盖终点，如果边 $(u,v')$ 有流量，则说明这条边在原图中被选，如果原点到 $u$ 有流量，则说明它是路径起始点。

对于本题，边的处理和不带权的一样直接在拆点二分图中连费用为边权，容量为 $1$ 的边，直接跳 $u$ 时，说明 $u$ 是路径起点，原点到 $u$ 有流量，可以从原点连边到 $u'$ 费用为从这个点出发的费用，可以想到这个图一定是满流的，跑最小费用最大流即可。

Code:

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cstring>

using namespace std;

int n,m;

int s,t;

#define MAXN 810

#define MAXM 15010

#define INF 0x3f3f3f3f

struct edge

{

	int to,nxt,v,f;

}e[MAXN * 3 * 2 + MAXM * 2];

int edgenum = 0;

int lin[MAXN * 2] = {0};

void add(int a,int b,int c,int f)

{

	e[edgenum].to = b;e[edgenum].f = f;e[edgenum].nxt = lin[a];lin[a] = edgenum;e[edgenum].v = c;++edgenum;

	e[edgenum].to = a;e[edgenum].f = 0;e[edgenum].nxt = lin[b];lin[b] = edgenum;e[edgenum].v = -c;++edgenum;

	return;

}

int d[MAXN << 1];

bool v[MAXN << 1];

int pre[MAXN << 1],rate[MAXN << 1];

bool SPFA()

{

	memset(d,0x3f,sizeof(d));

	memset(v,false,sizeof(v));

	memset(rate,0x3f,sizeof(rate));

	memset(pre,0,sizeof(pre));

	queue<int> q;

	q.push(s);

	d[s] = 0;

	v[s] = true;

	while(!q.empty())

	{

		int k = q.front();q.pop();

		v[k] = false;

		for(int i = lin[k];i != -1;i = e[i].nxt)

		{

			if(d[e[i].to] > d[k] + e[i].v && e[i].f)

			{

				d[e[i].to] = d[k] + e[i].v;

				rate[e[i].to] = min(rate[k],e[i].f);

				pre[e[i].to] = i;

				if(!v[e[i].to])

				{

					v[e[i].to] = true;

					q.push(e[i].to);

				}

			}

		}

	}

	return (d[t] != INF);

}

long long flow()

{

	for(int i = t;i != s;i = e[pre[i] ^ 1].to)

	{

		e[pre[i]].f -= rate[t];

		e[pre[i] ^ 1].f += rate[t];

	}

	return rate[t] * d[t];

}

long long EK()

{

	long long ans = 0;

	while(SPFA()){ans += flow();}

	return ans;

}

int main()

{

	memset(lin,-1,sizeof(lin));

	scanf("%d%d",&n,&m);

	s = 2 * n + 1;t = s + 1;

	int a,b,c;

	for(int i = 1;i <= n;++i)

	{

		add(s,i,0,1);

		add(i + n,t,0,1);

		scanf("%d",&a);

		add(s,i + n,a,1);

	}

	for(int i = 1;i <= m;++i)

	{

		scanf("%d%d%d",&a,&b,&c);

		if(a > b)swap(a,b);

		add(a,b + n,c,1);

	}

	cout << EK() << endl;

	return 0;

}