題目鏈接：點(diǎn)我點(diǎn)我:-) —只有洛谷有此題
題目描述： 奶酪店里最近出現(xiàn)了m只老鼠！它們的目標(biāo)就是把生產(chǎn)出來(lái)的所有奶酪都吃掉。奶酪店中一天會(huì)生產(chǎn)n塊奶酪，其中第i塊的大小為pi，會(huì)在第ri秒被生產(chǎn)出來(lái)，并且必須在第di秒之前將它吃掉。第j只老鼠吃奶酪的速度為sj，因此如果它單獨(dú)吃完第i快奶酪所需的時(shí)間為pi/sj。老鼠們吃奶酪的習(xí)慣很獨(dú)特，具體來(lái)說(shuō)： (1) 在任一時(shí)刻，一只老鼠最多可以吃一塊奶酪； (2) 在任一時(shí)刻，一塊奶酪最多被一只老鼠吃。 由于奶酪的保質(zhì)期常常很短，為了將它們?nèi)砍缘簦鲜髠冃枰褂靡环N神奇的魔法來(lái)延長(zhǎng)奶酪的保質(zhì)期。將奶酪的保質(zhì)期延長(zhǎng)T秒是指所有的奶酪的di變成di+T。同時(shí)，使用魔法的代價(jià)很高，因此老鼠們希望找到最小的T使得可以吃掉所有的奶酪。
輸入格式： 輸入文件的第一行包含一個(gè)整數(shù)K，表示輸入文件中數(shù)據(jù)的組數(shù)。 每組數(shù)據(jù)的第一行包含兩個(gè)整數(shù)n和m，分別表示奶酪和老鼠的數(shù)量。接下來(lái)的n行每行包含三個(gè)整數(shù)pi,ri,di。最后m行每行包含一個(gè)整數(shù)，表示sj。pi,ri,di,sj的含義如上文所述。
輸出格式： 包含K行，每行包含一個(gè)實(shí)數(shù)，表示你找到的最小的T。你的答案和標(biāo)準(zhǔn)答案的絕對(duì)誤差不應(yīng)超過(guò)
數(shù)據(jù)規(guī)模： 30%的數(shù)據(jù)中，1≤n,m≤5； 100%的數(shù)據(jù)中，1≤K≤5,1≤n,m≤30,1≤pi≤
思路： 網(wǎng)絡(luò)流好題 應(yīng)該容易想到二分答案和離散化奶酪的時(shí)間點(diǎn)
先考慮樸素的建圖，也就是不考慮每個(gè)時(shí)刻可以有多只老鼠在不同的小時(shí)刻吃同一個(gè)奶酪 1.我們將源點(diǎn)每個(gè)奶酪鏈流量為p[i]的邊 2.然后把每只老鼠的每個(gè)時(shí)間段拆為一個(gè)點(diǎn)，再將其與對(duì)應(yīng)的奶酪連邊，流量為這只老鼠可以在這個(gè)時(shí)間段吃多少奶酪 3.所有的老鼠向匯點(diǎn)連邊，無(wú)限流量
然而題目有限制，每個(gè)時(shí)刻可以有多只老鼠在不同的小時(shí)刻吃同一個(gè)奶酪，做法很巧妙，我們可以對(duì)老鼠的速度再進(jìn)行拆點(diǎn)，把s[]從大到小排序然后與下一個(gè)作差，如”9 6 2 1” -> “3 4 1 1”，然后再將其與匯點(diǎn)連邊的流量改為（rat為老鼠編號(hào)，dur為時(shí)間段大小，s為作差后的數(shù)組）rat*s[rat]*dur即可
為什么呢？ 可以發(fā)現(xiàn)速度進(jìn)行過(guò)如此處理之后， 9 = 3+4+1+1 6 = 4+1+1 2 = 1+1 1 = 1 9+6+2+1 = 3*1 + 4*2 + 1*3 + 1*4 (下面所有的s數(shù)組均為作差后的數(shù)組) 1.所以，當(dāng)我們把老鼠點(diǎn)到匯點(diǎn)的流量限制設(shè)為rat*s[rat]*dur后，對(duì)于每一只老鼠，它‘吃’的量不超過(guò)實(shí)際可以‘吃’的量。（上述式子解釋了，實(shí)際包括編號(hào)比它小的老鼠的吃的量） 2.每個(gè)老鼠點(diǎn)與奶酪的連邊為s[rat]*dur，這樣可以保證每只老鼠實(shí)際不可以超過(guò)自己這段時(shí)間可以吃的奶酪。 3.（對(duì)于第2點(diǎn)的解釋）實(shí)際這段時(shí)間奶酪被吃的量不超過(guò)最快的老鼠的速度在這個(gè)時(shí)間段可以吃的量，如果每只老鼠在2點(diǎn)所述的邊滿流，那么實(shí)際相當(dāng)于吃的最快的老鼠吃了這一整個(gè)時(shí)間段。而任何其它的情況均可以用別的老鼠湊出來(lái)，且由于第一點(diǎn)不會(huì)不合法
最后，每次二分答案，重新構(gòu)圖跑最大流，檢查是否滿流即可。
感想： 很好的網(wǎng)絡(luò)流題目，然而連網(wǎng)絡(luò)流都沒(méi)想到是什么鬼？？？ 原來(lái)網(wǎng)絡(luò)流構(gòu)圖還可以這么神奇，把每個(gè)點(diǎn)使勁拆成這個(gè)鬼樣子！！！ 網(wǎng)絡(luò)流的代碼應(yīng)該沒(méi)什么問(wèn)題了，但是構(gòu)圖能力還要再提高啦！ 吐槽一下我調(diào)了3個(gè)小時(shí)的錯(cuò)誤： 1.精度eps，寫錯(cuò)居然可以導(dǎo)致最大流超過(guò)了我的p數(shù)組值的和！！！ 2.我的天哪：(f=dfs(e.to, fmin(Mint, e.cap-e.flow)))>eps 這句話我不小心把 > eps寫到最后一個(gè)括號(hào)里面了。。
代碼：
//miaomiao 2017.2.3#include<cstdio>#include<cmath>#include<cstring>#include<algorithm>#include<vector>#include<queue>using namespace std;#define pb push_back#define Set(a, v) memset(a, v, sizeof(a))#define For(i, a, b) for(int i = (a); i <= (int)(b); i++)#define MN (30+5)#define N (3000+5)#define eps (1e-6)struct Edge{ int from, to; double cap, flow;};struct Dinic{ vector<int> G[N]; vector<Edge> edges; int m, s, t; int cur[N], d[N]; void init(){ For(i, 0, N-1) G[i].clear(); edges.clear(); } void AddEdge(int u, int v, double cap){ edges.pb((Edge){u, v, cap, 0}); edges.pb((Edge){v, u, 0, 0}); m = edges.size(); G[u].pb(m-2); G[v].pb(m-1); } bool Bfs(){ queue<int> q; q.push(s); Set(d, 0); d[s] = 1; int now; while(!q.empty()){ now = q.front(); q.pop(); For(i, 0, G[now].size()-1){ Edge &e = edges[G[now][i]]; if(!d[e.to] && e.cap-e.flow > eps){ d[e.to] = d[now]+1; q.push(e.to); } } } return d[t]; } double dfs(int now, double Mint){ if(Mint < eps || now == t) return Mint; double f; double ret = 0.0; for(int &i = cur[now]; i < G[now].size(); i++){ Edge &e = edges[G[now][i]]; if(d[e.to]==d[now]+1 && (f=dfs(e.to, fmin(Mint, e.cap-e.flow)))>eps){ e.flow += f; Mint -= f; edges[G[now][i]^1].flow -= f; ret += f; if(Mint < eps) return ret; } } return ret; } double Maxflow(){ double ret = 0.0; while(Bfs()){ Set(cur, 0); ret += dfs(s, (1LL<<60)*1.0); } return ret; }}Din;int n, m;double L, R, rp[MN], rr[MN], rd[MN], rs[MN], Ti[MN*2];void solve(){ double mid, la, sum = 0; int pn; For(i, 1, n) sum += rp[i]; while(R-L > eps){ mid = (L+R)/2.0; Din.init(); For(i, 1, n) Din.AddEdge(0, i, rp[i]); For(i, 1, n){ Ti[2*i-1] = rr[i]; Ti[2*i] = rd[i]+mid; } sort(Ti+1, Ti+2*n+1); Din.s = 0; Din.t = m*2*n+n+1; pn = n; For(rat, 1, m){ la = Ti[1]; For(i, 2, 2*n){ if(Ti[i]-la < eps) continue; ++pn; Din.AddEdge(pn, Din.t, rat*rs[rat]*(Ti[i]-la)); For(j, 1, n) if(rr[j]-la < eps && (rd[j]+mid)-Ti[i] > -eps) Din.AddEdge(j, pn, rs[rat]*(Ti[i]-la)); la = Ti[i]; } } if(sum-Din.Maxflow() < eps) R = mid; else L = mid; }新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
