【[SCOI2007]修车】

只能做网络流度日了

当然是要对每个修车的人拆点，把每个人拆成\(n\)个点用于接收不同时刻的车

每个车\(i\)向每个时刻\(k\)的人\(j\)连边，边权为\(t[i][j]*k\)这样就是这样修的等待时间了

代码

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#include<queue>

#define re register

#define maxn 545

#define LL long long

#define inf 999999999

#define max(a,b) ((a)>(b)?(a):(b))

#define min(a,b) ((a)<(b)?(a):(b))

inline int read()

{

	char c=getchar();int x=0;

	while(c<'0'||c>'9') c=getchar();

	while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;

}

struct E{int v,nxt,w,f;}e[maxn*maxn*2];

int S,T,head[maxn],d[maxn],vis[maxn];

int a[maxn][maxn];

int id[10][105];

int n,m,num=1,ans;

inline void add(int x,int y,int ca,int z) {e[++num].v=y;e[num].nxt=head[x];head[x]=num;e[num].w=z;e[num].f=ca;}

inline void C(int x,int y,int ca,int z) {add(x,y,ca,z),add(y,x,0,-1*z);}

std::queue<int> q;

inline int SPFA()

{

	for(re int i=S;i<=T;i++) d[i]=inf,vis[i]=0;

	q.push(T),d[T]=0;

	while(!q.empty())

	{

		int k=q.front();q.pop();vis[k]=0;

		for(re int i=head[k];i;i=e[i].nxt)

		if(e[i^1].f&&d[e[i].v]>d[k]+e[i^1].w)

		{

			d[e[i].v]=d[k]+e[i^1].w;

			if(!vis[e[i].v]) q.push(e[i].v),vis[e[i].v]=0;

		}

	}

	return d[S]<inf;

}

int dfs(int x,int now)

{

	if(x==T||!now) return now;

	int flow=0,ff;vis[x]=1;

	for(re int i=head[x];i;i=e[i].nxt)

	if(!vis[e[i].v]&&e[i].f&&d[x]+e[i^1].w==d[e[i].v])

	{

		ff=dfs(e[i].v,min(now,e[i].f));

		if(ff<=0) continue;

		e[i].f-=ff,e[i^1].f+=ff;

		now-=ff,flow+=ff;

		if(!now) break;

	}

	return flow;

}

int main()

{

	m=read(),n=read();

	for(re int i=1;i<=n;i++)

		for(re int j=1;j<=m;j++) a[i][j]=read();

	T=n;

	for(re int i=1;i<=m;i++)

		for(re int j=1;j<=n;j++)

			id[i][j]=++T;

	++T;

	for(re int i=1;i<=n;i++) C(S,i,1,0);

	for(re int i=1;i<=m;i++)

		for(re int j=1;j<=n;j++)

			C(id[i][j],T,1,0);

	for(re int i=1;i<=n;i++)

		for(re int j=1;j<=m;j++)

			for(re int k=1;k<=n;k++)

				C(i,id[j][k],1,k*a[i][j]);

	while(SPFA())

	{

		vis[T]=1;

		while(vis[T])

		{

			for(re int i=S;i<=T;i++) vis[i]=0;

			ans+=dfs(S,inf)*d[S];

		}

	}

	printf("%.2lf\n",(double)ans/double(n));

	return 0;

}

巴特西

【[SCOI2007]修车】

最新文章

热门文章