题解：
似乎是放在费用流里的
然而是有上下界的网络流QAQ
代码：
#include<bits/stdc++.h> using namespace std; const int N=40005; int n,m,x,mincost,s,t,S,ss,tt,tot,fi[N],ne[N],zz[N],sl[N],c[N]; int dis[N],last[N],d[N],vis[N]; queue <int> q; void jb(int x,int y,int cap,int z) { ne[++tot]=fi[x]; fi[x]=tot; zz[tot]=y; sl[tot]=cap; c[tot]=z; ne[++tot]=fi[y]; fi[y]=tot; zz[tot]=x; sl[tot]=0; c[tot]=-z; } int addflow(int s,int t) { int now=t,ans=1e9; while (now!=s) { ans=min(ans,sl[last[now]]); now=zz[last[now]^1]; } now=t; while (now!=s) { sl[last[now]]-=ans; sl[last[now]^1]+=ans; now=zz[last[now]^1]; } return ans; } int spfa(int s,int t) { memset(dis,127,sizeof(dis)); dis[s]=0; memset(vis,0,sizeof(vis)); vis[s]=1; while (!q.empty())q.pop(); q.push(s); while (!q.empty()) { int now=q.front();q.pop(); vis[now]=0; for (int i=fi[now];i!=-1;i=ne[i]) if (dis[zz[i]]>dis[now]+c[i]&&sl[i]) { dis[zz[i]]=dis[now]+c[i]; last[zz[i]]=i; if (!vis[zz[i]]) { vis[zz[i]]=1; q.push(zz[i]); } } } if (dis[t]>1e9) return 0; int flow=addflow(s,t); mincost+=flow*dis[t]; return 1; } int main() { tot=-1; memset(fi,-1,sizeof(fi)); scanf("%d%d",&n,&m); S=n+n+1,s=S+1,t=s+1;ss=t+1,tt=ss+1; d[s]-=m,d[S]+=m; for (int i=1;i<=n;i++) { scanf("%d",&x); jb(S,i,1e9,0); jb(n+i,t,1e9,0); d[i]-=x,d[n+i]+=x; } for (int i=1;i<n;i++) for (int j=i+1;j<=n;j++) { scanf("%d",&x); if (x==-1) continue; jb(n+i,j,1e9,x); } for (int i=1;i<=t;i++) { if (d[i]>0)jb(ss,i,d[i],0); if (d[i]<0)jb(i,tt,-d[i],0); } jb(t,s,1e9,0); while (spfa(ss,tt)); printf("%d ",mincost); }