BZOJ 1016: [JSOI2008]最小生成树计数

求一个无向图(n,m)的生成树数可以构造下面一个矩阵
矩阵大小:(n * n)
对于一个位置(i,j)
如果i==j则上面的数为点i的度数
否则为i到j的边数的相反数
如一个图1<->2,2<->3点数为3
则矩阵为
1 -1 0
-1 2 -1
0 -1 1
吧这个矩阵的第i行和第i列去掉(1<=i<=n i取任意值都可) 然后叫这个剩下来的矩阵n-1阶余子式 求这个矩阵的行列式的绝对值即为该图的生成树数 (我不知道行列式是什么啊QAQ 我就只知道能这么用QvQ 虽然听起来不像是一个值 但是就这么用吧QvQ) 求一个矩阵的行列式就是先用高斯消元把这个矩阵消成上三角矩阵 然后ans=π(f[i][i]) 对于求生成树数这个矩阵 ans最后会是一个整数 但是中间步骤可能是小数 最小生成树计数怎么做呢=、= 先把边按权值从小到大排序 从小到大遍历 对于边权相同的一些边取出来 对于这些边的每个联通子图求生成树数(自环要无视) ans=π每个联通子图求生成树数 最后把每个联通块用并查集分别并为一个点 然后再做下一个边权的边集即可 这题的ans可能很大 如果直接开double或long double都可能爆(其实long double不会=-=) 这题有mod一个数 如果可以让ans中间过程也是整数就非常好 考虑对一个矩阵的某行减掉某行的某倍 这个矩阵的行列式是不会变的 则我们可以用一个类似辗转相除的方法 让这个矩阵在保证每个元素仍是整数的情况下变为上三角矩阵(详见代码) 【周冬《生成树的计数及其应用》】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <vector>
#include <functional>
#include <ctime>
#include <cstdlib>
#include <sstream>
#include <set>
#include <deque>
using namespace std;
typedef long long ll;
typedef long double ld;

const ll inf = 31011;
const ll maxn = 105;

struct lin
{
    ll fr, to, v;
}p[10005];

struct line
{
    ll next, to;
}li[10005];

ll be[maxn], fa[maxn], l, to[maxn], tot, ans, n, m;
ll v[maxn][maxn];
queue<ll> q;

bool cmp(lin a, lin b)
{
    return a.v < b.v;
}

void makeline(ll fr, ll to)
{
    ++l;
    li[l].next = be[fr];
    be[fr] = l;
    li[l].to = to;
}

ll bfs(ll now)
{
    for (to[now] = tot = 1, v[1][1] = 0, q.push(now); !q.empty(); )
    {
        ll now = q.front();
        q.pop();
        for (ll i = be[now]; i; i = li[i].next)
        {
            ll _to = li[i].to;
            if (_to == now) continue;
            if (!to[_to])
            {
                to[_to] = ++tot;
                for (ll j = 1; j <= tot; ++j)
                    v[j][tot] = v[tot][j] = 0;
                q.push(_to);
            }
            v[to[now]][to[now]] += 1;
            v[to[now]][to[_to]] -= 1;
        }
    }
    if (tot == 1) return 1;
    ll ans = 1;
    for (ll i = 1; i < tot; ++i)
    {
        if (!v[i][i])
        {
            ll ans = -1;
            for (ll j = i + 1; j < tot; ++j)
                if (ans == -1 || abs(v[j][i]) > abs(v[ans][i]))
                    ans = j;
            for (ll j = i; j < tot; ++j)
                swap(v[i][j], v[ans][j]);
        }
        for (ll j = i + 1; j < tot; ++j)
            while (v[j][i])
            {
                ll t = v[i][i] / v[j][i];
                for (ll k = i; k < tot; ++k)
                    v[i][k] -= t * v[j][k],
                    swap(v[j][k], v[i][k]);
            }
        ans = (ans * v[i][i]) % inf;
    }
    return ans % inf;
}

ll getfa(ll now)
{
    return (!fa[now]) ? now : fa[now] = getfa(fa[now]);
}

