这是道网络流的题

怎么样建图呢？我们从每个人 Ai 连边至其所对应的两个设备 Bi Bj，流量为+∞。

然后新建一对源汇，源连至每个人，流量为满足此人要求的利润；每个设备连至汇，流量为建造设备的代价。

然后求最大流flow，答案就是总利润减去flow。

为什么这种建模可以呢？我们可以通过残留网络来观察。

我们会发现，答案的大小和残留网络中从源点出发的边的可行流量之和一致。

而且每条增广路会经过一条流量是成本的边和流量是利润的边，而且两者的可行流量是同时减小的。这就相当于利润和成本相互抵销。

若存在着一种最大获利的方案，我们就可以通过此方案构造一个残留网络。

所以可以用这种方法求最大获利。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #define rep(i, l, r) for(int i=l; i<=r; i++) #define down(i, l, r) for(int i=l; i>=r; i--) #define clr(x, c) memset(x, c, sizeof(c))#define travel(x) for(edge *p=d[x]; p; p=p->n) if (p->z)#define maxv 56789#define maxm 434567#define inf 0x7fffffffusing namespace std;int read(){ int x=0; char ch=getchar(); while (!isdigit(ch)) ch=getchar(); while (isdigit(ch)) { x=x*10+ch-'0'; ch=getchar(); } return x;}struct edge{int y, z; edge *n, *pair;} e[maxm], *fir[maxv], *pt, *d[maxv];inline void Init() {pt=e, clr(fir, 0);}inline void Add(int x, int y, int z) {pt->y=y, pt->z=z, pt->n=fir[x]; fir[x]=pt++;}inline void AddE(int x, int y, int z) {Add(x, y, z); Add(y, x, 0); fir[x]->pair=fir[y], fir[y]->pair=fir[x];}int h[maxv], gap[maxv], S, T, V;int n, m, ans;int sap(int now, int flow){ if (now==T) return flow; int rec=0, ret; travel(now) if (h[p->y]+1==h[now]) { ret=sap(p->y, min(flow-rec, p->z)); p->z-=ret, p->pair->z+=ret, d[now]=p; if ((rec+=ret)==flow) return flow; } if (!(--gap[h[now]])) h[S]=V; ++gap[++h[now]]; d[now]=fir[now]; return rec;}inline int maxflow(){ clr(h, 0), clr(gap, 0); gap[0]=V; rep(i, 1, V) d[i]=fir[i]; int flow=0; while (h[S]
           
            n) ans+=p->z; ans-=maxflow(); printf("%d\n", ans); return 0;}