题解 | #小美的修路#

这是最小生成树的变种，我们可以首先将的连接上，然后给剩余的边排序。需要注意排序后，索引信息回发生改变，需要保存好。然后依次检测联通性，如果不联通我们才连接。

连通性可以使用并查集来实现。

import sys
sys.setrecursionlimit(100010)
read = sys.stdin.readline

if __name__ == "__main__":
import sys
sys.setrecursionlimit(100010)
read = sys.stdin.readline

if __name__ == "__main__":
    n,m = map(int,read().split())
    fa = list(range(n))
    def find(x: int):
        if x != fa[x]:
            fa[x] = find(fa[x])
        return fa[x]
    edges = []
    vis = [False] * m
    for i in range(m):
        u,v,w,p = map(int,read().split())
        u -= 1
        v -= 1
        if p == 1:
            vis[i] = True
            f1 = find(u)
            f2 = find(v)
            fa[f1] = f2
        else:
            edges.append((w,u,v,i))
    edges.sort()
    for w,u,v,idx in edges:
        f1 = find(u)
        f2 = find(v)
        if f1 != f2:
            fa[f1] = f2
            vis[idx] = True
    cnt = 0
    for i in range(n):
        if i == find(i):
            cnt += 1
    if cnt > 1:
        print(-1)
        exit(0)
    print(sum(vis))
    for i in range(m):
        if vis[i]:
            print(i + 1,end = " ")
    print()