bzoj 1778: [Usaco2010 Hol]Dotp 驱逐猪猡【dp+高斯消元】

算是比较经典的高斯消元应用了

设f[i]为i点答案，那么dp转移为f[u]=Σf[v]*(1-p/q)/d[v]，意思是在u点爆炸可以从与u相连的v点转移过来

然后因为所有f都是未知数，高斯消元即可（记得输出大难的时候除以总概率和）

#include<iostream>

#include<cstdio>

using namespace std;

const int N=305;

int n,m,d[N],h[N],cnt;

double a[N][N],f[N],p,q,ans;

struct qwe

{

	int ne,to;

}e[N*N*2];

int read()

{

	int r=0,f=1;

	char p=getchar();

	while(p>'9'||p<'0')

	{

		if(p=='-')

			f=-1;

		p=getchar();

	}

	while(p>='0'&&p<='9')

	{

		r=r*10+p-48;

		p=getchar();

	}

	return r*f;

}

int add(int u,int v)

{

	cnt++;

	d[u]++;

	e[cnt].ne=h[u];

	e[cnt].to=v;

	h[u]=cnt;

}

void gaosi()

{

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

	{

		int nw=i;

		for(int j=i+1;j<=n;j++)

			if(a[j][i]>a[nw][i])

				nw=j;

		for(int j=i;j<=n+1;j++)

			swap(a[i][j],a[nw][j]);

		for(int j=i+1;j<=n+1;j++)

			a[i][j]/=a[i][i];

		a[i][i]=1;

		for(int j=i+1;j<=n;j++)

		{

			for(int k=i+1;k<=n+1;k++)

				a[j][k]-=a[j][i]*a[i][k];

			a[j][i]=0;

		}

	}

	// for(int i=1;i<=n;i++)

    // {

        // int nw=i;

        // for(int j=i;j<=n;j++)

			// if(a[j][i]>a[nw][i])

				// nw=j;

        // if(nw!=i)

			// for(int j=i;j<=n+1;j++)

				// swap(a[nw][j],a[i][j]);

        // for(int j=i+1;j<=n;j++)

        // {

            // double t=a[j][i]/a[i][i];

            // for(int k=i;k<=n+1;k++)

				// a[j][k]-=t*a[i][k];

        // }

    // }

	for(int i=n;i>=1;i--)

	{

		for(int j=n;j>i;j--)

			a[i][n+1]-=f[j]*a[i][j];

		f[i]=a[i][n+1]/a[i][i];

	}

}

int main()

{

	n=read(),m=read(),p=read(),q=read();

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

	{

		int x=read(),y=read();

		add(x,y),add(y,x);

	}

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

	{

		a[i][i]+=1;

		for(int j=h[i];j;j=e[j].ne)

			a[e[j].to][i]-=(1-p/q)/d[i];

	}

	a[1][n+1]+=1-p/q;

	gaosi();

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

		ans+=f[i];

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

		printf("%.9lf\n",f[i]/ans);

	return 0;

}

巴特西

bzoj 1778: [Usaco2010 Hol]Dotp 驱逐猪猡【dp+高斯消元】

最新文章

热门文章