本文共 2027 字，大约阅读时间需要 6 分钟。
#include #include #include #include #include #include #include #include #include #include using namespace std; #define MM(a) memset(a,0,sizeof(a)) typedef long long ll; typedef unsigned long long ULL; const int mod = 1000000007; const double eps = 1e-10; const int inf = 0x3f3f3f3f; const int big=50000; int max(int a,int b) {return a>b?a:b;}; int min(int a,int b) {return a G[3000]; int w[55][3000],dist[3000],inq[3000],prel[3000],prev[3000]; int n,m,x,y,c; void add_edge(int u,int v,int cap,int cost) { G[u].push_back(edge{v,cap,cost,G[v].size()}); G[v].push_back(edge{u,0,-cost,G[u].size()-1}); } int mcost(int s,int t,int f) { int mincost=0; while(f>0) { memset(dist,inf,sizeof(dist)); memset(inq,0,sizeof(inq)); dist[s]=0; queue q; q.push(s); inq[s]=1; while(!q.empty()) { int u=q.front(); q.pop(); inq[u]=0; //printf("///\n"); //cout< < 0&&dist[e.to]>dist[u]+e.cost) { dist[e.to]=dist[u]+e.cost; prev[e.to]=u; prel[e.to]=j; if(!inq[e.to]) { q.push(e.to); inq[e.to]=1; } } } } int minn=inf; for(int i=t;i>s;) { int f=prev[i]; int j=prel[i]; minn=min(minn,G[f][j].cap); i=prev[i]; } for(int i=t;i>s;) { int f=prev[i]; int j=prel[i]; G[f][j].cap-=minn; G[i][G[f][j].rev].cap+=minn; mincost+=G[f][j].cost; i=prev[i]; } f-=minn; } // cout< <<"hhahhaha"< >cas; while(cas--) { scanf("%d %d",&n,&m); int s=0,t=n+n*m+1; memset(w,0,sizeof(w)); for(int i=s;i<=t;i++) G[i].clear(); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&w[i][j]); for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) for(int k=1;k<=n;k++) add_edge(k,i*n+j,1,w[k][i]*j); for(int i=1;i<=n;i++) add_edge(s,i,1,0); for(int j=n+1;j<=n+n*m;j++) add_edge(j,t,1,0); printf("%.6f\n",((double)mcost(s,t,n))/n); } return 0; }
分析：这道题目最难的地方就在于构图，刚开始想的是构建一个时间和工厂的二元组，但是后来
发现是行不通的，因为加工玩具的时间的又依赖性的； 但是我们发现一个工厂加工倒数第k个玩具时
加工这个玩具的总的耗费时间是k*（该工厂单独加工这个玩具的时间），由此相出根据加工次序构图，
然后最小费用流求解即可。
转载地址：http://ytgsi.baihongyu.com/