【BZOJ 1070】[SCOI2007] 修车

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1070

这个题目,最开始想到的肯定是完全按照时间来拆点
这样想起来很直观,然而估计会wa?因为一个车是一个整体,不能中间暂停
于是只能考虑以车为单位来拆点。然后计算贡献。
这题真的是好妙啊!

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;

int m,n,s,t,vout;// m means the worker     n means the car
int str[70][20];
struct edge{
	int from,to,cap,cost,flow;
	edge(int from,int to,int cap,int flow,int cost):from(from),to(to),cap(cap),cost(cost),flow(flow){}
	edge(){}
};
vector<edge> edges;
vector<int> node[700];//1-60 is the car  71-INF is the worker

void addedge(int from,int to,int cap,int flow,int cost){
	edges.push_back( edge(from,to,cap,0,cost) );
	edges.push_back( edge(to,from,0,0,-cost) );
	int asd=edges.size();
	node[from].push_back(asd-2);
	node[to].push_back(asd-1);
}

void init(){
	cin>>m>>n;
	for (int i=1,hc;i<=n;i++){//car
		for (int j=1;j<=m;j++){//worker
		    scanf("%d",&hc);//hc=-hc;
		    for (int k=1,hj;k<=n;k++){
                hj=n+(j-1)*n+k;
				addedge(i,hj,1,0,hc*k);		    	
		    }
		}
	}
	s=0;t=n+n*m+1;
	for (int i=1;i<=n;i++) addedge(0,i,1,0,0);
	for (int i=n+1;i<t;i++) addedge(i,t,1,0,0);
}

int d[1000],a[1000],p[1000],inq[1000];
bool bellman_ford(){
	queue<int> Q;Q.push(s);
	memset(inq,0,sizeof (inq));
	for (int i=1;i<=t;i++) d[i]=0x7ffffeee;
	a[s]=0x7ffffeee;d[s]=0;p[s]=0;inq[s]=1;
	
	while(!Q.empty()) {
		int now=Q.front();Q.pop();inq[now]=0;
		int len=node[now].size();
		for (int i=0;i<len;i++){
			edge& e=edges[node[now][i]];
			if (e.cap>e.flow && d[e.to]>d[now]+e.cost){
				d[e.to]=d[now]+e.cost;
				p[e.to]=node[now][i];
				a[e.to]=min(a[now],e.cap-e.flow);
				if (!inq[e.to]) inq[e.to]=1,Q.push(e.to);
			}
		}
	}
	if (d[t]==0x7ffffeee) return false;
	vout+=d[t]*a[t];
	for (int i=t;i!=s;i=edges[p[i]].from){
		edges[p[i]].flow+=a[t];
		edges[p[i]^1].flow-=a[t];
	}
	return true;
}

int main(){
	init();
	while (bellman_ford()) {}
	printf("%.2f",(double)vout/(double)n);
	return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注