这题建图自己想了半天搞不懂，然后看了一下别人的建图。。。一脸茫然。。

最后去看了下胡波涛的《最小割模型在信息学竞赛的应用》里面详细的讲解了将最大获利问题转换为最小割模型的过程。

建图：

源点与人连边，容量为获利。站点与汇点连边，容量为耗资。然后是相应的人与其需求的站点连边，容量为无穷。

这样建图就完成了，然后就是找最小割，即割边上的值便为不能获取的利润值，用总值减去得出最大利润。

 

#include
    
     #include
     
      #include
      
       #define MAXN 60000              //点的个数#define INF 1e8#define min(a,b) (a
       
        b?a:b)using namespace std;struct edge{    int u,v,w,next;}E[400050];                     //边的个数  记得乘2int head[MAXN],ecnt;int gap[MAXN],cur[MAXN],pre[MAXN],dis[MAXN];int l,r,mid;int N,M,scr,sink,vn,num;void Insert(int u,int v,int w){    E[ecnt].u=u;    E[ecnt].v=v;    E[ecnt].w=w;    E[ecnt].next=head[u];    head[u]=ecnt++;    E[ecnt].u=v;    E[ecnt].v=u;    E[ecnt].w=0;    E[ecnt].next=head[v];    head[v]=ecnt++;}int Sap(int s,int t,int n)//核心代码(模版){    int ans=0,aug=INF;//aug表示增广路的流量    int i,v,u=pre[s]=s;    for(i=0;i<=n;i++)    {        cur[i]=head[i];        dis[i]=gap[i]=0;    }    gap[s]=n;    bool flag;    while(dis[s]
        
         0&&dis[u]==dis[v]+1)            {                flag=true;//找到容许边                aug=min(aug,E[j].w);                pre[v]=u;                u=v;                if(u==t)                {                    ans+=aug;                    while(u!=s)                    {                        u=pre[u];                        E[cur[u]].w-=aug;                        E[cur[u]^1].w+=aug;//注意                    }                    aug=INF;                }                break;//找到一条就退出            }        }        if(flag) continue;        int mindis=n;        for(i=head[u];i!=-1;i=E[i].next)        {            v=E[i].v;            if(E[i].w>0&&dis[v]