# 【BZOJ 1070】[SCOI2007] 修车

#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;
}
}
}
s=0;t=n+n*m+1;
}

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;
}


## 2 thoughts to “【BZOJ 1070】[SCOI2007] 修车”

1. Thank you for every other excellent post. Where else may just anyone get that type of information in such an ideal manner of writing? I have a presentation subsequent week, and I am at the search for such info.

2. I think other website proprietors should take this web site as an model, very clean and excellent user genial style and design, let alone the content. You are an expert in this topic!