Loading...

SP104 HIGH - Highways

check评论:0 条 remove_red_eye浏览量:43 change_historyTags:默认分类
作者 : deco date_range日期 : 2019-11-18

链接

矩阵树定理裸题

我们搞出基尔霍夫矩阵后,直接删除第$n$行和第$n$列即可,然后辗转相除的方法求值可以减少精度误差

但好像是$O(n^3logn)$的?QAQ不管了

/*  Never Island  */
/*deco loves Chino*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
int T;
int n,m;
int d[13][13],t[13][13],kk[13][13];
signed main()
{
    cin>>T;
    while(T--)
    {
        cin>>n>>m;
        memset(t,0,sizeof(d));
        memset(d,0,sizeof(t));
        int ans=1;
        for(int i=1;i<=m;i++)
        {
            int x,y;
            scanf("%lld%lld",&x,&y);
            d[x][x]++,d[y][y]++;
            t[x][y]++,t[y][x]++;
        }
        for(int i=1;i<n;i++)
        {
            for(int j=1;j<n;j++)
            {
                kk[i][j]=d[i][j]-t[i][j];
            }
        }
        for(int i=1;i<n;i++)
        {
            for(int j=i+1;j<n;j++)
            {
                while(kk[j][i])
                {
                    int tt=kk[i][i]/kk[j][i];
                    for(int k=i;k<n;k++)
                    {
                        kk[i][k]=kk[i][k]-tt*kk[j][k];
                    }
                    swap(kk[i],kk[j]);
                    ans=-ans;
                }
            }
            ans*=kk[i][i];
        }
        cout<<ans<<"\n";
    }
    return 0;
}

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名