int main()
{
    ans = 1;
    scanf("%lld%lld", &n, &m);
    for (ll i = 0; i < m; ++i)
        scanf("%lld%lld%lld", &p[i].fr, &p[i].to, &p[i].v);
    sort(p, p + m, cmp);
    ans = 1;
    for (ll i = 0; i < m;)
    {
        l = 0;
        memset(be, 0, sizeof(be));
        memset(to, 0, sizeof(to));
        ll j;
        for (j = i; j < m && p[i].v == p[j].v; ++j)
            makeline(getfa(p[j].fr), getfa(p[j].to)),
            makeline(getfa(p[j].to), getfa(p[j].fr));
        ll t = j;
        for (ll j = 1; j <= n; ++j)
            if (!to[getfa(j)])
                ans = (ans * bfs(getfa(j))) % inf;
        for (ll j = i; j < t; ++j)
            if (getfa(p[j].fr) != getfa(p[j].to))
                fa[getfa(p[j].fr)] = getfa(p[j].to);
        i = t;
    }
    for (int i = 1; i <= n; ++i)
        if (getfa(i) != getfa(1))
        {
            cout << 0;
            return 0;
        }
    cout << abs(ans);
}

博物馆(museum)

这题求的是到某个点为终点的概率
以某个点为终点的概率可以是这个状态被进入的期望次数
即f[i][j]表示第一个人到i点 第二个人到j点的进入这个状态的期望次数
12
p是停留在某个点的概率 d是某个点的度数 S1 S2是初始状态
这个方程有环
所以用高斯消元做
把每个fij看成一个元 拿去解方程 即可出解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <vector>
#include <functional>
#include <ctime>
#include <cstdlib>
#include <sstream>
#include <set>
#include <deque>
using namespace std;
typedef long long ll;
typedef long double ld;

struct line
{
    int to, next;
}li[1005];

int n, m, a, b, be[25], d[25], to[1005][2], fr[25][25], tot, l;
double p[25], v[405][405], ans[405];

void makeline(int fr, int to)
{
    ++l;
    li[l].next = be[fr];
    be[fr] = l;
    li[l].to = to;
}

int main()
{
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
    scanf("%d%d%d%d", &n, &m, &a, &b);
    for (int i = 0; i < m; ++i)
    {
        int fr, to;
        scanf("%d%d", &fr, &to);
        makeline(fr, to);
        makeline(to, fr);
        ++d[fr], ++d[to];
    }
    for (int i = 1; i <= n; ++i)
        scanf("%lf", &p[i]);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
        {
            fr[i][j] = tot;
            to[tot][0] = i, to[tot][1] = j;
            ++tot;
        }
    for (int i = 0; i < tot; ++i)
    {
        int u1 = to[i][0], u2 = to[i][1];
        v[i][i] = -1 ;
        if (u1 == u2) continue;
        v[i][i] += p[u1] * p[u2];
        double va1 = p[u1] * (1 - p[u2]) / d[u2],
                     va2 = (1 - p[u1]) * p[u2] / d[u1],
                     va = (1 - p[u1]) * (1 - p[u2]) / d[u1] / d[u2];

        for (int j1 = be[u2]; j1; j1 = li[j1].next)
            v[fr[u1][li[j1].to]][i] = va1;

        for (int j1 = be[u1]; j1; j1 = li[j1].next)
            v[fr[li[j1].to][u2]][i] = va2;

        for (int j1 = be[u1]; j1; j1 = li[j1].next)
            for (int j2 = be[u2]; j2; j2 = li[j2].next)
                v[fr[li[j1].to][li[j2].to]][i] = va;
    }
    v[fr[a][b]][tot] = -1;/*
    for (int i = 0; i < tot; ++i)
    {
        for (int j = 0; j <= tot; ++j) printf("%.2f ", v[i][j]);
        printf("\n");
    }*/

    for (int i = 0; i < tot; ++i)
    {
        int t = -1;
        for (int j = i; j < tot; ++j)
            if (t == -1 || abs(v[j][i]) > abs(v[t][i]))
                t = j;
        for (int j = 0; j <= tot; ++j)
            swap(v[i][j], v[t][j]);
        for (int j = i + 1; j < tot; ++j)
        {
            double va = v[j][i] / v[i][i];
            for (int k = i; k <= tot; ++k)
                v[j][k] -= va * v[i][k];
        }
    }
    for (int i = tot - 1; i >= 0; --i)
    {
        for (int j = i + 1; j < tot; ++j)
            v[i][tot] -= ans[j] * v[i][j];
        ans[i] = v[i][tot] / v[i][i];
    }/*
    for (int i = 0; i < tot; ++i)
        printf("%.6f ", ans[i]);
        printf("\n");*/

    for (int i = 1; i <= n; ++i)
        printf("%.6f ", ans[fr[i][i]] + 1e-8);
    fclose(stdin);fclose(stdout);
}

