字符串終于告一段落了！

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

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

網(wǎng)絡(luò)流從最水的開(kāi)始做。。。

題解: 二分答案ans, 然后可以得到每個(gè)攻擊者在ans時(shí)間內(nèi)最多產(chǎn)生的總傷害，從起點(diǎn)往攻擊者連邊容量為此值，從每個(gè)攻擊者往能攻擊的防御者連邊容量為\(+\inf\), 從每個(gè)防御者往終點(diǎn)連邊邊權(quán)為其裝甲值，求最大流，判斷其是否等于裝甲值之和即可。

時(shí)間復(fù)雜度\(O(MaxFlow(n,n^2))\)

代碼

#include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #include<cmath> using namespace std;const int N = 102; const int M = 2600; const double INF = 1e7; const double EPS = 1e-8;namespace MaxFlow {struct Edge{int v,nxt,rev; double w;} e[(M<<1)+3];int fe[N+3];int te[N+3];int dep[N+3];int que[N+3];int n,en;void clear(){for(int i=1; i<=en; i++){e[i].v = e[i].nxt = e[i].rev = 0; e[i].w = 0.0;}for(int i=1; i<=n; i++) fe[i] = 0;n = en = 0;}void addedge(int u,int v,double w){en++; e[en].v = v; e[en].w = w;e[en].nxt = fe[u]; fe[u] = en; e[en].rev = en+1;en++; e[en].v = u; e[en].w = 0;e[en].nxt = fe[v]; fe[v] = en; e[en].rev = en-1;}bool bfs(){for(int i=1; i<=n; i++) dep[i] = 0;int head = 1,tail = 1; que[tail] = 1; dep[1] = 1;while(head<=tail){int u = que[head]; head++;for(int i=fe[u]; i; i=e[i].nxt){if(dep[e[i].v]==0 && e[i].w>EPS){dep[e[i].v] = dep[u]+1;tail++; que[tail] = e[i].v;}}}return dep[2]!=0;}double dfs(int u,double cur){if(u==2) return cur;double rst = cur;for(int i=te[u]; i; i=e[i].nxt){if(dep[e[i].v]==dep[u]+1 && e[i].w>0 && rst>0){double flow = dfs(e[i].v,min(rst,e[i].w));if(flow>EPS){rst -= flow; e[i].w -= flow; e[e[i].rev].w += flow;if(e[i].w>EPS) te[u] = i;if(rst==0) return cur;}}}if(abs(cur-rst)<EPS) dep[u] = 0;return cur-rst;}double dinic(int _n){n = _n;double ret = 0.0;while(bfs()){for(int i=1; i<=n; i++) te[i] = fe[i];ret += dfs(1,INF);}return ret;} }int a[N+3],b[N+3]; int c[N+3][N+3]; int n,m;int main() {scanf("%d%d",&n,&m); double std = 0.0;for(int i=1; i<=n; i++) {scanf("%d",&a[i]); std += (double)a[i];}for(int i=1; i<=m; i++) scanf("%d",&b[i]);for(int i=1; i<=m; i++){for(int j=1; j<=n; j++) scanf("%d",&c[i][j]);}double left = 0.0,right = INF;while(right-left>1e-5){double mid = (left+right)*0.5;MaxFlow::clear();for(int i=1; i<=m; i++){MaxFlow::addedge(1,i+2,mid*(double)b[i]);}for(int i=1; i<=n; i++){MaxFlow::addedge(i+m+2,2,(double)a[i]);}for(int i=1; i<=m; i++){for(int j=1; j<=n; j++){if(c[i][j]==1){MaxFlow::addedge(i+2,j+m+2,INF);}}}double ans = MaxFlow::dinic(m+n+2);if(abs(ans-std)<EPS){right = mid;}else{left = mid;}}printf("%.6lf\n",left);return 0; }

總結(jié)

以上是生活随笔為你收集整理的BZOJ 3993 Luogu P3324 [SDOI2015]星际战争 (最大流、二分答案)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。