上下界最小费用流

限制点访问量->拆点[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
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define inf 20021225#define ll long long#define M 100010#define N 210using 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
           
             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
            
             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\n",ans); return 0;}