BZOJ 2115: [Wc2011] Xor

首先可以证明 一条从起点到终点的路径可以拆成一条从起点到终点的简单路径+一些环
只要是在图上的环 都可以选择取或不取
因为可以走到某个点 绕环一圈 然后回到起点
这样的话 就只要对每个环进行消元(求基?线性无关?什么什么的= =
然后随便找一条从起点到终点的简单路径(可以证明随便找一条都可以
在那个求出来的数组里贪心的消一消 遇0就消 然后就是答案

具体做法可以dfs 无向图的dfs树只有返祖边 一条返祖边对应一个环
每个点记录dfs树上根到这个点xor和即可
环的权=sum[now] ^ sum[to] ^ v[now][to]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <vector>
#include <functional>
#include <ctime>
#include <cstdlib>
#include <sstream>
#include <set>
#include <deque>
using namespace std;
typedef long long ll;
typedef long double ld;

const ll maxn = 50006;

struct line
{
    ll to, next, v;
}li[maxn * 4];

ll be[maxn], n, m, t[105], d[maxn], l, b[maxn];

void makeline(ll fr, ll to, ll v)
{
    ++l;
    li[l].next = be[fr];
    be[fr] = l;
    li[l].to = to;
    li[l].v = v;
}

void add(ll v)
{
    for (ll i = 61; i >= 0; --i)
        if (v & (1LL << i)) v ^= t[i];
    for (ll i = 61; i >= 0; --i)
        if (v & (1LL << i))
        {
            t[i] = v;
            break;
        }
}

void dfs(ll now)
{
    for (ll i = be[now]; i; i = li[i].next)
    {
        ll to = li[i].to;
        if (b[to])
            add(d[now] ^ d[to] ^ li[i].v);
        else
        {
            d[to] = d[now] ^ li[i].v;
            b[to] = 1;
            dfs(to);
        }
    }
}

int main()
{
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
    scanf("%lld%lld", &n, &m);
    for (ll i = 0; i < m; ++i)
    {
        ll fr, to, v;
        scanf("%lld%lld%lld", &fr, &to, &v);
        makeline(fr, to, v);
        makeline(to, fr, v);
    }
    b[1] = 1;
    dfs(1);
    for (ll i = 61; i >= 0; --i)
        if (!(d[n] & (1LL << i)))
            d[n] ^= t[i];
    cout << d[n];
    fclose(stdin);fclose(stdout);
}

全国互虐 TEST 5.31【魔法】

首先 可以证明
一条路径是由一大堆环和一条从1到某个点的链组成的
对于图上的所有环 对于某条链 都可以选或不选
即环和链的选择是独立的
如果现在有cnt个本质不同的环
和ccnt个本质不同的链
答案就是ccnt * 2^(cnt) – 1
因为对于每条链 所有环都可以选或不选
然后减掉0的情况

所谓本质相同的环a,b
就是把a任意异或其他环 得出的答案集合A
和把b任意异或其他环 得出的答案集合B是相同的
则他们本质相同
排除这种情况 只要对他们进行高斯消元 排除掉0的值就行了

本质相同的链的定义类似 两条链在环中进行高斯消元后 如果答案一样 则本质相同

然后就可以算出ans了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <vector>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <stack>
#include <iostream>
#include <algorithm>
#include <string>
#include <functional>
#include <sstream>
using namespace std;
typedef long long ll;
typedef long double ld;

const ll maxn = 100005;

struct line
{
  ll to, next, v;
}li[maxn];

struct Line
{
  ll fr, to, v;
}L[maxn];

ll a[maxn], v[maxn], c[maxn], b[maxn], n, m, q, be[maxn], l, ans[maxn], Q[maxn], f[maxn], cnt, ccnt, r[maxn];
set<ll> s;

void dfs(ll now, ll la)
{
  f[now] = la;
  c[++ccnt] = la;
  v[now] = 1;
  for (ll i = be[now]; i; i = li[i].next)
  {
    ll to = li[i].to;
    if (v[to]) a[++cnt] = f[now] ^ f[to] ^ li[i].v;
    else dfs(to, la ^ li[i].v);
  }  
}

ll re(ll v)
{
  for (ll i = 62; i >= 0; --i)
    if (v & (1LL << i)) v ^= r[i];
  return v;
}

ll calc()
{
  for (ll i = 1; i <= cnt; ++i) b[i] = 0;
  for (ll i = 62; i >= 0; --i)
  {
    ll p = 0;
    for (ll j = 1; j <= cnt; ++j)
      if (!b[j] && (a[j] & (1LL << i)))
      {
        p = j;
        break;          
      }
    if (!p)
    {
      r[i] = 0;
      continue;      
    }
    r[i] = a[p]; b[p] = 1;
    for (ll j = 1; j <= cnt; ++j)
      if (p != j && a[j] & (1LL << i)) a[j] ^= a[p];
  }
  ll cur = 0;
  for (ll i = 1; i <= cnt; ++i)
    if (a[i]) a[++cur] = a[i];
  cnt = cur;
  s.clear();
  cur = 0;
  for (ll i = 1; i <= ccnt; ++i)
  {
    ll t = re(c[i]);
    if (s.find(t) == s.end())
    {
      s.insert(t);
      c[++cur] = c[i];          
    }
  }
  ccnt = cur;
  return ccnt * (1LL << cnt) - 1;
}

void makeline(ll fr, ll to, ll v)
{
  ++l;
  li[l].next = be[fr];
  be[fr] = l;
  li[l].to = to;
  li[l].v = v;    
}

int main()
{
  scanf("%lld%lld%lld", &n, &m, &q);
  for (ll i = 1; i <= m; ++i)
    scanf("%lld%lld%lld", &L[i].fr, &L[i].to, &L[i].v);
  for (ll i = 0; i < q; ++i) scanf("%lld", &Q[i]), b[Q[i]] = 1;
  for (ll i = 1; i <= m; ++i)
    if (!b[i])
    {
      makeline(L[i].fr, L[i].to, L[i].v);
      makeline(L[i].to, L[i].fr, L[i].v);
    }
  dfs(1, 0);
  ans[q] = calc();
  for (ll i = q - 1; i >= 0; --i)
  {
    ll fr = L[Q[i]].fr, to = L[Q[i]].to, V = L[Q[i]].v;
    makeline(fr, to, V);
    makeline(to, fr, V);
    if (v[fr] && v[to]) a[++cnt] = f[fr] ^ f[to] ^ V;
    else if (v[fr]) dfs(to, f[fr] ^ V);
    else if (v[to]) dfs(fr, f[to] ^ V);
    ans[i] = calc();
  }
  for (ll i = 0; i <= q; ++i) printf("%lld\n", ans[i]);
}

BZOJ 1013: [JSOI2008]sphere

给n维空间一个圆的圆周上的n+1点 求圆心
设这个圆心的坐标是一个n元组(a1,a2,a3,..,an)
半径为r
n点坐标为(bi1,..,bin)
————-
距离:设两个n为空间上的点A, B的坐标为(a1, a2, …, an), (b1, b2, …, bn),则AB的距离定义为:dist = sqrt( (a1-b1)^2 + (a2-b2)^2 + … + (an-bn)^2 )
————-
可列出n+1个方程
sqr(a1 –  b11) + … = sqr(r)



化开后用分别减后一个可得n个一次方程 :
(2*b21 – 2*b11) a1 + … + b11^2 – b21^2… = 0


用高斯消元解之即可

高斯消元步骤:
考虑是n元的n个方程 其他类似
————————-

1
&nbsp;&nbsp;
1
for
1
(
1
int
1
i = 0; i &lt; n; ++i)//用第i个方程消除i+1~n方程中第i个未知数的系数
1
&nbsp;&nbsp;
1
{
1
&nbsp;&nbsp;&nbsp;&nbsp;
1
int
1
k = i;
1
&nbsp;&nbsp;&nbsp;&nbsp;
1
double
1
mx =
1
abs
1
(f[i][i]);
1
&nbsp;&nbsp;&nbsp;&nbsp;
1
for
1
(
1
int
1
j = i + 1; j &lt; n; ++j)
1
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
1
if
1
(mx &lt;
1
abs
1
(f[j][i]))
1
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
1
{
1
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
1
mx =
1
abs
1
(f[j][i]);
1
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
1
k = j;
1
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
1
}
1
&nbsp;&nbsp;&nbsp;&nbsp;
1
for
1
(
1
int
1
2
j = 0; j &lt;= n; ++j) swap(f[i][j], f[k][j]);
//把i~n中第i个未知数系数绝对值最大的换到第i个 用这个去消其他的 可以减少误差
1
&nbsp;&nbsp;&nbsp;&nbsp;
1
for
1
(
1
int
1
j = i + 1; j &lt; n; ++j)
1
&nbsp;&nbsp;&nbsp;&nbsp;
1
{
1
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
1
double
1
t = f[j][i] / f[i][i];
1
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
1
for
1
(
1
int
1
k = i + 1; k &lt;= n; ++k) f[j][k] -= f[i][k] * t;
1
&nbsp;&nbsp;&nbsp;&nbsp;
1
2
}
//消。。。
1
&nbsp;&nbsp;
1
}

————————-
然后求未知数就倒着一个个求上来就行了、
————————-

1
&nbsp;&nbsp;
1
for
1
(
1
int
1
i = n - 1; i &gt;= 0; --i)
1
&nbsp;&nbsp;
1
{
1
&nbsp;&nbsp;&nbsp;&nbsp;
1
for
1
(
1
int
1
j = i + 1; j &lt; n; ++j) f[i][n] += ans[j] * f[i][j];
1
&nbsp;&nbsp;&nbsp;&nbsp;
1
ans[i] = -f[i][n] / f[i][i];
1
&nbsp;&nbsp;
1
}
1
&nbsp;&nbsp;
1
for
1
(
1
int
1
i = 0; i &lt; n - 1; ++i)
1
printf
1
(
1
"%.3f "
1
, ans[i]);

————————-
高斯消元在某些地方循环变量限制是<n 某些是<=n 我弄混了好几次= =。。
ps.
无解:就是出现某一行有(0,0,…,a)(a <> 0)的情况 这样就无解
无穷解:在处理第i个未知数的系数时 发现i~n的第i个未知数的系数都为0 则第i个未知数无穷解
——————code—————-

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <vector>
#include <functional>
#include <ctime>
#include <cstdlib>
#include <sstream>
#include <set>
using namespace std;
typedef long long ll;
 
double a[15][15], f[15][15], ans[15];
int n;
 
int main()
{
  scanf(“%d”, &n);
  for (int i = 0; i <= n; ++i)
    for (int j = 0; j < n; ++j) scanf(“%lf”, &a[i][j]);
 
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < n; ++j)
      f[i][j] = 2 * a[i + 1][j] – 2 * a[i][j],
      f[i][n] += a[i][j] * a[i][j] – a[i + 1][j] * a[i + 1][j];
 
  for (int i = 0; i < n; ++i)
  {
    int k = i;
    double mx = abs(f[i][i]);
    for (int j = i + 1; j < n; ++j)
      if (mx < abs(f[j][i]))
      {
        mx = abs(f[j][i]);
        k = j;
      }
    for (int j = 0; j <= n; ++j) swap(f[i][j], f[k][j]);
    for (int j = i + 1; j < n; ++j)
    {
      double t = f[j][i] / f[i][i];
      for (int k = i + 1; k <= n; ++k) f[j][k] -= f[i][k] * t;
    }
  }
 
  for (int i = n – 1; i >= 0; –i)
  {
    for (int j = i + 1; j < n; ++j) f[i][n] += ans[j] * f[i][j];
    ans[i] = -f[i][n] / f[i][i];
  }
  for (int i = 0; i < n – 1; ++i) printf(“%.3f “, ans[i]);
  printf(“%.3f”, ans[n – 1]);

}