現在怎么做的題都這么水了。。

題目鏈接: (bzoj) https://www.lydsy.com/JudgeOnline/problem.php?id=4819

(luogu) https://www.luogu.org/problemnew/show/P3705

題解: 常規分數規劃套路，二分答案\(mid\)之后邊權改變為\(a_{i,j}-mid\times b_{i,j}\)求最大費用最大流即可。（我求成最小費用了，真厲害）

從網上學到一種神奇做法: 迭代

每次按照上次的答案\(mid\)來計算，順便求出方案，據此求出這次的答案，若兩次答案差大于一閾值則繼續迭代

至于為什么是對的。。。只能說感性理解吧（大霧）

這樣的話次數會小很多！但是這種網絡流題求方案比較容易，如果是一些求答案很簡單但是求方案很麻煩的問題，迭代就不適用了。

代碼

迭代

#include<cstdio> #include<cstdlib> #include<cstring> #include<cassert> #include<algorithm> #include<cmath> using namespace std;const double INF = 1e9; const double EPS = 1e-8;namespace MaxFlowMinCost {const int N = 202;const int M = 10200;struct Edge{int u,v,w,nxt,rev; double c;} e[(M<<1)+3];int fe[N+3];int que[N+3];bool inq[N+3];double dis[N+3];int lst[N+3];int n,en,s,t,mf; double mc;void clear(){for(int i=1; i<=n; i++) fe[i] = que[i] = lst[i] = 0;for(int i=1; i<=en; i++) e[i].u = e[i].v = e[i].w = e[i].nxt = e[i].rev = 0,e[i].c = 0.0;n = en = s = t = mf = 0; mc = 0.0;}void addedge(int u,int v,int w,double c){ // printf("addedge %d %d %d %lf\n",u,v,w,c);en++; e[en].u = u; e[en].v = v; e[en].w = w; e[en].c = c;e[en].nxt = fe[u]; fe[u] = en; e[en].rev = en+1;en++; e[en].u = v; e[en].v = u; e[en].w = 0; e[en].c = -c;e[en].nxt = fe[v]; fe[v] = en; e[en].rev = en-1;}bool spfa(){for(int i=1; i<=n; i++) dis[i] = -INF;int head = 1,tail = 2; que[1] = s; dis[s] = 0.0; inq[s] = true;while(head!=tail){int u = que[head]; head++; if(head>n+1) head = 1;for(int i=fe[u]; i; i=e[i].nxt){if(dis[e[i].v]<dis[u]+e[i].c-EPS && e[i].w>0){dis[e[i].v] = dis[u]+e[i].c;lst[e[i].v] = i;if(!inq[e[i].v]){que[tail] = e[i].v; tail++; if(tail>n+1) tail = 1;inq[e[i].v] = true;}}}inq[u] = false;}return dis[t]>-INF+1;}void calc_mfmc(){int flow = 100;for(int i=t; i!=s; i=e[lst[i]].u) {flow = min(flow,e[lst[i]].w);}for(int i=t; i!=s; i=e[lst[i]].u) {e[lst[i]].w -= flow; e[e[lst[i]].rev].w += flow;}mf += flow; mc += dis[t]*(double)flow;}void mfmc(int _n,int _s,int _t){n = _n; s = _s; t = _t;while(spfa()){calc_mfmc();} // printf("mf=%d mc=%lf\n",mf,mc);} } using MaxFlowMinCost::fe; using MaxFlowMinCost::e;const int N = 100; int a[N+3][N+3],b[N+3][N+3]; int n;int main() {scanf("%d",&n);for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) scanf("%d",&a[i][j]);for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) scanf("%d",&b[i][j]);double mid = 0.0,ans = 1.0;while(abs(ans-mid)>EPS){mid = ans; // printf("mid=%lf ans=%lf\n",mid,ans);for(int i=1; i<=n; i++) {MaxFlowMinCost::addedge(1,i+2,1,0.0);}for(int i=1; i<=n; i++) {MaxFlowMinCost::addedge(i+n+2,2,1,0.0);}for(int i=1; i<=n; i++){for(int j=1; j<=n; j++){MaxFlowMinCost::addedge(i+2,j+n+2,1,a[i][j]-b[i][j]*mid);}}MaxFlowMinCost::mfmc(n+n+2,1,2);double deno = 0.0,nume = 0.0;for(int i=3; i<=n+2; i++){for(int j=fe[i]; j; j=e[j].nxt){if(e[j].w==0){int x = i-2,y = e[j].v-n-2; // printf("(%d %d)\n",x,y);nume += a[x][y]; deno += b[x][y];break;}}}ans = nume/deno;MaxFlowMinCost::clear();}printf("%.6lf\n",ans);return 0; }

總結

以上是生活随笔為你收集整理的BZOJ 4819 Luogu P3705 [SDOI2017]新生舞会 (最大费用最大流、二分、分数规划)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。