今天看到这题,这TM不是上星期BC的最后一题吗!!!!!!!!于是整个人都不好了,为什么我没有早点开始做BZOJ!!
于是用上星期在题解里看到的方法A了这题
这道题的思路是拆点
由于每一个人的选择 只会对后边来修车的人有影响 我们只要考虑这个人是倒数第几个人来修车的就好了
新建s,t。
将每个店员拆成n个点,其中第t个点代表倒数第t个修。比如 我是第一个人 是倒数第二个人来修车的,那么我这个选择就会让我自己和我后面的人总共等2*T[i][j]的时间,所以只要连一条容量为1的边,费用为倒数第k个 k*T[i][j]就好了。剩下来就是 s连到每个人容量1费用0,店员连到t,容量1,费用0就好了
巧妙的构图 考试的时候根本没想到。
#include <cstdio> #include <algorithm> using namespace std; typedef long long LL; const int N=100010,INF=1049999654; LL n,m,to[N*4],from[N*4],pre[N*4],now[N*2],cost[N*4],flow[N*4],tail=1,prev[N],dis[N],ans,inq[N],l,r,q[N],tmp; void add(int u,int v,int f,int co){ to[++tail]=v;from[tail]=u;flow[tail]=f;pre[tail]=now[u];now[u]=tail;cost[tail]=co; to[++tail]=u;from[tail]=v;flow[tail]=0;pre[tail]=now[v];now[v]=tail;cost[tail]=-co; } bool spfa(int s,int t){ for(int i=1;i<=n+m*n+2;i++) inq[i]=0,dis[i]=INF,prev[i]=0; l=r=0;dis[s]=0;q[++r]=s;inq[s]=1; while(l<r){ int x=q[(++l)%N];inq[x]=0; for(int i=now[x];i;i=pre[i]) if(flow[i]>0 && dis[to[i]]>dis[x]+cost[i]){ dis[to[i]]=dis[x]+cost[i];prev[to[i]]=i; if(!inq[to[i]]) q[(++r)%N]=to[i],inq[to[i]]=1; } } return dis[t]!=INF; } void zg(int s,int t){ LL f=INF; for(int i=t;i!=s;i=from[prev[i]]) f=min(f,flow[prev[i]]); for(int i=t;i!=s;i=from[prev[i]]) {flow[prev[i]]-=f;flow[prev[i]^1]+=f;ans+=f*cost[prev[i]];} } int main(){ scanf("%lld%lld",&m,&n); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++) { scanf("%lld",&tmp); for(int T=1;T<=n;T++) add(i,j*n+T,1,T*tmp); } } for(int i=n+1;i<=n+m*n;i++) add(i,n+m*n+2,1,0); for(int i=1;i<=n;i++) add(n+m*n+1,i,1,0); while(spfa(n+m*n+1,n+m*n+2)) zg(n+m*n+1,n+m*n+2); printf("%.2lf",(double)ans/n); }