[Ctsc2015]misc

https://lydsy.com/JudgeOnline/problem.php?id=4055

题解

观察题目要我们求的东西：

\[ans[k]=\sum_{i}\sum_j \frac{a_i*a_j*f_k[i][j]}{f[i][j]}
\]

然后我们可以先枚举i，然后对于那个带限制的最短路部分，我们可以把贡献拆成两部分来计算。

\[ans[k]=\sum_{i}a_i*f[i][k]\sum_j\frac{a_j*f[k][j]}{f[i][j]}
\]

由于我们还要满足最短路的限制，所以我们可以先对每个i建出以i为源点的最短路\(DAG\)然后再\(DAG\)上维护后面的求和就可以了，这样可以保证是合法的。

Warning

维护f数组时注意一开始为了转移将\(f[i][i]=1\)，最后做完了记得清空。

代码

#include<bits/stdc++.h>

#define N 1009

#define M 4009

#define mm make_pair

using namespace std;

typedef long long ll;

int head[N],tot,dis[N],du[N],n,m;

bool vis[N];

vector<int>vec[N];

vector<int>::iterator it;

priority_queue<pair<int,int> >q;

long double cnt[N][N],g[N],ans[N],a[N];

inline ll rd(){

	ll x=0;char c=getchar();bool f=0;

	while(!isdigit(c)){if(c=='-')f=1;c=getchar();}

	while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}

	return f?-x:x;

}

struct edge{

	int n,to,l;double f;

}e[M<<1];

inline void add(int u,int v,int l,double f){

	e[++tot].n=head[u];e[tot].to=v;head[u]=tot;e[tot].f=f;e[tot].l=l;

}

inline void link(int i,int u){

	vec[u].push_back(i);du[e[i].to]++;

}

inline void dij(int s){

	memset(dis,0x3f,sizeof(dis));

	memset(vis,0,sizeof(vis));

	q.push(mm(0,s));cnt[s][s]=1;dis[s]=0;

	while(!q.empty()){

		int u=q.top().second;q.pop();

		if(vis[u])continue;

		vis[u]=1;

		for(int i=head[u];i;i=e[i].n){

			int v=e[i].to;

			if(dis[v]>dis[u]+e[i].l){

				dis[v]=dis[u]+e[i].l;

				cnt[s][v]=cnt[s][u]*e[i].f;

			    q.push(mm(-dis[v],v));

			}

			else if(dis[v]==dis[u]+e[i].l)cnt[s][v]+=cnt[s][u]*e[i].f;

		}

	}

}

inline void topsort(int s){

	memset(g,0,sizeof(g));

	queue<int>q;

	for(int i=1;i<=n;++i)if(!du[i])q.push(i);

	while(!q.empty()){

		int u=q.front();q.pop();

		ans[u]+=a[s]*cnt[s][u]*g[u];

		g[u]+=a[u]/cnt[s][u];

		for(it=vec[u].begin();it!=vec[u].end();++it){

			int i=*it,v=e[i].to;

			if(!--du[v])q.push(v);

			g[v]+=g[u]*e[i].f;

		}

	}

}

int main(){

	n=rd();m=rd();

	for(int i=1;i<=n;++i)a[i]=rd();

	int u,v,l;double f;tot=1;

	for(int i=1;i<=m;++i){

		u=rd();v=rd();l=rd();scanf("%lf",&f);

		add(u,v,l,f);add(v,u,l,f);

	}

	for(int s=1;s<=n;++s){

		dij(s);

		cnt[s][s]=0;

		for(int u=1;u<=n;++u)

		  for(int i=head[u];i;i=e[i].n)if(dis[u]+e[i].l==dis[e[i].to])link(i^1,e[i].to);

		topsort(s);

		for(int u=1;u<=n;++u)vec[u].clear();

	}

	for(int i=1;i<=n;++i)printf("%.8Lf\n",ans[i]);

	return 0;

}

巴特西

[Ctsc2015]misc

题解

Warning

代码

最新文章

热门文章