題目描述

3333年，在銀河系的某星球上，X軍團和Y軍團正在激烈地作戰。

在戰斗的某一階段，Y軍團一共派遣了N個巨型機器人進攻X軍團的陣地，其中第i個巨型機器人的裝甲值為Ai。當一個巨型機器人的裝甲值減少到0或者以下時，這個巨型機器人就被摧毀了。

X軍團有M個激光武器，其中第i個激光武器每秒可以削減一個巨型機器人Bi的裝甲值。激光武器的攻擊是連續的。

這種激光武器非常奇怪，一個激光武器只能攻擊一些特定的敵人。Y軍團看到自己的巨型機器人被X軍團一個一個消滅，他們急需下達更多的指令。

為了這個目標，Y軍團需要知道X軍團最少需要用多長時間才能將Y軍團的所有巨型機器人摧毀。但是他們不會計算這個問題，因此向你求助。

輸入輸出格式

輸入格式：

?

第一行，兩個整數，N、M。第二行，N個整數，A1、A2...AN。第三行，M個整數，B1、B2...BM。接下來的M行，每行N個整數，這些整數均為0或者1。這部分中的第i行的第j個整數為0表示第i個激光武器不可以攻擊第j個巨型機器人，為1表示第i個激光武器可以攻擊第j個巨型機器人。

?

輸出格式：

?

一行，一個實數，表示X軍團要摧毀Y軍團的所有巨型機器人最少需要的時間。輸出結果與標準答案的絕對誤差不超過10-3即視為正確。

?

輸入輸出樣例

輸入樣例#1：?復制 2 2 3 10 4 6 0 1 1 1 輸出樣例#1：?復制 1.300000

說明

【樣例說明1】

戰斗開始后的前0.5秒，激光武器1攻擊2號巨型機器人，激光武器2攻擊1號巨型機器人。1號巨型機器人被完全摧毀，2號巨型機器人還剩余8的裝甲值；

接下來的0.8秒，激光武器1、2同時攻擊2號巨型機器人。2號巨型機器人被完全摧毀。

對于全部的數據，1<=N, M<=50，1<=Ai<=10^5105，1<=Bi<=1000，輸入數據保證X軍團一定能摧毀Y軍團的所有巨型機器人

題解

　　第一眼看過去：不就是個裸的費用流么

　　第二眼：臥槽為啥答案是個實數

　　然后就gg了，乖乖跑去看題解了

　　我原來思路是這樣，連邊，容量為攻擊力，然后費用為1，代表天數，跑個最小費用流（后來發現自己sb了……因為不同激光的費用會算在一起……）

　　然而天數有可能是實數

　　那么我們可以考慮二分答案，枚舉到底有幾天，然后建邊如下

　　對于每一個激光武器，我們從源向他連邊，容量為攻擊力*天數（表示它這幾天不停攻擊能有這么多攻擊力）

　　對于每一個機器人，我們把它向匯連邊，容量為血量（代表他能承受這么多攻擊力）

　　然后激光對能攻擊到的機器人連邊

　　那么跑一個最大流，看看流是否等于機器人的總血量，是的話就滿足答案了

　　然而因為都是實數，精度是$1e-3$，那么我們可以把所有的數都乘上$10000$來消除精度的影響

　　那么就需要開很多$long\ long$了，所以……?#define int long long?了解一下？

1 //minamoto 2 #include<iostream> 3 #include<cstdio> 4 #include<cstring> 5 #include<queue> 6 #define int long long 7 #define inf 1e15 8 using namespace std; 9 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) 10 char buf[1<<21],*p1=buf,*p2=buf; 11 inline int read(){ 12 #define num ch-'0' 13 char ch;bool flag=0;int res; 14 while(!isdigit(ch=getc())) 15 (ch=='-')&&(flag=true); 16 for(res=num;isdigit(ch=getc());res=res*10+num); 17 (flag)&&(res=-res); 18 #undef num 19 return res; 20 } 21 const int N=205,M=50005; 22 int head[N],Next[M],ver[M],edge[M],tot; 23 inline void init(){memset(head,0,sizeof(head)),tot=1;} 24 inline void add(int u,int v,int e){ 25 ver[++tot]=v,Next[tot]=head[u],head[u]=tot,edge[tot]=e; 26 ver[++tot]=u,Next[tot]=head[v],head[v]=tot,edge[tot]=0; 27 } 28 int dep[N],cur[N],n,m,s,t; 29 queue<int> q; 30 bool bfs(){ 31 memset(dep,-1,sizeof(dep)); 32 while(!q.empty()) q.pop(); 33 for(int i=s;i<=t;++i) cur[i]=head[i]; 34 q.push(s),dep[s]=0; 35 while(!q.empty()){ 36 int u=q.front();q.pop(); 37 for(int i=head[u];i;i=Next[i]){ 38 int v=ver[i]; 39 if(dep[v]<0&&edge[i]){ 40 dep[v]=dep[u]+1,q.push(v); 41 if(v==t) return true; 42 } 43 } 44 } 45 return false; 46 } 47 int dfs(int u,int limit){ 48 if(u==t||!limit) return limit; 49 int flow=0,f; 50 for(int i=cur[u];i;i=Next[i]){ 51 int v=ver[i];cur[u]=i; 52 if(dep[v]==dep[u]+1&&(f=dfs(v,min(limit,edge[i])))){ 53 flow+=f,limit-=f; 54 edge[i]-=f,edge[i^1]+=f; 55 if(!limit) break; 56 } 57 } 58 if(!flow) dep[u]=-1; 59 return flow; 60 } 61 int dinic(){ 62 int flow=0; 63 while(bfs()) flow+=dfs(s,inf); 64 return flow; 65 } 66 bool x[N][N];int hp[N],atk[N],sum; 67 void build(int tim){ 68 init(); 69 for(int i=1;i<=n;++i) add(s,i,tim*atk[i]); 70 for(int i=1;i<=m;++i) add(i+n,t,hp[i]); 71 for(int i=1;i<=n;++i) 72 for(int j=1;j<=m;++j) 73 if(x[i][j]) add(i,j+n,inf); 74 } 75 signed main(){ 76 //freopen("testdata.in","r",stdin); 77 m=read(),n=read(),s=0,t=n+m+1; 78 for(int i=1;i<=m;++i) hp[i]=read()*10000ll,sum+=hp[i]; 79 for(int i=1;i<=n;++i) atk[i]=read(); 80 for(int i=1;i<=n;++i) 81 for(int j=1;j<=m;++j) 82 x[i][j]=read(); 83 int l=0,r=10000000000ll,ans=0; 84 while(l<=r){ 85 int mid=l+r>>1; 86 build(mid); 87 if(dinic()>=sum) ans=mid,r=mid-1; 88 else l=mid+1; 89 } 90 printf("%.4lf\n",ans/10000.0); 91 return 0; 92 }

?

轉載于:https://www.cnblogs.com/bztMinamoto/p/9564156.html

總結

以上是生活随笔為你收集整理的bzoj3993: [SDOI2015]星际战争（二分+最大流）的全部內容，希望文章能夠幫你解決所遇到的問題。

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