裸的费用流。 源点向每件物品连边，容量为C[i], 费用为0。 每个人向汇点连S[i]+1条边，每条边的容量为T[i][j] - T[i][j-1], 费用为W[i][j]。 物品和员工之间直接按所给的矩阵连容量为无穷大的边。 结果要用long long 。
#include <iostream> #include <queue> #include <string.h> #include <cstdio> #define MAX 2010 #define MAXE 600010 using namespace std; int maxData = 0x7fffffff; queue<int> dl; int head[MAX],cost[MAXE],net[MAXE],to[MAXE],cap[MAXE]; int cnt=1; int map[300][300]; void add(int x,int y,int c,int z) { to[++cnt]=y; cost[cnt]=z; cap[cnt]=c; net[cnt]=head[x]; head[x]=cnt; } int flow[MAX]; int pre[MAX];//前驱节点 int xb[MAX];//记录下标，便于修改容量 int n,m; int mflow=0;//最大流 long long mcost=0;//最小费用 int dis[MAX];//记录从源点到当前节点的最小的费用值，学过最小路的都懂 int f[MAX];//标记是否在队列中 int ti[MAX]; int BFS(int s,int t) { memset(dis,127,sizeof(dis));//赋初值最大值 memset(f,0,sizeof(f));//赋值为0 int INF=dis[0]; while(!dl.empty()) dl.pop(); for(int i=1;i<=n;i++) pre[i]=-1;//清空前驱节点 f[s]=1; dis[s]=0; pre[s]=0; flow[s]=maxData; dl.push(s); while(!dl.empty()) { int dd=dl.front(); dl.pop(); f[dd]=0; for(int i=head[dd];i;i=net[i]) { int tmp=to[i]; if(cap[i]>0&&dis[tmp]>dis[dd]+cost[i])//松弛操作 { dis[tmp]=dis[dd]+cost[i]; pre[tmp]=dd; xb[tmp]=i; flow[tmp]=min(flow[dd],cap[i]); if(!f[tmp]) f[tmp]=1,dl.push(tmp); } } } if(dis[t]>=INF) return 0;//成功找到了增广路 return 1; } void max_flow(int s,int t) { while(BFS(s,t)) { int k=t; while(k!=s) { cap[xb[k]]-=flow[t]; cap[xb[k]^1]+=flow[t]; k=pre[k]; } mflow+=flow[t]; mcost+=flow[t]*dis[t];//流量乘以最小单位流量的费用即为最小费用 } } int main() { int s,t; t=MAX-1; scanf("%d%d",&n,&m);//n为人,m为产品 s=0; int b=n+m; for(int i=1;i<=n;i++) add(s,i,maxData,0),add(i,s,0,0); for(int i=1;i<=m;i++) { int c; scanf("%d",&c); add(i+n,t,c,0); add(t,i+n,0,0); } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&map[i][j]); for(int i=1;i<=n;i++) { int ss; scanf("%d",&ss); for(int j=1;j<=ss;j++) scanf("%d",&ti[j]); ti[ss+1]=maxData; for(int j=1;j<=ss+1;j++) { int x1; scanf("%d",&x1); add(i,++b,ti[j]-ti[j-1],x1); add(b,i,maxData,-x1); for(int k=1;k<=m;k++) if(map[i][k]) add(b,k+n,maxData,0),add(k+n,b,0,0); } } max_flow(s,t); printf("%lld",mcost); return 0; }