- #include
- #include
- #include
- #include
- using namespace std;
- struct X
- {
- int v,f,n,cap,cos;
- }x[66005];
- intti[65][15],s=1,dis[605],fl[605],pre[605];
- boolvis[605];
- queue<int>q;
- voidadd(intu,intv,intcap,int cos)
- {
- x[++s].n=x[u].f;
- x[x[u].f=s].v=v;
- x[s].cap=cap;
- x[s].cos=cos;
- }
- bool spfa()
- {
- memset(dis,0x3f,sizeof(dis));
- memset(fl,0,sizeof(fl));
- q.push(1);vis[1]=1;
- dis[1]=0;fl[1]=61;
- for(;!q.empty();q.pop())
- {
- intu=q.front();vis[u]=0;
- for(inti=x[u].f;i;i=x[i].n)
- if(x[i].cap&&dis[x[i].v]>dis[u]+x[i].cos)
- {
- fl[x[i].v]=min(fl[u],x[i].cap);
- pre[x[i].v]=i;
- dis[x[i].v]=dis[u]+x[i].cos;
- if(!vis[x[i].v])
- {
- vis[x[i].v]=1;
- q.push(x[i].v);
- }
- }
- }
- returndis[2]<1061109567;
- }
- int main()
- {
- intn,m,cnt,ans=0;
- scanf("%d%d",&m,&n);
- cnt=n+2;
- for(inti=1;i<=n;++i)
- for(intj=1;j<=m;++j)
- scanf("%d",&ti[i][j]);
- for(inti=1;i<=n;++i)
- {
- add(i+2,2,1,0);
- add(2,i+2,0,0);
- for(intj=1;j<=m;++j)
- {
- ++cnt;
- add(1,cnt,1,0);
- add(cnt,1,0,0);
- for(intk=1;k<=n;++k)
- {
- add(cnt,k+2,61,i*ti[k][j]);
- add(k+2,cnt,0,-i*ti[k][j]);
- }
- }
- }
- while(spfa())
- {
- ans+=dis[2]*fl[2];
- for(inti=2;i!=1;i=x[pre[i]^1].v)
- x[pre[i]].cap-=fl[2],x[pre[i]^1].cap+=fl[2];
- }
- printf("%.2lf",(double)ans/n);
- return 0;
- }
来源: