BZOJ3270: 博物馆

类似之前usaco的那道题。。

可能简单一点 少几个变量。。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<iostream>
using namespace std;

char c;
inline void read(int&a)
{a=;do c=getchar();while(c<'0'||c>'9');
while(c<='9'&&c>='0')a=(a<<)+(a<<)+c-'0',c=getchar();}

int n,m,a,b;
#define no(x,y) ((x)*n+(y)-n)

struct Chain
{
    int u;
    Chain*next;
}*Head[];

inline void Add(int u,int v)
{
    Chain*tp=new Chain;
    tp->next=Head[u];Head[u]=tp;tp->u=v;
}

double T[][];
double I[][];
double A[][];
const
    double eps=e-;
void Gauss()
{
    int n=::n;
    n=n*n;
    for(int i=;i<=n;i++)
    {
        int j=-;
        for(int k=i;k<=n;k++)
            if(abs(T[k][i])>eps)
            {j=k;break;}
        for(int k=;k<=n;k++)
            swap(T[j][k],T[i][k]),swap(I[j][k],I[i][k]);
        for(int k=;k<=n;k++)
            if(i!=k)T[i][k]/=T[i][i],I[i][k]/=T[i][i];
        I[i][i]/=T[i][i];
        T[i][i]/=T[i][i];
        for(int j=i+;j<=n;j++)
            {
                double e=T[j][i];
                for(int k=;k<=n;k++)
                    T[j][k]-=T[i][k]*e,
                    I[j][k]-=I[i][k]*e;
            }
    }
    for(int i=n;i;i--)
    {
        for(int j=i-;j;j--)
            {
                for(int k=;k<=n;k++)
                    I[j][k]-=T[j][i]*I[i][k];
                T[j][i]-=T[j][i]*T[i][i];
            }   
    }

}

double F[];
int d[];


int main()
{
    read(n),read(m),read(a),read(b);
    while(m--)
    {
        int x,y;
        read(x),read(y);Add(x,y),Add(y,x);
        d[x]++;
        d[y]++;
    }
    for(int i=;i<=n;i++)
        scanf("%lf",F+i);
    for(int i=;i<=n;i++)
        for(int t=;t<=n;t++)
            if(i!=t)
                for(Chain*tp=Head[i];tp;tp=tp->next)
                    T[no(i,t)][no(tp->u,t)]+=F[t]*(-F[i])*1./d[i];

    for(int i=;i<=n;i++)
        for(int t=;t<=n;t++)
            if(i!=t)
                for(Chain*tp=Head[t];tp;tp=tp->next)
                    T[no(i,t)][no(i,tp->u)]+=F[i]*(-F[t])*1./d[t];
    for(int i=;i<=n;i++)
        for(int t=;t<=n;t++)
            if(i!=t)
                T[no(i,t)][no(i,t)]+=F[t]*F[i];
    for(int i=;i<=n;i++)
        for(int t=;t<=n;t++)
            if(i!=t)
                for(Chain*tp=Head[i];tp;tp=tp->next)
                    for(Chain*tp2=Head[t];tp2;tp2=tp2->next)
                        T[no(i,t)][no(tp->u,tp2->u)]+=(-F[t])*(-F[i])*1./d[i]/d[t];

    for(int i=;i<=n*n;i++)
        for(int t=;t<=n*n;t++) 
            if(i==t)T[i][t]=-T[i][t],I[i][t]=;
            else T[i][t]=-T[i][t];
        Gauss();
    for(int i=;i<=n;i++)
    {
        printf("%.6f ",I[no(a,b)][no(i,i)]);
    }
    return ;
}