洛谷$P2053\ [SCOI2007]$修车 网络流

正解:网络流

解题报告:

传送门$QwQ$

一个很妙的建图,,,说实话我麻油想到$QwQ$

考虑对每个工人建$n$个点,表示这是他修的倒数第$i$辆车,就可以算出影响是$t\cdot i$,然后对每辆车和这$n\cdot m$个节点连边,跑个费用流就做完辣$QwQ$

具体港下怎么建图$QwQ$?

就考虑建两排点,左侧是$n\cdot m$个点表示工人,右侧是$n$个点表示车.然后$S$和工人之间连流量为1费用为0的边,工人和车连流量为1费用为$t\cdot i$的边,车和$T$连流量为1费用为0的边

然后就欧克了?$QwQ$

#include<bits/stdc++.h>

using namespace std;

#define il inline

#define lf double

#define gc getchar()

#define t(i) edge[i].to

#define w(i) edge[i].wei

#define fy(i) edge[i].fy

#define ri register int

#define rb register bool

#define rc register char

#define rp(i,x,y) for(ri i=x;i<=y;++i)

#define e(i,x) for(ri i=head[x];~i;i=edge[i].nxt)

const int N=1e5+;

int head[N],ed_cnt=-,vis[N],S,T,fr_ed[N],fr_nod[N],dis[N],n,m,as;

struct ed{int to,nxt,wei,fy;}edge[N<<];

struct node{int x,y;}nod[N];

il int read()

{

    rc ch=gc;ri x=;rb y=;

    while(ch!='-' && (ch>'' || ch<''))ch=gc;

    if(ch=='-')ch=gc,y=;

    while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=gc;

    return y?x:-x;

}

il int nam(ri x,ri y){return (x-)*n+y;}

il void ad(ri x,ri y,ri z,ri p)

{

    //printf("%d -> %d : %d , %d\n",y,x,z,p);

    edge[++ed_cnt]=(ed){x,head[y],z,p};head[y]=ed_cnt;edge[++ed_cnt]=(ed){y,head[x],,-p};head[x]=ed_cnt;}

il bool spfa()

{

    queue<int>Q;Q.push(S);memset(vis,,sizeof(vis));vis[S]=;memset(dis,,sizeof(dis));dis[S]=;

    while(!Q.empty())

    {

        ri nw=Q.front();Q.pop();vis[nw]=;

        e(i,nw)

            if(w(i) && fy(i)+dis[nw]<dis[t(i)])

            {dis[t(i)]=dis[nw]+fy(i),fr_ed[t(i)]=i,fr_nod[t(i)]=nw;if(!vis[t(i)])Q.push(t(i)),vis[t(i)]=;}

    }

    if(dis[T]==dis[T+])return ;

    //printf("dep[T]=%d\n",dep[T]);

    ri flow=dis[T+];

    for(ri i=T;i!=S;i=fr_nod[i])flow=min(flow,w(fr_ed[i]));

    for(ri i=T;i!=S;i=fr_nod[i])w(fr_ed[i])-=flow,w(fr_ed[i]^)+=flow;as+=dis[T]*flow;

    return ;

}

int main()

{

    //freopen("2053.in","r",stdin);freopen("2053.out","w",stdout);

    memset(head,-,sizeof(head));m=read();n=read();S=,T=n*m+n+;

    rp(j,,m)rp(i,,n)ad(nam(j,i),S,,);rp(i,,n)ad(T,n*m+i,,);

    rp(i,,n)rp(j,,m){ri t=read();rp(k,,n)ad(n*m+i,nam(j,k),,t*k);}

    while(spfa());printf("%.2lf\n",(lf)as/n);

    return ;

}