LG2053/BZOJ1070 「SCOI2007」修车费用流

问题描述

LG2053

题解

将\(m\)个修理工拆为\(n \times m\)个，将修理工和车辆看做二分图，连出一个完全二分图。

边流量为\(1\)，费用为时间，费用流即可。

\(\mathrm{Code}\)

#include<bits/stdc++.h>

using namespace std;

template <typename Tp>

void read(Tp &x){

	x=0;char ch=1;int fh;

	while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();

	if(ch=='-'){

		fh=-1;ch=getchar();

	}

	else fh=1;

	while(ch>='0'&&ch<='9'){

		x=(x<<1)+(x<<3)+ch-'0';

		ch=getchar();

	}

	x*=fh;

}

const int maxn=63;

const int maxm=13;

const int INF=0x3f3f3f3f; 

int n,m;

int a[maxn][maxm];

int Head[100000],Next[1000000],to[1000000],tot=1,w[1000000],co[1000000];

int S,T;

void add(int a,int b,int c,int d){

	to[++tot]=b,Next[tot]=Head[a],Head[a]=tot,w[tot]=c,co[tot]=d;

}

bool vis[100000];

int now[1000000],pre[1000000];

int dis[100000];

int ans,flow;

bool spfa() {

    memset(vis,0,sizeof(vis));memset(dis,0x3f,sizeof(dis));

    queue<int>q;q.push(S);vis[S]=1;dis[S]=0;now[S]=INF;

    while(!q.empty()){

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

        for (int i=Head[x];i;i=Next[i]){

            int y=to[i],z=w[i],ww=co[i];

            if (!z||dis[y]<=dis[x]+ww) continue;

            dis[y]=dis[x]+ww;

            now[y]=min(now[x],z);

            pre[y]=i;

            if(!vis[y]){

                q.push(y);

                vis[y] = 1;

            }

        }

    }

    return dis[T]!=INF;

}

void upd(){

	flow+=now[T],ans+=dis[T]*now[T];

	int p=T;

	while(p!=S){

		int k=pre[p];

		w[k]-=now[T],w[k xor 1]+=now[T];

		p=to[k xor 1];

	}

}

int main(){

	read(m);read(n);tot=1;

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

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

			read(a[i][j]);

		}

	}

	S=n*(m+1)+1,T=S+1;

	for(int i=1;i<=n*m;i++){

		add(S,i,1,0);add(i,S,0,0);

	}

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

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

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

				int p=(i-1)*n+k;

				add(p,j+n*m,1,a[j][i]*k);add(j+n*m,p,0,-a[j][i]*k);

			}

		}

	}

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

		add(n*m+i,T,1,0);add(T,n*m+i,0,0);

	}

	while(spfa())

		upd();

	double ret=(double)ans/(double)n*1.0;

	cout<<fixed<<setprecision(2)<<ret<<endl;

	return 0;

}

巴特西

LG2053/BZOJ1070 「SCOI2007」修车费用流

问题描述

题解

\(\mathrm{Code}\)

最新文章

热门文章

巴特西

LG2053/BZOJ1070 「SCOI2007」修车 费用流

问题描述

题解

\(\mathrm{Code}\)

最新文章

热门文章

LG2053/BZOJ1070 「SCOI2007」修车费用流