终极情报网题解

首先建立源点和汇点，然后建一个辅助源点，让源点和辅助源点之间连一条流量为(k)，费用为(1)的边，表示最多增广(k)次。
接下来对于那些和总部联通的人，流量即为最大传递消息数量，费用为这次的安全程度。
对于任意(2)个能联系的人，按照相同的方法处理。
那些和敌军情报部门能联系的人和汇点连边，流量为(k)，费用也为(1)。
这样我们就初步建出了一张图，考虑最后的答案，设(F_{i,j})为(i,j)之间传递信息的实际数目，(S_{i,j})为(i,j)传递消息的安全程度，(A_i)为总部和这个点传递信息的数目，(P_i)为总部和这个点联系的安全程度，那么答案就是(max{prod_{i=1}^nprod_{j=1}^nS_{i,j}^{F_{i,j}}prod_{i=1}^nA_i^{P_i}})，我们考虑对边权取对数，那么最后的答案就化为了(min{sum_{i=1}^nsum_{j=1}^n(-F_{i,j} imes ln(S_{i,j}))+sum_{i=1}^n(-P_i imes ln{A_i})})。
现在问题就转化为了求和，可以用最小费用最大流求解。

#include <bits/stdc++.h>
#define eps 1e-12
int n,k;
int S=1,cloneS=2,T=3;
int Max_flow[301],call[301],vis[301],flow[301],last_edge[301];
double proA[301],dis[301];
int head[1000000],tot=1;
std::queue<int>q;
struct edge{
	int to;
	int nxt;
	int flow;
	double cost;
}e[1000000];
void add(int x,int y,int flow,double cost){
	e[++tot]={y,head[x],flow,cost};
	head[x]=tot;
	e[++tot]={x,head[y],0,-cost};
	head[y]=tot;
}
bool spfa(){
	for(int i=1;i<=n+3;++i){
	  dis[i]=-100;
	  vis[i]=0;
	}
	dis[S]=0;
	flow[S]=k;
	last_edge[S]=-1;
	q.push(S);
	while(!q.empty()){
		int x=q.front();
		q.pop();
		vis[x]=0;
		for(int i=head[x];i;i=e[i].nxt){
			int y=e[i].to;
			if(e[i].flow&&dis[y]+eps<dis[x]+e[i].cost){
				dis[y]=dis[x]+e[i].cost;
				flow[y]=std::min(e[i].flow,flow[x]);
				last_edge[y]=i;
				if(!vis[y]){
					vis[y]=1;
					q.push(y);
				}
			}
		}
	}
  if(fabs(dis[T]+100.0)<eps)
    return 0;
  return 1;
}
void deal(double ans){
  char ch[40];
  sprintf(ch,"%.15f
",ans);
  int sum=0,i;
  for(i=0;sum<5;i++)
    if((ch[i]!='0'&&ch[i]!='.')|sum>0)
      sum++;
  if(ch[i]>='5')
    ch[i-1]++;
  ch[i]=0;
  for(;i>=0;i--)
    if(ch[i]=='.')
		  break;
    else 
		  if(ch[i]>'9')
        ch[i-1]++,ch[i]='0';
  printf("%s
",ch);
}
void dinic(){
	int Flow=0;
	double cost=0;
	while(spfa()){
		cost+=dis[T]*flow[T];
		Flow+=flow[T];
		for(int i=last_edge[T];~i;i=last_edge[e[i^1].to]){
			e[i].flow-=flow[T];
			e[i^1].flow+=flow[T];
		}
	}
	if(Flow!=k){
		puts("0.00000000");
		return;
	}
	else{
		cost=std::exp(cost);
		deal(cost);
	}
}
main(){
	scanf("%d%d",&n,&k);
	add(S,cloneS,k,log(1.0));
	for(int i=1;i<=n;++i)
	  scanf("%lf",&proA[i]);
	for(int i=1;i<=n;++i){
	  scanf("%d",&Max_flow[i]);
	  if(proA[i])
	  	add(cloneS,i+3,Max_flow[i],log(proA[i]));
	}
	for(int i=1;i<=n;++i){
		scanf("%d",&call[i]);
		if(call[i])
		  add(i+3,T,k,log(1.0));
	}
	while(true){
		int spyA,spyB;
		double pro;
		int Maxflow;
		scanf("%d%d",&spyA,&spyB);
		if(spyA+spyB==-2)
		  break;
		scanf("%lf%d",&pro,&Maxflow);
		add(spyA+3,spyB+3,Maxflow,log(pro));
		add(spyB+3,spyA+3,Maxflow,log(pro));
	}
	dinic();
	return 0;
}

终极情报网 题解

相关推荐