import java.io.*; import java.util.*; class Edge{ int o, t, a, b; public Edge(int o, int t, int a, int b){ this.o = o; this.t = t; this.a = a; this.b = b; } } public class Main{ static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); static final int N = 1010, mod = (int) 1e9 + 7; static int[] p = new int[N]; static int n, m; static int[][] c = new int[N][N]; static Edge[] edges; public static void initC(){ for (int i = 0; i < N; i ++ ) for (int j = 0; j <= i; j ++ ){ if (j == 0) c[i][j] = 1; else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod; } } public static int find(int u){ if (p[u] != u){ p[u] = find(p[u]); } return p[u]; } public static void union(int i, int j){ p[find(i)] = find(j); } public static void main(String[] args) throws IOException{ String[] ss = br.readLine().split(" "); n = Integer.parseInt(ss[0]); m = Integer.parseInt(ss[1]); edges = new Edge[m]; initC(); for (int i = 0; i <= n; i ++ ) p[i] = i; for (int i = 0 ; i < m; i ++ ){ String[] strs = br.readLine().split(" "); int o = Integer.parseInt(strs[0]), t = Integer.parseInt(strs[1]), a = Integer.parseInt(strs[2]), b = Integer.parseInt(strs[3]); edges[i] = new Edge(o, t, a, b); } Arrays.sort(edges, (x, y) -> { return c[y.a][y.b] - c[x.a][x.b]; }); int cnt = 0, ans = 0; for (int i = 0; i < m; i ++ ){ Edge e = edges[i]; if (find(e.o) == find(e.t)) continue; union(e.o, e.t); ans = (ans + c[e.a][e.b]) % mod; cnt ++ ; } if (cnt != (n - 1)) bw.write(-1 + ""); else bw.write(ans + ""); bw.flush(); } }

代码用一个裸并查集做的