怎么建设淘宝那样的网站,网页设计与制作课本,网站备案接入商,一流的医疗网站建设前言 n和m搞反调半天系列 正题
AC记录链接#xff1a; https://www.luogu.org/record/show?rid7949136 大意
又m个员工#xff0c;n辆车#xff0c;第j个员工修第i辆车需要T[i][j]的时间#xff0c;求分配让顾客平均等待时间最短。 解题思路
首先先假设一个修车工要修…前言 n和m搞反调半天系列 正题
AC记录链接 https://www.luogu.org/record/show?rid7949136 大意
又m个员工n辆车第j个员工修第i辆车需要T[i][j]的时间求分配让顾客平均等待时间最短。 解题思路
首先先假设一个修车工要修1−w1−w1 - w个人那么对等待时间就要加上
t[1]∗wt[2]∗(w−1)...t[w−1]∗2t[w]t[1]∗wt[2]∗(w−1)...t[w−1]∗2t[w]
t[1]*w+t[2]*(w-1)...+t[w-1]*2+t[w] 那我们可以将m个修车工拆成m*n个人表示第m个人第n次修车然后可以将顾客和修车工建立完全二分图权值为权值∗第几次权值∗第几次
权值*第几次之后将原点连车工人连汇点。代码
#includecstdio
#includecstring
#includealgorithm
using namespace std;
struct line{int to,w,c,next;
}a[100081];
int tot,n,m,s,t,f[5001],ls[5001],tail,answer;
int state[5001],x,y,w,c,ans,head,pre[5001];
bool v[5001];
void addl(int x,int y,int w,int c)
{a[tot].toy;a[tot].ww;a[tot].cc;a[tot].nextls[x];ls[x]tot;a[tot].tox;a[tot].w0;a[tot].c-c;a[tot].nextls[y];ls[y]tot;
}
bool spfa()
{for (int i1;it;i)f[i]2147483647;head0;tail1;v[s]true;state[1]s;f[s]0;while (head!tail){headhead%t1;int xstate[head];for (int qls[x];q;qa[q].next){int ya[q].to;if (a[q].wf[x]a[q].cf[y]){f[y]f[x]a[q].c;pre[y]q;if (!v[y]){v[y]true;tailtail%t1;state[tail]y;}}}v[x]false;}if (f[t]2147483647) return 0;else return 1;
}
void upway()
{int now;ansf[t];nowt;answer1;while (now!s){a[pre[now]].w--;a[pre[now]^1].w;nowa[pre[now]^1].to;}
}
int main()
{tot1;scanf(%d%d,m,n);sm*nn1;tm*nn2;for (int i1;in;i)for (int j1;jm;j){scanf(%d,x);for (int k1;kn;k)addl(n*mi,~-(j)*nk,1,k*x);//连接}for (int in*m1;in*mn;i) addl(s,i,1,0);//连原点for (int i1;in*m;i)addl(i,t,1,0);//连汇点while (spfa()){upway();}printf(%.2lf,1.0*ans/n);
}
