企业网站建设的开放方式一般有,如何做网络营销推广55,合肥网站seo,竞价推广哪里开户/*一开始以为是个贪心 发现自己太naive了将每个技术工人拆成n个点#xff0c;一共拆n*m个#xff0c;第i个表示倒数第i次修车。
让每辆车向拆出来的点连边#xff0c;费用为tmp[i][j]*k#xff0c;i是技工#xff0c;j是车#xff0c;k是拆出来的第几个点#xff0c;
这… /*一开始以为是个贪心 发现自己太naive了将每个技术工人拆成n个点一共拆n*m个第i个表示倒数第i次修车。
让每辆车向拆出来的点连边费用为tmp[i][j]*ki是技工j是车k是拆出来的第几个点
这样设置费用的原因是j是i倒数第k个修的那么i修的后k个车都要等倒数第k个车。
然后跑最小费用最大流就可以了
*/#includeiostream
#includecstdio
#includecstring
#includecmath
#includealgorithm
#includequeue
using namespace std;inline int read()
{char cgetchar();int num0;for(;!isdigit(c);cgetchar());for(;isdigit(c);cgetchar())numnum*10c-0;return num;
}const int N65;
const int M2e55;int m,n,S,T;
int tim[N][N];
long long ans;int head[M],num_edge;
struct Edge
{int v,nxt,flow,cost;
}edge[M];inline void add_edge(int u,int v,int flow,int cost)
{edge[num_edge].vv;edge[num_edge].flowflow;edge[num_edge].costcost;edge[num_edge].nxthead[u];head[u]num_edge;edge[num_edge].vu;edge[num_edge].flow0;edge[num_edge].cost-cost;edge[num_edge].nxthead[v];head[v]num_edge;
}int dis[M];
queueint que;
bool inque[M];
bool spfa()
{memset(dis,0x3f,sizeof(dis));que.push(S),dis[S]0;int now;while(!que.empty()){nowque.front(),que.pop();for(int ihead[now],v;i;iedge[i].nxt){if(edge[i].flow0)continue;vedge[i].v;if(dis[v]dis[now]edge[i].cost){dis[v]dis[now]edge[i].cost;if(!inque[v]){que.push(v);inque[v]1;}}}inque[now]0;}return dis[T]!0x3f3f3f3f;
}int vis[M],visf;
int dfs(int u,int flow)
{if(uT||!flow)return flow;int outflow0;vis[u]visf;for(int ihead[u],v,tmp;i;iedge[i].nxt){if(!edge[i].flow)continue;vedge[i].v;if(vis[v]!visfdis[v]dis[u]edge[i].cost){tmpdfs(v,min(flow,edge[i].flow));if(!tmp)continue;ans1ll*tmp*edge[i].cost;edge[i].flow-tmp;edge[i^1].flowtmp;flow-tmp;outflowtmp;if(!flow){vis[u]0;return outflow;}}}vis[u]0;dis[u]0x7fffffff;return outflow;
}int main()
{num_edge1;mread(),nread();Tnn*m1;for(int i1;in;i)for(int j1;jm;j)tim[j][i]read();for(int i1;in;i)add_edge(S,i,1,0);for(int i1,p;im;i){for(int j1;jn;j){pi*nj;add_edge(p,T,1,0);for(int c1;cn;c)add_edge(c,p,1,tim[i][c]*j);}}while(spfa()){visf;dfs(S,0x7fffffff);}printf(%.2lf,1.0*ans/n);return 0;
} 转载于:https://www.cnblogs.com/lovewhy/p/9633745.html
