BZOJ3993: [SDOI2015]星際戰爭

Description

?3333年，在銀河系的某星球上，X軍團和Y軍團正在激烈地作戰。在戰斗的某一階段，Y軍團一共派遣了N個巨型機器人進攻X軍團的陣地，其中第i個巨型機器人的裝甲值為Ai。當一個巨型機器人的裝甲值減少到0或者以下時，這個巨型機器人就被摧毀了。X軍團有M個激光武器，其中第i個激光武器每秒可以削減一個巨型機器人Bi的裝甲值。激光武器的攻擊是連續的。這種激光武器非常奇怪，一個激光武器只能攻擊一些特定的敵人。Y軍團看到自己的巨型機器人被X軍團一個一個消滅，他們急需下達更多的指令。為了這個目標，Y軍團需要知道X軍團最少需要用多長時間才能將Y軍團的所有巨型機器人摧毀。但是他們不會計算這個問題，因此向你求助。

Input

第一行，兩個整數，N、M。

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

Output

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

Sample Input

2 2
3 10
4 6
0 1
1 1

Sample Output

1.300000

HINT

?【樣例說明1】

戰斗開始后的前0.5秒，激光武器1攻擊2號巨型機器人，激光武器2攻擊1號巨型機器人。1號巨型機器人被完全摧毀，2號巨型機器人還剩余8的裝甲值； 接下來的0.8秒，激光武器1、2同時攻擊2號巨型機器人。2號巨型機器人被完全摧毀。 對于全部的數據，1<=N, M<=50，1<=Ai<=105，1<=Bi<=1000，輸入數據保證X軍團一定能摧毀Y軍團的所有巨型機器人

---

題解Here! 很容易想到我們二分所需要的時間$T$。 然后用網絡流判定是否能在這段時間內打完。 建圖很簡單：

從$S$到每一個武器$i$連一條邊，容量為$B_i\times t$。

從每一個機器人$i+m$向$T$連一條邊，容量為$A_i$。

從每個武器向所有能攻擊的機器人連一條邊，容量為$MAX$。

然后就可以跑了。

對于精度問題，注意到這題的精度要求并不是很高。

可以不用$double$二分及計算，把所有的流量全部乘以$10000$即可。

記得開$long\ long$。

附代碼：

#include<iostream> #include<algorithm> #include<cstdio> #include<queue> #include<cstring> #define MAXN 60 #define MAX (1LL<<62) using namespace std; int n,m,c=2,s,t; long long sum=0,blood[MAXN],attack[MAXN]; bool edge[MAXN][MAXN]; int head[MAXN<<1],deep[MAXN<<1]; struct node{int next,to;long long w; }a[MAXN*MAXN<<1]; inline int read(){int date=0,w=1;char c=0;while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}return date*w; } inline void add(int u,int v,long long w){a[c].to=v;a[c].w=w;a[c].next=head[u];head[u]=c++;a[c].to=u;a[c].w=0;a[c].next=head[v];head[v]=c++; } bool bfs(){int u,v;queue<int> q;for(int i=s;i<=t;i++)deep[i]=0;deep[s]=1;q.push(s);while(!q.empty()){u=q.front();q.pop();for(int i=head[u];i;i=a[i].next){v=a[i].to;if(a[i].w&&!deep[v]){deep[v]=deep[u]+1;if(v==t)return true;q.push(v);}}}return false; } long long dfs(int x,long long limit){if(x==t)return limit;int v;long long sum,cost=0;for(int i=head[x];i;i=a[i].next){v=a[i].to;if(a[i].w&&deep[v]==deep[x]+1){sum=dfs(v,min(a[i].w,limit-cost));if(sum>0){a[i].w-=sum;a[i^1].w+=sum;cost+=sum;if(cost==limit)break;}else deep[v]=-1;}}return cost; } long long dinic(){long long ans=0;while(bfs())ans+=dfs(s,MAX);return ans; } inline void clean(){c=2;memset(head,0,sizeof(head));memset(a,0,sizeof(a)); } bool check(long long x){clean();for(int i=1;i<=m;i++)add(s,i,x*attack[i]);for(int i=1;i<=n;i++)add(i+m,t,blood[i]);for(int i=1;i<=m;i++)for(int j=1;j<=n;j++)if(edge[i][j])add(i,j+m,MAX);long long now=dinic();return (now<sum?true:false); } void work(){long long l=0,r=100000000000LL,mid;while(l<=r){mid=l+r>>1;if(check(mid))l=mid+1;else r=mid-1;}printf("%.6lf\n",(double)l/10000.00); } void init(){n=read();m=read();s=0;t=n+m+1;for(int i=1;i<=n;i++){blood[i]=10000LL*read();sum+=blood[i];}for(int i=1;i<=m;i++)attack[i]=read();for(int i=1;i<=m;i++)for(int j=1;j<=n;j++)edge[i][j]=read(); } int main(){init();work();return 0; }

?

轉載于:https://www.cnblogs.com/Yangrui-Blog/p/9519890.html

總結

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

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