P2053 SCOI2007 修車 網路流

2022-09-22 20:48:01 字數 1462 閱讀 6740

戳這裡

建不會建模,直接搬運題解的做法

我麼將題意轉化一下,求出每一個人對於整體答案的貢獻,如果一輛車後面等了 \(k\) 個人,那麼這輛車的被等待時間就是 \(k\times t_\) ,然後我們要做的就是為每一輛車分配一個修車工人和一個修車次序,使得任意兩個車的修車工人和修車次序不會相同,然後使得總體的貢獻最小,這個很費用流

具體來說就是設 \(f_(i,j)\) 表示第 \(i\) 個工人的第 \(j\) 次修理,這樣我們把每一輛車 \(x\) 向這一個點連一條邊,它的等待時間就是 \(j\times t(i,x)\) ,也就是這條邊的費用,然後原點向每一輛車連一條邊權為 \(0\) 流量為 \(1\) 的邊,每一個工人的每一次修理向匯點連一條邊權為 \(0\) 流量為 \(1\) 的邊,這樣跑一遍費用流,保證了不會有任何兩輛車連向同一次修理

#include#define pii pair#define mk(x,y) make_pair(x,y)

#define lc rt<<1

#define rc rt<<1|1

#define pb push_back

#define fir first

#define sec second

#define inl inline

#define reg register

using namespace std;

namespace zzc

while (isdigit(ch))

return x*f; }

const int maxn = 1e3+5;

const int maxm = 1e5+5;

const int inf = 0x3f3f3f3f;

int n,m,st,ed,cnt=1,ans;

int head[maxn],dep[maxn],lst[maxn],siz[maxn],pre[maxn],flow[maxn],dis[maxn];

bool vis[maxn];

queueq;

struct edge

e[maxm];

void add(int u,int v,int w,int x)

void add_edge(int u,int v,int w,int x)

inl int id(int x,int y)

bool spfa()}}

} return pre[ed]!=-1; }

void mcmf()

} }

void work()

}for(int j=1;j<=m;j++) for(int k=1;k<=n;k++) add_edge(id(j,k),ed,1,0);

mcmf();

printf("%.2f\n",1.0*ans/n); }}

int main()

P2053 SCOI2007 修車

題目連結 這是一道很不錯的費用流好題,建圖的思想很是巧妙 我們把每個工人拆成 n 個點,表示當前工人在 n 個不同的時間段,那麼 m 個工人...

P2053 SCOI2007 修車

同一時刻有n位車主帶著他們的愛車來到了汽車維修中心。維修中心共有m位技術人員,不同的技術人員對不同的車進行維修所用的時間是不同的。現在需要安排這m位技術人員所維修的車及順序,使得顧客平均等待的時間最小。 說明 顧客的等待時間是指從他把車送至維修中心到維修完畢所用的時間。 第一行有兩個數m n,表示技...

P2053 SCOI2007 修車 費用流

同一時刻有n位車主帶著他們的愛車來到了汽車維修中心。維修中心共有m位技術人員,不同的技術人員對不同的車進行維修所用的時間是不同的。現在需要安排這m位技術人員所維修的車及順序,使得顧客平均等待的時間最小。 說明 顧客的等待時間是指從他把車送至維修中心到維修完畢所用的時間。 左邊放n個點,表示n輛車。右...