首页 > 代码库 > bzoj1070题解

bzoj1070题解

2024-09-10 17:19:24   209人阅读

【解题思路】

　　考虑拆点，得到一个二分图：左边点<i,j>表示第i个技师按顺序第j辆修的车，右边点k表示第k个车主，连接左右的边表示第k个车主可能成为第i个技师的第j个客户。

　　虽然是二分图，但直接跑匈牙利会跪，于是考虑费用流，左图都和源点连边，右图都和汇点连边，跑个流即可。复杂度O(松)。

【参考代码】

技术分享
 1 #pragma GCC optimize(2) 2 #include <cstdio> 3 #include <cstring> 4 #define REP(i,low,high) for(register int i=(low);i<=(high);i++) 5 #define INF 0x7f7f7f7f 6 using namespace std; 7 template<typename T> inline bool getmin(T &tar,const T &pat) {return pat<tar?tar=pat,1:0;} 8 const static int T=1001; static int E=1; bool inq[T+10]; int w,c,hed[T+10],pre[T+10],que[T<<3]; long long dst[T+10],tim[10][100]; 9 struct edge10 {11     int fr,to,fl,nx; long long vl;12     edge() {fl=INF;}13     edge(const int &x,const int &y,const int &f,const long long &v) {fr=x,to=y,fl=f,vl=v,nx=hed[x],hed[x]=E;}14 }edg[100010];15 inline void add_edge(const int &fr,const int &to,const int &fl,const long long &vl) {edg[++E]=edge(fr,to,fl,vl),edg[++E]=edge(to,fr,0,-vl);}16 inline bool SPFA()17 {18     memset(dst,0x7f,sizeof dst),dst[0]=que[0]=0ll,memset(inq,0,sizeof inq),inq[0]=1;19     for(int head=-1,tail=0;head++<tail;)20     {21         int now=que[head];22         for(int i=hed[now];i;i=edg[i].nx)23         {24             int p=edg[i].to; if(edg[i].fl&&getmin(dst[p],dst[now]+edg[i].vl)) {pre[p]=i; if(!inq[p]) inq[que[++tail]=p]=1;}25         }26         inq[now]=0;27     }28     return dst[T]<INF;29 }30 int main()31 {32     scanf("%d%d",&w,&c),memset(hed,0,sizeof hed); REP(i,1,c) REP(j,1,w) scanf("%lld",&tim[j][i]); int n=w*c; long long ans=0ll;33     REP(i,1,n) add_edge(0,i,1,0ll); REP(i,1,c) add_edge(n+i,T,1,0ll); REP(i,1,w) REP(j,1,c) REP(k,1,c) add_edge((i-1)*c+j,n+k,1,tim[i][k]*j);34     while(SPFA())35     {36         int mnr=INF; for(int i=pre[T];i;i=pre[edg[i].fr]) getmin(mnr,edg[i].fl);37         for(int i=pre[T];i;i=pre[edg[i].fr]) edg[i].fl-=mnr,edg[i^1].fl+=mnr,ans+=edg[i].vl*mnr;38     }39     return printf("%.2lf\n",(double)ans/c),0;40 }
View Code

 

bzoj1070题解


联系
我们