Description
西山风景区是苏州著名的*风景区，一到暑假，游客们都蜂拥而至。作为太湖风景区的精华，西山景区吸引人的地方主要在它的群岛风光、花果丛林和名胜古迹。
ginrat对这个地方向往已久，在暑假时忙里偷空出来玩了一次。一到景区，具有特殊观察力的他就开始观察，他发现，景区实际上是由太湖的一部分水域和露出水面的许多小岛构成的，小岛之间由许多桥（或者是堤坝，whatever）连接。ginrat是一个玩起来很有责任心的人，他非常想要逛完每个岛、每个桥，可bj提醒他，网页小组还等着他回去写文档，时间紧迫。根据导游的信息，这里共有\(n\)座岛，\(m\)座桥，ginrat开跑车经过每个桥或岛的时间很少很少，但他却要在每个桥或岛上面好好欣赏风景，这需要一定的时间。他不会重复在一个岛或桥上面欣赏风景。由于时间紧迫，他也降低了自己的目的。如果一座桥连接的两座岛他都在上面欣赏过了，这座桥上的风景他就认为他已经看过了，如果一座岛周围连接的所有的桥上的风景他都看过了，那么岛上的风景他也不想看了。
现在ginrat需要最少的时间来逛完景区，你能帮他吗？
Input Format
第一行两个整数\(n\)和\(m\)，分别表示岛屿的数量和桥的数量。
第二行有\(n\)个整数，分别表示n个岛屿ginrat观光所需要的时间。
第\(3~m+2\)行，每行三个整数，表示这座桥连接的两个岛的编号以及ginrat观光这座桥上风景所需要的时间。
Output Format
一个整数，ginrat观光所需最少时间。
Sample Input
2 1
2 2
1 2 1
Sample Output
1
Hint
\(n \le 500,m \le 1500\)
ginrat每次观光时间不超过\(100000\)
将边也看成一个点这个图便是二分图，然后就是一个最小割的经典题了，题解戳这里。
由于没有收益，我们便可以把收益看成\(0\)，然后连边即可。
首先将所有的边点染成黑色，其他的染成白色。
由源点向所有黑点连边，流量即为黑点的点权。再由所有白点向汇点连边，流量也为点权。最后若黑白点相连，由黑点向白点连流量为\(inf\)的边。跑最大流即可。
#include<iostream>
#include<cstring>
#include<queue>
#include<cstdio>
#include<cstdlib>
using namespace std;
#define inf (1<<30)
#define maxn (200010)
int N,M,cnt = 1,source,sink,side[maxn],next[maxn]; bool in[maxn];
int toit[maxn],cap[maxn],cur[maxn],nd[maxn],d[maxn],pre[maxn];
inline int read()
{
char ch; int f = 1,ret = 0;
do ch = getchar(); while (!(ch >= '0'&&ch <= '9')&&ch != '-');
if (ch == '-') f = -1,ch = getchar();
do ret = ret*10+ch-'0',ch = getchar(); while (ch >= '0'&&ch <= '9');
return ret*f;
}
inline void add(int a,int b,int c) { next[++cnt] = side[a]; side[a] = cnt; toit[cnt] = b; cap[cnt] = c; }
inline void ins(int a,int b,int c) { add(a,b,c); add(b,a,0); }
inline void bfs()
{
queue <int> team;
memcpy(cur,side,4*(sink+1));
team.push(sink); d[sink] = 1; in[sink] = true; d[sink] = 1;
while (!team.empty())
{
int now = team.front(); team.pop(); nd[d[now]]++;
for (int i = side[now];i;i = next[i])
if (cap[i^1]&&!in[toit[i]])
in[toit[i]] = true,d[toit[i]] = d[now]+1,team.push(toit[i]);
}
}
inline int isap()
{
bfs();
int res = 0,now = source,ca = inf;
while (d[source] <= sink)
{
if (now == sink)
{
while (now != source)
cap[pre[now]] -= ca,cap[pre[now]^1] += ca,now = toit[pre[now]^1];
res += ca; ca = inf;
}
bool flag = false;
for (int i = cur[now];i;i = next[i])
if (cap[i] && d[toit[i]] == d[now]-1)
{
cur[now] = pre[toit[i]] = i; ca = min(ca,cap[i]);
now = toit[i]; flag = true; break;
}
if (flag) continue;
int arg = sink;
if (!--nd[d[now]]) break;
for (int i = side[now];i;i = next[i])
if (cap[i]&&d[toit[i]] < arg) arg = d[toit[i]];
++nd[d[now] = arg+1]; cur[now] = side[now];
if (now != source) now = toit[pre[now]^1];
}
return res;
}
int main()
{
freopen("1313.in","r",stdin);
freopen("1313.out","w",stdout);
N = read(); M = read();
source = N+M+1; sink = N+M+2;
for (int i = 1;i <= N;++i) ins(source,i,read());
for (int i = 1;i <= M;++i)
{
int a = read(),b = read();
ins(N+i,sink,read());
ins(a,N+i,inf); ins(b,N+i,inf);
}
printf("%d",isap());
fclose(stdin); fclose(stdout);
return 0;
}