题目传送门: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; }
Thank you for every other excellent post. Where else may just anyone get that type of information in such an ideal manner of writing? I have a presentation subsequent week, and I am at the search for such info.
I think other website proprietors should take this web site as an model, very clean and excellent user genial style and design, let alone the content. You are an expert in this topic!