构图思路:

1. 源点S与顶点v连边，容量为A

2. 顶点v与汇点T连边，容量为B

3. 边(a,b,c),则顶点a与顶点b连双向边，容量为c

则最小花费为该图最小割即最大流。

 

若两个作业分别在不同机器运行，则之间若有边，则必定是满流，否则必定还有增广路。

#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;const int inf = 0x3f3f3f3f;const int MAXN = (int)2e5+10;int n, m;int S, T, N;int head[MAXN], idx;struct Edge{    int v, f, nxt;}edge[MAXN<<3];void AddEdge(int u,int v,int f){    edge[idx].v = v, edge[idx].f = f;    edge[idx].nxt = head[u], head[u] = idx++;    edge[idx].v = u, edge[idx].f = 0;    edge[idx].nxt = head[v], head[v] = idx++;}int vh[MAXN], h[MAXN];int dfs(int u,int flow){    if(u == T) return flow;    int tmp = h[u]+1, sum = flow;    for(int i = head[u]; ~i; i = edge[i].nxt ){        if( edge[i].f && (h[edge[i].v]+1 == h[u]) ){            int p = dfs( edge[i].v, min(sum,edge[i].f));            edge[i].f -= p, edge[i^1].f += p, sum -= p;            if( sum == 0 || h[S] == N ) return flow - sum;        }    }    for(int i = head[u]; ~i; i = edge[i].nxt )        if( edge[i].f ) tmp = min( tmp, h[ edge[i].v ] );    if( --vh[ h[u] ] == 0 ) h[S] = N;    else ++vh[ h[u]=tmp+1 ];    return flow-sum;}int sap(){    int maxflow = 0;    memset(h,0,sizeof(h));    memset(vh,0,sizeof(vh));    vh[0] = N;    while( h[S]