一组wa数据，正确输出 $842$，我输出 $877$。
```
13 22
58 8
14 7
23 69
18 4
17 75
6 10
34 6
46 7
9 5
26 63
27 55
10 16
60 23
11 5 198
12 13 76
1 8 623
6 10 405
7 13 842
2 10 331
5 6 112
5 12 922
8 4 39
13 5 176
11 2 955
6 2 657
9 2 326
5 8 899
5 3 398
11 4 560
3 8 20
12 2 990
8 9 776
6 10 638
2 9 844
7 2 551
```
by Nt_Tsumiki @ 2023-08-24 19:15:00
什么问题能难住 Nt 网络流大佬
by int_R @ 2023-08-24 19:20:59
```cpp
#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#define int long long
namespace Dinic {
struct Node { int to,nxt,dis; }e[1000005];
int tot=1,s,t,head[4005],vis[4005],cur[4005];
void add(int x,int y,int k) { e[++tot]=Node{y,head[x],k},head[x]=tot; }
bool bfs() {
std::memset(vis,0,sizeof vis);
std::queue<int> q; q.push(s); vis[s]=1;
while (!q.empty()) {
int x=q.front(); q.pop();
for (int i=head[x];i;i=e[i].nxt) {
int y=e[i].to; cur[x]=head[x];
if (e[i].dis and !vis[y]) {
vis[y]=vis[x]+1;
q.push(y);
}
}
}
return vis[t];
}
int dfs(int x,int flow) {
if (x==t) return flow;
int res=0;
for (int i=cur[x];i and flow;i=e[i].nxt) {
int y=e[i].to; cur[x]=i;
if (e[i].dis and vis[y]==vis[x]+1) {
int k=dfs(y,std::min(e[i].dis,flow));
e[i].dis-=k,e[i^1].dis+=k,res+=k,flow-=k;
}
}
return res;
}
}
using namespace std;
using namespace Dinic;
int n,m,cnt,sum;
int S[205],P[205],f[205][205];
bool check(int mid) {
tot=1;
memset(head,0,sizeof head);
for (int i=1;i<=n;i++) {
add(s,i,S[i]),add(i,s,0);
add(i+n,t,P[i]),add(t,i+n,0);
}
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
if (f[i][j]<=mid) add(i,j+n,1e18),add(j+n,i,0);
int res=0;
while (bfs()) res+=dfs(s,1e18);
return res==sum;
}
signed main() {
scanf("%lld%lld",&n,&m);
for (int i=1;i<=n;i++) {
scanf("%lld%lld",S+i,P+i);
sum+=S[i];
}
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
if (i!=j) f[i][j]=1e18;
for (int i=1,x,y,k;i<=m;i++) {
scanf("%lld%lld%lld",&x,&y,&k);
f[x][y]=min(f[x][y],k),f[y][x]=min(f[y][x],k);
}
for (int k=1;k<=n;k++)
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++) f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
int l=0,r=1e17,ans=0; t=2*n+1;
while (l<=r) {
int mid=(l+r>>1);
if (check(mid)) r=mid-1,ans=mid;
else l=mid+1;
}
printf("%lld\n",ans);
return 0;
}
```
by Estelle_N @ 2023-08-24 19:28:02
@[Nt_Tsumiki](/user/420129)
61行
by Estelle_N @ 2023-08-24 19:28:28
%%%
by Joy_Dream_Glory @ 2023-08-24 19:29:42
@[Estelle_N](/user/469356) 多谢多谢多谢
by Nt_Tsumiki @ 2023-08-24 19:31:44