【bzoj1070】修车

  • 本文为博主原创,未经许可不得转载

我真是废了,这么水的题我居然没看出来是费用流

把每个人拆成n个点,表示次数即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<bits/stdc++.h>
#define FILE "read"
#define MAXN 100010
#define INF (int)1e9
using namespace std;
struct node{int y,next,v,w;}e[MAXN<<1];
int n,m,S,T,cnt,ans,len(1),a[110][110],Link[MAXN],vis[MAXN],dis[MAXN],id[110][110],LN[MAXN],LE[MAXN],flow[MAXN];
queue<int>q;
inline int read(){
int x=0,f=1; char ch=getchar();
while(ch>'9'||ch<'0') {if(ch=='-') f=-1; ch=getchar();}
while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
void insert(int x,int y,int v,int w){
e[++len].next=Link[x];Link[x]=len;e[len].y=y;e[len].v=v;e[len].w=w;
e[++len].next=Link[y];Link[y]=len;e[len].y=x;e[len].v=0;e[len].w=-w;
}
bool spfa(){
memset(vis,0,sizeof(vis));
memset(dis,10,sizeof(dis));
int oo=dis[0];q.push(S);dis[S]=0;vis[S]=1;flow[S]=INF;
while(!q.empty()){
int x=q.front(); q.pop(); vis[x]=0;
for(int i=Link[x];i;i=e[i].next)if(dis[x]+e[i].w<dis[e[i].y]&&e[i].v){
dis[e[i].y]=dis[x]+e[i].w; flow[e[i].y]=min(flow[x],e[i].v);
LN[e[i].y]=x; LE[e[i].y]=i;
if(!vis[e[i].y]) q.push(e[i].y),vis[e[i].y]=1;
}
}
if(dis[T]==oo) return 0;
ans+=flow[T]*dis[T];
for(int i=T;i!=S;i=LN[i]) e[LE[i]].v-=flow[T],e[LE[i]^1].v+=flow[T];
return 1;
}
int main(){
freopen(FILE".in","r",stdin);
freopen(FILE".out","w",stdout);
m=read(); n=read(); S=++cnt; T=++cnt;
for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)a[i][j]=read();
for(int i=1;i<=m;++i)for(int j=1;j<=n;++j)
id[i][j]=++cnt,insert(S,id[i][j],1,0);
for(int i=1;i<=n;++i){
int x=++cnt; insert(x,T,1,0);
for(int j=1;j<=m;++j)for(int k=1;k<=n;++k)insert(id[j][k],x,1,k*a[i][j]);
}
while(spfa());
printf("%.2lf\n",(double)ans/n);
return 0;
}
文章目录
,