BZOJ 1070 [SCOI2007]修车

starli posted @ 2016年2月03日 19:24 in 网络流 , 191 阅读

今天看到这题,这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);
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter