上下界最小费用流
限制点访问量->拆点[i,i']
建图：
1.s->S [m,m] 0
2.S->i [0,inf] 0 i'->t [0,inf] 0
3.i‘-j [0,inf] x
4.i->i'[vi,vi] 0
然后就是上下界流的常见套路啦
根据“调整”原则 先是每个点点权为di=ini-outi 然后>0的连源点 <0的连汇点
然后循环流原始源点和汇点连边 由于这个题每条限制边都是卡紧的所以不需要再往回跑一次
接下来就是喜闻乐见的dinic解决啦
//Love and Freedom. #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<queue> #define inf 20021225 #define ll long long #define M 100010 #define N 210 using namespace std; struct edge{int to,lt,f,c,fm;}e[M<<1]; int in[N],cnt=1,S,t,ss,s,tt,from[N]; void add(int x,int y,int f,int c) { e[++cnt].to=y;e[cnt].fm=x;e[cnt].lt=in[x];e[cnt].f=f;e[cnt].c=c;in[x]=cnt; e[++cnt].to=x;e[cnt].fm=y;e[cnt].lt=in[y];e[cnt].f=0;e[cnt].c=-c;in[y]=cnt; } queue<int> q; int dis[N]; bool vis[N]; bool spfa() { while(!q.empty()) q.pop(); memset(from,0,sizeof(from)); memset(vis,0,sizeof(vis)); memset(dis,48,sizeof(dis)); dis[ss]=0; vis[ss]=1; q.push(ss); while(!q.empty()) { int x=q.front(); q.pop(); for(int i=in[x];i;i=e[i].lt) { int y=e[i].to; if(e[i].f&&dis[y]>dis[x]+e[i].c) { dis[y]=dis[x]+e[i].c; from[y]=i; if(!vis[y]) vis[y]=1,q.push(y); //if(y==tt) return 1; } } vis[x]=0; } return dis[tt]!=dis[0]; } int flow() { int f=inf; for(int i=tt;i!=ss;i=e[from[i]].fm) f=min(f,e[from[i]].f); for(int i=tt;i!=ss;i=e[from[i]].fm) e[from[i]].f-=f,e[from[i]^1].f+=f; return dis[tt]*f; } int d[N],n,v[N]; int ans; int main() { int m; int x; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%d",&v[i]); d[i]-=v[i]; d[i+n]+=v[i]; } S=n<<1|1; s=S+1; t=s+1; ss=t+1; tt=ss+1;// tt=ss+1; d[s]-=m; d[S]+=m; for(int i=1;i<n;i++) for(int j=i+1;j<=n;j++) { scanf("%d",&x); if(x==-1) continue; add(i+n,j,inf,x); } for(int i=1;i<=n;i++) add(S,i,inf,0),add(i+n,t,inf,0); for(int i=1;i<=S;i++) { if(d[i]>0) add(ss,i,d[i],0); if(d[i]<0) add(i,tt,-d[i],0); } add(t,s,inf,0); while(spfa()) ans+=flow(); printf("%d ",ans); return 0; }