题意: 给了M个机器，N个糖果要被生产,每个糖果有一个Si和Ti的时间，只能在Si或者在Si<=t<Ti的时间开始生产 每个机器进行转化生产产品的时候都会产生一个代价，然后求最小的代价生产了者N个糖果。
我们可以知道 每台机器在开始的时候需要时间和钱去启动，一旦启动后 就剩下就是在 糖果之间的转移了
先建一个S 和一个T，一个糖果拆成3个糖果,S->M—>C1->C3, S->C2->C3->T 因为时间是一个天然的有序 他们之间的转化形成了一个 DAG 图，所以后面那个直接构造一个类似二分图
#include <iostream> #include <algorithm> #include <string.h> #include <vector> #include <cstdio> #include <queue> using namespace std; const int maxn=105; const int INF=2147483647; const int MAXN=805; int N,M,K; int S[maxn],T[maxn]; int C[maxn][maxn],D[maxn][maxn],E[maxn][maxn],F[maxn][maxn]; void read() { for(int i=1; i<=N; i++) scanf("%d%d",&S[i],&T[i]); for(int i=1; i<=N; i++) for(int j=1; j<=M; j++) scanf("%d",&C[i][j]); for(int i=1; i<=N; i++) for(int j=1; j<=M; j++) scanf("%d",&D[i][j]); for(int i=1; i<=N; i++) for(int j=1; j<=N; j++) scanf("%d",&E[i][j]); for(int i=1; i<=N; i++) for(int j=1; j<=N; j++) scanf("%d",&F[i][j]); } struct Edge { int from,to,cap,flow,cost; Edge(int cfrom=0, int cto=0, int ccap=0, int cflow=0, int ccost=0) { from=cfrom; to=cto; cap=ccap; flow=cflow; cost=ccost; } }; struct McMF { int n,m,s,t; vector<Edge>edges; vector<int>G[MAXN]; int inq[MAXN]; int d[MAXN]; int p[MAXN]; int a[MAXN]; void init(int n) { this->n=n; m=0; for(int i=0; i<=n; i++)G[i].clear(); edges.clear(); } void AddEdge(int from, int to ,int cap, int cost) { edges.push_back(Edge(from,to,cap,0,cost)); edges.push_back(Edge(to,from,0,0,-cost)); m+=2; G[from].push_back(m-2); G[to].push_back(m-1); } bool BellManFord(int s, int t,int &flow,int &cost) { for(int i=0; i<=n; i++)d[i]=INF; memset(inq,0,sizeof(inq)); d[s]=0; inq[s]=1; p[s]=0;a[s]=INF; queue<int>Q; Q.push(s); while(!Q.empty()) { int u=Q.front(); Q.pop(); inq[u]=0; for(int i=0; i<G[u].size(); i++) { Edge &e=edges[G[u][i]]; if(e.cap>e.flow && d[e.to]>d[u]+e.cost) { d[e.to]=d[u]+e.cost; p[e.to]=G[u][i]; a[e.to]=min(a[u],e.cap-e.flow); if(!inq[e.to]){ Q.push(e.to); inq[e.to]=1; } } } } if(d[t]==INF)return false; flow+=a[t]; cost+=d[t]; int u=t; while(u!=s){ edges[p[u]].flow+=a[t]; edges[p[u]^1].flow-=a[t]; u=edges[p[u]].from; } return true; } void Mincost(int s, int t,int &flow,int &cost) { while(BellManFord(s,t,flow,cost)); } }mcmf; void buildedg() { int st=0,ed=N*3+M+1; for(int i=1; i<=M; i++) { mcmf.AddEdge(st,i,1,0); for(int j=1; j<=N; j++) { if(C[j][i]<T[j]) { if(C[j][i]<=S[j]) mcmf.AddEdge(i,M+j,1,D[j][i]); else mcmf.AddEdge(i,M+j,1,K*(C[j][i]-S[j])+D[j][i]); } } } for(int i=1; i<=N; i++) for(int j=1; j<=N; j++) { if(i==j || T[i]+E[i][j]>=T[j])continue; if(T[i]+E[i][j]<=S[j]) mcmf.AddEdge(M+N+i,M+N*2+j,1,F[i][j]); else mcmf.AddEdge(M+N+i,M+N*2+j,1,F[i][j]+K*(T[i]+E[i][j]-S[j]) ); } for(int i=1; i<=N; i++) { mcmf.AddEdge(st,M+N+i,1,0); mcmf.AddEdge(M+i,M+N*2+i,1,0); mcmf.AddEdge(M+N*2+i,ed,1,0); } } int main() { while(scanf("%d%d%d",&N,&M,&K)==3) { if(N==0&&M==0&&K==0)break; read(); mcmf.init(N*3+M+2); buildedg(); int flow=0,cost=0; mcmf.Mincost(0,M+N*3+1,flow,cost); if(flow<N)puts("-1"); else printf("%d\n",cost); } return 0; }
原文：http://www.cnblogs.com/Opaser/p/4949891.html
