In this HackerRank Alex vs Fedor problem solution, We consider two trees different if the sets of the numbers of edges that are included in these trees are different. We consider two sets A and B different if there is at least one element that is present in A and not present in B or vice versa.
We should also mention that the graphs with an enormous number of spanning trees upset Alex, as well as Fedor, so they will never have a graph that has more than 10 to power 18 spanning trees.
At some point, Fedor became too lazy to look for minimal spanning trees and now he just picks some arbitrary spanning tree from Alex's graph. Each spanning tree has an equal probability to be picked by Fedor. What is the probability of Fedor's victory now?
Problem solution in Python.
#!/bin/python3
import os
import sys
from decimal import *
#
# Complete the alexFedor function below.
#
#
# For the weighted graph, <name>:
#
# 1. The number of nodes is <name>_nodes.
# 2. The number of edges is <name>_edges.
# 3. An edge exists between <name>_from[i] to <name>_to[i] and the weight of the edge is <name>_weight[i].
#
#
def alexFedor(graph_nodes, graph_from, graph_to, graph_weight):
#
# Write your code here.
#
getcontext().prec = 30
def gcd(x, y):
return gcd(y, x % y) if y else x
def find(x):
if x != pre[x]:
pre[x] = find(pre[x])
return pre[x]
def join(_x, _y):
pre[find(_x)] = find(_y)
def gauss(n0):
if n0 <= 1:
return 1
n0 -= 1
res = 1
d = [[0]*n0 for _ in range(n0)]
for i in range(n0):
for j in range(n0):
d[i][j] = Decimal(a[i][j])
for i in range(n0):
if d[i][i] == 0:
for j in range(i+1, n0):
if d[j][i] != 0:
for k in range(i,n0):
d[i][k], d[j][k] = d[j][k], d[i][k]
break
for j in range(i+1, n0):
tmp = d[j][i]
for k in range(n0):
d[j][k] -= d[i][k] / d[i][i] * tmp
res *= d[i][i]
return int(abs(res)+Decimal(0.5))
graph_from = [x-1 for x in graph_from]
graph_to = [x-1 for x in graph_to]
n, m = graph_nodes, len(graph_from)
#a = ([[0] * n]) * n
a = [[0] * n for _ in range(n)]
for i in range(m):
x, y = graph_from[i], graph_to[i]
a[x][x] += 1
a[y][y] += 1
a[x][y] -= 1
a[y][x] -= 1
al_count = gauss(n)
min_count = 1
idx = list(range(m))
pre = list(range(n))
idx.sort(key=lambda _x: graph_weight[_x])
l = 0
while l < m:
r = l + 1
while r < m and graph_weight[idx[l]] == graph_weight[idx[r]]:
r += 1
for i in range(l, r):
graph_from[idx[i]] = find(graph_from[idx[i]])
graph_to[idx[i]] = find(graph_to[idx[i]])
for i in range(l, r):
join(graph_from[idx[i]], graph_to[idx[i]])
idx[l:r] = sorted(idx[l:r], key=lambda _x: find(graph_from[_x]))
ll = l
while ll < r:
rr = ll + 1
while rr < r and find(graph_from[idx[ll]]) == find(graph_from[idx[rr]]):
rr += 1
# calculate ways with pathes id from ll to rr
v = [0] * n
for i in range(ll, rr):
v[graph_from[idx[i]]] = v[graph_to[idx[i]]] = 1
for i in range(1, n):
v[i] += v[i-1]
for i in range(v[-1]):
for j in range(v[-1]):
a[i][j] = 0
for i in range(ll, rr):
x, y = v[graph_from[idx[i]]] - 1, v[graph_to[idx[i]]] - 1
a[x][x] += 1
a[y][y] += 1
a[x][y] -= 1
a[y][x] -= 1
min_count *= gauss(v[-1])
ll = rr
l = r
for i in range(1, n):
if find(i) != find(0):
min_count = 0
_gcd = gcd(al_count, min_count)
if _gcd:
al_count //= _gcd
min_count //= _gcd
return str(min_count) + '/' + str(al_count)
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
graph_nodes, graph_edges = map(int, input().split())
graph_from = [0] * graph_edges
graph_to = [0] * graph_edges
graph_weight = [0] * graph_edges
for graph_itr in range(graph_edges):
graph_from[graph_itr], graph_to[graph_itr], graph_weight[graph_itr] = map(int, input().split())
result = alexFedor(graph_nodes, graph_from, graph_to, graph_weight)
fptr.write(result + '\n')
fptr.close()
Problem solution in Java.
import java.io.*;
import java.math.BigInteger;
import java.util.*;
public class Solution {
static class EdgeNode implements Comparable<EdgeNode> {
int u;
int v;
int w;
EdgeNode(int u, int v, int w) {
this.u = u;
this.v = v;
this.w = w;
}
@Override
public int compareTo(EdgeNode rhs) {
return w - rhs.w;
}
}
static class DisjointSet {
int[] p;
DisjointSet(int n) {
p = new int[n];
}
void clear() {
for (int i = 0; i < p.length; i++) {
p[i] = i;
}
}
int find(int x) {
if (x == p[x]) {
return x;
}
return p[x] = find(p[x]);
}
boolean join(int x, int y) {
x = find(x);
y = find(y);
if (x == y) {
return false;
}
p[x] = y;
return true;
}
}
static long getDet(long[][] a, int n) {
long ret = 1;
for (int i = 1; i <= n - 1; i++) {
for (int j = i + 1; j <= n - 1; j++) {
while (a[j][i] != 0) {
long t = a[i][i] / a[j][i];
for (int k = i; k <= n - 1; k++) {
a[i][k] -= a[j][k] * t;
}
for (int k = i; k <= n - 1; k++) {
long tmp = a[i][k];
a[i][k] = a[j][k];
a[j][k] = tmp;
}
ret = -ret;
}
}
if (a[i][i] == 0) {
return 0;
}
ret *= a[i][i];
}
return Math.abs(ret);
}
static void addEdgeToKmat(long[][] a, int x, int y) {
addEdgeToKmat(a, x, y, 1);
}
static void addEdgeToKmat(long[][] a, int x, int y, int cnt) {
a[x][x] += cnt;
a[y][y] += cnt;
a[x][y] -= cnt;
a[y][x] -= cnt;
}
static int[][] tmpGcnt;
static DisjointSet ds;
static DisjointSet dsTmp;
static boolean[] vis;
static long getMstCntOneBlock() {
Map<Integer, List<Integer> > blocks = new HashMap<>();
for (int i = 0; i < vis.length; i++) {
if (vis[i]) {
vis[i] = false;
int index = dsTmp.find(i);
List<Integer> l = blocks.get(index);
if (l == null) {
l = new ArrayList<>();
blocks.put(index, l);
}
l.add(i);
}
}
long ret = 1;
for (Map.Entry<Integer, List<Integer>> block : blocks.entrySet()) {
int len = block.getValue().size();
if (len <= 1) {
continue ;
}
List<Integer> l = block.getValue();
long[][] kmat = new long [tmpGcnt.length][tmpGcnt.length];
for (int x = 0; x < len; x++) {
for (int y = 0; y < x; y++) {
addEdgeToKmat(kmat, x, y, tmpGcnt[l.get(x)][l.get(y)]);
}
}
ret *= getDet(kmat, len);
for (int x = 0; x < len; x++) {
ds.p[l.get(x)] = block.getKey();
}
}
for (int i = 0; i < ds.p.length; i++) {
ds.p[i] = dsTmp.p[i] = ds.find(i);
}
return ret;
}
static long getMstCnt(EdgeNode[] edges) {
Arrays.sort(edges);
ds.clear();
dsTmp.clear();
Arrays.fill(vis, false);
for (int[] arr : tmpGcnt) {
Arrays.fill(arr, 0);
}
int preELen = -1;
long ret = 1;
for (int i = 0; i < edges.length; i++) {
if (preELen != edges[i].w) {
ret *= getMstCntOneBlock();
preELen = edges[i].w;
}
int pu = ds.find(edges[i].u);
int pv = ds.find(edges[i].v);
if (pu == pv) {
continue;
}
vis[pu] = vis[pv] = true;
dsTmp.join(pu, pv);
tmpGcnt[pu][pv] += 1;
tmpGcnt[pv][pu] += 1;
}
return ret * getMstCntOneBlock();
}
static long getStCnt(EdgeNode[] edges, int n) {
long[][] kmat = new long[n][n];
for (int i = 0; i < edges.length; i++) {
addEdgeToKmat(kmat, edges[i].u, edges[i].v);
}
return getDet(kmat, n);
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
StringTokenizer st = new StringTokenizer(br.readLine());
int graphNodes = Integer.parseInt(st.nextToken());
int graphEdges = Integer.parseInt(st.nextToken());
EdgeNode[] edges = new EdgeNode[graphEdges];
for (int i = 0; i < graphEdges; i++) {
st = new StringTokenizer(br.readLine());
int u = Integer.parseInt(st.nextToken())-1;
int v = Integer.parseInt(st.nextToken())-1;
int w = Integer.parseInt(st.nextToken());
edges[i] = new EdgeNode(u, v, w);
}
vis = new boolean[graphNodes];
ds = new DisjointSet(graphNodes);
dsTmp = new DisjointSet(graphNodes);
tmpGcnt = new int[graphNodes][graphNodes];
long mstCnt = getMstCnt(edges);
long stCnt = getStCnt(edges, graphNodes);
if (mstCnt == stCnt) {
bw.write("1/1");
} else {
long gcdAb = BigInteger.valueOf(mstCnt).gcd(BigInteger.valueOf(stCnt)).intValue();
bw.write((mstCnt / gcdAb) + "/" + (stCnt / gcdAb));
}
bw.newLine();
bw.close();
br.close();
}
}
Problem solution in C++.
#include <cmath>
#include <ctime>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <fstream>
#include <sstream>
#include <vector>
#include <string>
#include <bitset>
#include <queue>
#include <map>
#include <set>
using namespace std;
#define sz(x) ((int)((x).size()))
#define out(x) printf(#x" %d\n", x)
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define repf(i,a,b) for (int i = (a); i <= (b); ++i)
#define repd(i,a,b) for (int i = (a); i >= (b); --i)
#define repcase int t, Case = 1; for (scanf ("%d", &t); t; --t)
#define repeach(i,x) for (__typeof((x).begin()) i = (x).begin(); i != (x).end(); ++i)
typedef long long int64;
typedef pair<int, int> pii;
int sgn(double x) { return (x > 1e-8) - (x < -1e-8); }
int count_bit(int x) { return x == 0? 0 : count_bit(x >> 1) + (x & 1); }
template<class T> inline void ckmin(T &a, const T b) { if (b < a) a = b; }
template<class T> inline void ckmax(T &a, const T b) { if (b > a) a = b; }
const int MAXN = 100 + 10;
struct edge_node {
int u, v, w;
void input() {
scanf ("%d%d%d", &u, &v, &w);
--u, --v;
}
bool operator<(const edge_node& rhs) const {
return w < rhs.w;
}
};
struct disjoint_set {
int p[MAXN];
void clear(int n) { rep (i, n) p[i] = i; }
int find(int x) { return x == p[x]? x : p[x] = find(p[x]); }
bool join(int x, int y) { x = find(x), y = find(y); return x == y? false : p[x] = y, true; }
} ds, ds_tmp;
edge_node edges[MAXN];
int tmp_gcnt[MAXN][MAXN];
bool vis[MAXN];
int n, m;
int64 get_det(int64 a[][MAXN], int n) {
int64 ret = 1;
repf (i, 1, n - 1) {
repf (j, i + 1, n - 1) {
while (a[j][i]) {
int64 t = a[i][i] / a[j][i];
repf (k, i, n - 1) a[i][k] -= a[j][k] * t;
repf (k, i, n - 1) swap (a[i][k], a[j][k]);
ret = -ret;
}
}
if (a[i][i] == 0) return 0;
ret *= a[i][i];
}
return abs(ret);
}
void add_edge_to_kmat(int64 a[][MAXN], int x, int y, int cnt = 1) {
a[x][x] += cnt; a[y][y] += cnt;
a[x][y] -= cnt; a[y][x] -= cnt;
}
int64 get_mst_cnt_one_block() {
map<int, vector<int> > blocks;
rep (i, n) if (vis[i]) {
vis[i] = false;
blocks[ds_tmp.find(i)].push_back(i);
}
int64 ret = 1;
for (const auto& block : blocks) {
if (sz(block.second) <= 1) {
continue ;
}
int len = sz(block.second);
int64 kmat[MAXN][MAXN] = {0};
rep (x, len) rep (y, x) {
add_edge_to_kmat(kmat, x, y, tmp_gcnt[block.second[x]][block.second[y]]);
}
ret *= get_det(kmat, len);
rep (x, len) {
ds.p[block.second[x]] = block.first;
}
}
rep (i, n) {
ds.p[i] = ds_tmp.p[i] = ds.find(i);
}
return ret;
}
int64 get_mst_cnt() {
sort (edges, edges + m);
ds.clear(n), ds_tmp.clear(n);
memset (vis, 0, sizeof(vis));
memset (tmp_gcnt, 0, sizeof(tmp_gcnt));
int pre_e_len = -1;
int64 ret = 1;
rep (i, m) {
if (pre_e_len != edges[i].w) {
ret *= get_mst_cnt_one_block();
pre_e_len = edges[i].w;
}
int pu = ds.find(edges[i].u), pv = ds.find(edges[i].v);
if (pu == pv) {
continue;
}
vis[pu] = vis[pv] = true;
ds_tmp.join(pu, pv);
tmp_gcnt[pu][pv] += 1;
tmp_gcnt[pv][pu] += 1;
}
return ret * get_mst_cnt_one_block();
}
int64 get_st_cnt() {
int64 kmat[MAXN][MAXN] = {0};
rep (i, m) {
add_edge_to_kmat(kmat, edges[i].u, edges[i].v);
}
return get_det(kmat, n);
}
int main() {
while (scanf ("%d%d", &n, &m) != EOF) {
rep (i, m) {
edges[i].input();
}
int64 mst_cnt = get_mst_cnt();
int64 st_cnt = get_st_cnt();
int64 gcd_ab = __gcd(mst_cnt, st_cnt);
cout << mst_cnt / gcd_ab << '/' << st_cnt / gcd_ab << endl;
}
return 0;
}Problem solution in C.
#include<stdio.h>
#include<stdlib.h>
#define MOD 1000000000000000003LL
int N, M, mmst[100][100], *u, *v, *w, map[100];
long long aa[100][100][100][2];
unsigned long long CC(unsigned long long n, unsigned long long d)
{
while(1)
{
n %= d;
if( n == 0 )
{
return d;
}
d %= n;
if( d == 0 )
{
return n;
}
}
}
void merge3(int *a, int *left_a, int *right_a, int *b, int *left_b, int *right_b, int *c, int *left_c, int *right_c, int left_size, int right_size)
{
int i = 0, j = 0;
while( i < left_size || j < right_size )
{
if( i == left_size )
{
a[i + j] = right_a[j];
b[i + j] = right_b[j];
c[i + j] = right_c[j];
j++;
}
else if( j == right_size )
{
a[i + j] = left_a[i];
b[i + j] = left_b[i];
c[i + j] = left_c[i];
i++;
}
else if( left_a[i] <= right_a[j] )
{
a[i + j] = left_a[i];
b[i + j] = left_b[i];
c[i + j] = left_c[i];
i++;
}
else
{
a[i + j] = right_a[j];
b[i + j] = right_b[j];
c[i + j] = right_c[j];
j++;
}
}
return;
}
void sort_a3(int *a, int *b, int *c, int size)
{
if( size < 2 )
{
return;
}
int m = ( size + 1 ) / 2, i;
int *left_a, *left_b, *left_c, *right_a, *right_b, *right_c;
left_a = (int*)malloc(m * sizeof(int));
right_a = (int*)malloc(( size - m ) * sizeof(int));
left_b = (int*)malloc(m * sizeof(int));
right_b = (int*)malloc(( size - m ) * sizeof(int));
left_c = (int*)malloc(m * sizeof(int));
right_c = (int*)malloc(( size - m ) * sizeof(int));
for( i = 0 ; i < m ; i++ )
{
left_a[i] = a[i];
left_b[i] = b[i];
left_c[i] = c[i];
}
for( i = 0 ; i < size - m ; i++ )
{
right_a[i] = a[i + m];
right_b[i] = b[i + m];
right_c[i] = c[i + m];
}
sort_a3(left_a, left_b, left_c, m);
sort_a3(right_a, right_b, right_c, size - m);
merge3(a, left_a, right_a, b, left_b, right_b, c, left_c, right_c, m, size - m);
free(left_a);
free(right_a);
free(left_b);
free(right_b);
free(left_c);
free(right_c);
return;
}
long long mul(unsigned long long x, unsigned long long y)
{
unsigned long long a, b, c, d, A, B, C;
long long ans;
int i;
a = x / 1000000000;
b = x % 1000000000;
c = y / 1000000000;
d = y % 1000000000;
A = d * b % MOD;
B = ( d * a + c * b ) % MOD;
C = a * c % MOD;
for( i = 0 ; i < 9 ; i++ )
{
B = B * 10 % MOD;
}
for( i = 0 ; i < 18 ; i++ )
{
C = C * 10 % MOD;
}
ans = ( A + B + C ) % MOD;
return ans;
}
void lu(long long **a, long long **ml, long long **mu, long long **dl, long long **du, int n)
{
int i = 0, j = 0, k = 0;
long long t1, t2;
for( i = 0 ; i < n ; i++ )
{
for( j = 0 ; j < n ; j++ )
{
if( j < i )
{
ml[j][i] = 0;
dl[j][i] = 1;
}
else
{
ml[j][i] = a[j][i];
dl[j][i] = 1;
for( k = 0 ; k < i ; k++ )
{
t1 = mul(ml[j][k], mu[k][i]);
t2 = mul(dl[j][k], du[k][i]);
ml[j][i] = ( mul(ml[j][i], t2) - mul(t1, dl[j][i]) + MOD ) % MOD;
dl[j][i] = mul(dl[j][i], t2);
}
}
}
for( j = 0 ; j < n ; j++ )
{
if( j < i )
{
mu[i][j] = 0;
du[i][j] = 1;
}
else if( j == i )
{
mu[i][j] = 1;
du[i][j] = 1;
}
else
{
mu[i][j] = mul(a[i][j], dl[i][i]);
du[i][j] = ml[i][i];
for( k = 0 ; k < i ; k++ )
{
t1 = mul(mul(ml[i][k], mu[k][j]), dl[i][i]);
t2 = mul(mul(dl[i][k], du[k][j]), ml[i][i]);
mu[i][j] = ( mul(mu[i][j], t2) - mul(t1, du[i][j]) + MOD ) % MOD;
du[i][j] = mul(du[i][j], t2);
}
}
}
}
}
long long modInverse(long long a, long long mod)
{
long long b0 = mod, t, q, x0 = 0, x1 = 1;
while( a > 1 )
{
q = a / mod;
t = mod;
mod = a % mod;
a = t;
t = x0;
x0 = x1 - q * x0;
x1 = t;
}
if( x1 < 0 )
{
x1 += b0;
}
return x1;
}
long long det(long long **a, int n)
{
long long **ml, **mu, **dl, **du, ans = 1;
int i, j;
ml = (long long**)malloc(n * sizeof(long long*));
for( i = 0 ; i < n ; i++ )
{
ml[i] = (long long*)malloc(n * sizeof(long long));
}
mu = (long long**)malloc(n * sizeof(long long*));
for( i = 0 ; i < n ; i++ )
{
mu[i] = (long long*)malloc(n * sizeof(long long));
}
dl = (long long**)malloc(n * sizeof(long long*));
for( i = 0 ; i < n ; i++ )
{
dl[i] = (long long*)malloc(n * sizeof(long long));
}
du = (long long**)malloc(n * sizeof(long long*));
for( i = 0 ; i < n ; i++ )
{
du[i] = (long long*)malloc(n * sizeof(long long));
}
for( i = 0 ; i < n ; i++ )
{
for( j = 0 ; j < n ; j++ )
{
ml[i][j] = mu[i][j] = 0;
dl[i][j] = du[i][j] = 1;
a[i][j] = ( a[i][j] + MOD ) % MOD;
}
}
lu(a, ml, mu, dl, du, n);
for( i = 0 ; i < n ; i++ )
{
ans = mul(mul(ans, ml[i][i]), modInverse(dl[i][i], MOD));
}
for( i = 0 ; i < n ; i++ )
{
free(ml[i]);
free(mu[i]);
free(dl[i]);
free(du[i]);
}
free(ml);
free(mu);
free(dl);
free(du);
return ans;
}
unsigned long long MST()
{
unsigned long long ans = 0;
int i, j, p1, p2, p3, p4;
for( i = 0 ; i < N ; i++ )
{
for( j = 0 ; j < N ; j++ )
{
mmst[i][j] = 0;
}
}
int *p = (int*)malloc(N * sizeof(int));
for( i = 0 ; i < N ; i++ )
{
p[i] = i;
}
for( i = 0 ; i < M ; i++ )
{
p1 = u[i] - 1;
while( p[p1] != p1 )
{
p1 = p[p1];
}
p2 = v[i] - 1;
while( p[p2] != p2 )
{
p2 = p[p2];
}
if( p1 != p2 )
{
ans += w[i];
mmst[u[i] - 1][v[i] - 1] = 1;
mmst[v[i] - 1][u[i] - 1] = 1;
}
p3 = u[i] - 1;
while(1)
{
if( p[p3] == p3 )
{
p[p3] = p1;
break;
}
p4 = p3;
p3 = p[p3];
p[p4] = p1;
}
p3 = v[i] - 1;
while(1)
{
if( p[p3] == p3 )
{
p[p3] = p1;
break;
}
p4 = p3;
p3 = p[p3];
p[p4] = p1;
}
}
free(p);
return ans;
}
void dfs(int x, int p)
{
int i, j, k;
for( i = 0 ; i < N ; i++ )
{
if( mmst[x][i] && i != p )
{
dfs(i, x);
}
}
if( p != -1 && p != N - 1 )
{
for( i = 0 ; i < N - 1 ; i++ )
{
for( j = 0 ; j < N - 1 && aa[i][x][j][0] != -1 ; j++ )
{
for( k = 0 ; k < M ; k++ )
{
if( aa[i][p][k][0] == -1 || aa[i][p][k][0] == aa[i][x][j][0] )
{
aa[i][p][k][0] = aa[i][x][j][0];
aa[i][p][k][1] += aa[i][x][j][1];
break;
}
}
}
}
}
return;
}
int main()
{
int i, j, k, c = 0;
long long mst, tst, tmst, C, min, **a;
scanf("%d%d", &N, &M);
u = (int*)malloc(M * sizeof(int));
v = (int*)malloc(M * sizeof(int));
w = (int*)malloc(M * sizeof(int));
a = (long long**)malloc(N * sizeof(long long*));
for( i = 0 ; i < N ; i++ )
{
a[i] = (long long*)malloc(N * sizeof(long long));
}
for( i = 0 ; i < M ; i++ )
{
scanf("%d%d%d", u + i, v + i, w + i);
}
for( i = 0 ; i < 100 ; i++ )
{
map[i] = -1;
}
for( i = 0 ; i < M ; i++ )
{
if( map[u[i] - 1] == -1 )
{
map[u[i] - 1] = ++c;
}
if( map[v[i] - 1] == -1 )
{
map[v[i] - 1] = ++c;
}
u[i] = map[u[i] - 1];
v[i] = map[v[i] - 1];
}
sort_a3(w, u, v, M);
mst = MST();
for( i = 0 ; i < N - 1 ; i++ )
{
for( j = 0 ; j < N - 1 ; j++ )
{
a[i][j] = 0;
}
}
for( i = 0 ; i < M ; i++ )
{
if( u[i] != N )
{
a[u[i] - 1][u[i] - 1]++;
}
if( v[i] != N )
{
a[v[i] - 1][v[i] - 1]++;
}
if( u[i] != N && v[i] != N )
{
a[u[i] - 1][v[i] - 1]--;
a[v[i] - 1][u[i] - 1]--;
}
}
tst = det(a, N - 1);
for( i = 0 ; i < N - 1 ; i++ )
{
for( j = 0 ; j < N - 1 ; j++ )
{
for( k = 0 ; k < M ; k++ )
{
aa[i][j][k][0] = -1;
aa[i][j][k][1] = 0;
}
}
}
for( i = 0 ; i < M ; i++ )
{
if( u[i] != N )
{
for( j = 0 ; j < M ; j++ )
{
if( aa[u[i] - 1][u[i] - 1][j][0] == -1 || aa[u[i] - 1][u[i] - 1][j][0] == w[i] )
{
aa[u[i] - 1][u[i] - 1][j][0] = w[i];
aa[u[i] - 1][u[i] - 1][j][1]++;
break;
}
}
}
if( v[i] != N )
{
for( j = 0 ; j < M ; j++ )
{
if( aa[v[i] - 1][v[i] - 1][j][0] == -1 || aa[v[i] - 1][v[i] - 1][j][0] == w[i] )
{
aa[v[i] - 1][v[i] - 1][j][0] = w[i];
aa[v[i] - 1][v[i] - 1][j][1]++;
break;
}
}
}
if( u[i] != N && v[i] != N )
{
for( j = 0 ; j < M ; j++ )
{
if( aa[u[i] - 1][v[i] - 1][j][0] == -1 || aa[u[i] - 1][v[i] - 1][j][0] == w[i] )
{
aa[u[i] - 1][v[i] - 1][j][0] = w[i];
aa[u[i] - 1][v[i] - 1][j][1]--;
break;
}
}
for( j = 0 ; j < M ; j++ )
{
if( aa[v[i] - 1][u[i] - 1][j][0] == -1 || aa[v[i] - 1][u[i] - 1][j][0] == w[i] )
{
aa[v[i] - 1][u[i] - 1][j][0] = w[i];
aa[v[i] - 1][u[i] - 1][j][1]--;
break;
}
}
}
}
dfs(N - 1, -1);
for( j = 0 ; j < N - 1 ; j++ )
{
min = -1;
for( i = 0 ; i < N - 1 ; i++ )
{
for( k = 0 ; k < M && aa[i][j][k][0] != -1 ; k++ )
{
if( ( min == -1 || aa[i][j][k][0] < min ) && aa[i][j][k][1] )
{
min = aa[i][j][k][0];
}
}
}
for( i = 0 ; i < N - 1 ; i++ )
{
a[i][j] = 0;
for( k = 0 ; k < M && aa[i][j][k][0] != -1 ; k++ )
{
if( aa[i][j][k][0] == min )
{
a[i][j] = aa[i][j][k][1];
break;
}
}
}
}
tmst = det(a, N - 1);
C = CC(tst, tmst);
printf("%lld/%lld", tmst / C, tst / C);
return 0;
}
0 Comments