BZOJ 3993 [SDOI2015]星際戰爭 二分+最大流
來源：程序員人生 發布時間：2016-05-31 16:35:45 閱讀次數：2537次
題意:
有n個怪獸，m個武器，每一個武器能打哪些怪獸的關系已給出，每一個武器在1s內可以打多少血量已給出，每一個怪獸有多少血量已給出。
求怪獸團滅的最小時間。
解析:
一樣是1道答案存在單調性的題目。
所以我們可以斟酌2分答案后，每次重新構建1次圖。
修改的地方其實就是原點到每一個武器的流量（即2分的答案時間內該武器最多能打血）和將上1次跑過的圖復原。
最后判斷最大流是不是等于怪獸總血量便可。
注意浮點數相等判斷。
代碼:
#include #include #include #include #include #include #define N 55 #define INF 0x3f3f3f3f #define eps 1e⑻ using namespace std; int n,m; int head[3*N],cnt; double sum; struct node
{ int from,to,next; double val;
}edge[(N*N)<<2]; double b[N]; void init()
{ memset(head,-1,sizeof(head));
} void edgeadd(int from,int to,double val)
{
edge[cnt].from=from,edge[cnt].to=to,edge[cnt].val=val;
edge[cnt].next=head[from];
head[from]=cnt++;
} double dis[N*3]; int dep[N*3]; int S,T; int bfs()
{ memset(dep,0,sizeof(dep)); queue<int>q;
q.push(S);
dep[S]=1; while(!q.empty())
{ int u=q.front();
q.pop(); for(int i=head[u];i!=-1;i=edge[i].next)
{ int to=edge[i].to; if(dep[to]!=0||fabs(edge[i].val)continue;
dep[to]=dep[u]+1;
q.push(to);
}
} return dep[T]?1:0;
} double dfs(int now,double max_vale)
{ double ret=0; if(now==T)return max_vale; for(int i=head[now];i!=-1;i=edge[i].next)
{ int to=edge[i].to; if(dep[to]!=dep[now]+1||fabs(edge[i].val)continue; double tmp=dfs(to,min(max_vale-ret,edge[i].val));
ret+=tmp;
edge[i].val-=tmp;
edge[i^1].val+=tmp; if(fabs(ret-max_vale)return max_vale;
} return ret;
} bool check(double mid)
{ for(int i=0;i2)
edge[i].val+=edge[i^1].val,edge[i^1].val=0; for(int i=head[S];i!=-1;i=edge[i].next)
edge[i].val=b[edge[i].to-n]*mid; double ret=0; while(bfs())
{ while(double t=dfs(S,INF))
{
ret+=t;
}
} if(fabs(ret-sum)return 1; return 0;
} int main()
{
init(); scanf("%d%d",&n,&m);
S=0,T=n+m+1; for(int i=1;i<=n;i++) { int x; scanf("%d",&x);
edgeadd(i,T,x);
edgeadd(T,i,0);
sum+=x;
} for(int i=1;i<=m;i++) { scanf("%lf",&b[i]);
edgeadd(S,n+i,INF);
edgeadd(n+i,S,0);
} for(int i=1;i<=m;i++) { for(int j=1;j<=n;j++) { int jd; scanf("%d",&jd); if(jd)
{
edgeadd(n+i,j,INF);
edgeadd(j,n+i,0);
}
}
} double l=0,r=INF; double ans=l; while(r-l>eps)
{ double mid=(l+r)/2.0; if(check(mid))ans=mid,r=mid; else l=mid;
} printf("%lf
",ans);
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
