题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1070
这个题目，最开始想到的肯定是完全按照时间来拆点
这样想起来很直观，然而估计会wa？因为一个车是一个整体，不能中间暂停
于是只能考虑以车为单位来拆点。然后计算贡献。
这题真的是好妙啊！
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
int m,n,s,t,vout;// m means the worker n means the car
int str[70][20];
struct edge{
int from,to,cap,cost,flow;
edge(int from,int to,int cap,int flow,int cost):from(from),to(to),cap(cap),cost(cost),flow(flow){}
edge(){}
};
vector<edge> edges;
vector<int> node[700];//1-60 is the car 71-INF is the worker
void addedge(int from,int to,int cap,int flow,int cost){
edges.push_back( edge(from,to,cap,0,cost) );
edges.push_back( edge(to,from,0,0,-cost) );
int asd=edges.size();
node[from].push_back(asd-2);
node[to].push_back(asd-1);
}
void init(){
cin>>m>>n;
for (int i=1,hc;i<=n;i++){//car
for (int j=1;j<=m;j++){//worker
scanf("%d",&hc);//hc=-hc;
for (int k=1,hj;k<=n;k++){
hj=n+(j-1)*n+k;
addedge(i,hj,1,0,hc*k);
}
}
}
s=0;t=n+n*m+1;
for (int i=1;i<=n;i++) addedge(0,i,1,0,0);
for (int i=n+1;i<t;i++) addedge(i,t,1,0,0);
}
int d[1000],a[1000],p[1000],inq[1000];
bool bellman_ford(){
queue<int> Q;Q.push(s);
memset(inq,0,sizeof (inq));
for (int i=1;i<=t;i++) d[i]=0x7ffffeee;
a[s]=0x7ffffeee;d[s]=0;p[s]=0;inq[s]=1;
while(!Q.empty()) {
int now=Q.front();Q.pop();inq[now]=0;
int len=node[now].size();
for (int i=0;i<len;i++){
edge& e=edges[node[now][i]];
if (e.cap>e.flow && d[e.to]>d[now]+e.cost){
d[e.to]=d[now]+e.cost;
p[e.to]=node[now][i];
a[e.to]=min(a[now],e.cap-e.flow);
if (!inq[e.to]) inq[e.to]=1,Q.push(e.to);
}
}
}
if (d[t]==0x7ffffeee) return false;
vout+=d[t]*a[t];
for (int i=t;i!=s;i=edges[p[i]].from){
edges[p[i]].flow+=a[t];
edges[p[i]^1].flow-=a[t];
}
return true;
}
int main(){
init();
while (bellman_ford()) {}
printf("%.2f",(double)vout/(double)n);
return 0;
}
![FS~3Z]@~(4B0{S~)AKZ2G88](http://oi.cyo.ng/wp-content/uploads/2016/08/FS3Z@4B0SAKZ2G88.jpg)
![HP@{Q%Y1HMU{H9M4V]{N6)D](http://oi.cyo.ng/wp-content/uploads/2016/08/HP@QY1HMUH9M4VN6D.jpg)
