最便宜的构建

pypy3 解法, 执行用时: 2122ms, 内存消耗: 66732K, 提交时间: 2023-06-09 22:06:54

from sys import stdin
input=lambda:stdin.readline().strip()
n,m=map(int,input().split())
A=[]
MAX=0
for i in range(m):
    u,v,w=map(int,input().split())
    MAX=max(MAX,w)
    A.append((w,u,v))
A.sort(key=lambda x:x[0])
k=int(input())
L=[]
for i in range(k):
    temp=list(map(int,input().split()))
    L.append(temp[1:])
def find(x,node):
    if x==node[x]:
        return x
    node[x]=find(node[x],node)
    return node[x]
def check(mid):
    node=[i for i in range(n+1)]
    for w,u,v in A:
        if w>mid:
            break
        u=find(u,node)
        v=find(v,node)
        if u==v:continue
        if u>v:u,v=v,u
        node[v]=u
    for num in L:
        for i in range(1,len(num)):
            if find(num[i],node)!=find(num[i-1],node):
                return False
    return True
l=0
r=MAX
while l<r:
    mid=l+r>>1
    if check(mid):
        r=mid
    else:
        l=mid+1
print(l)

C++(clang++ 11.0.1) 解法, 执行用时: 339ms, 内存消耗: 27276K, 提交时间: 2023-06-18 19:03:24

#include<bits/stdc++.h>
using namespace std;

const int N = 1e6+10;

int n,m,k;
int p[N];

vector<int>v[N];

struct node{
	int a,b,w;
}e[N];

int find(int x)
{
	return x==p[x]?x:p[x]=find(p[x]);
}

int check(int mid)
{
	for(int i=1;i<=n;i++) p[i]=i;
	for(int i=1;i<=m;i++)
	{
		if(e[i].w>mid) continue;
		p[find(e[i].a)]=find(e[i].b);
	}
	for(int i=1;i<=k;i++)
	{
		int ans=find(v[i][0]);
		for(int j=0;j<v[i].size();j++)
			if(find(v[i][j])!=ans) return 0;
	}
	return 1;
}



int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int x,y,c;
		cin>>x>>y>>c;
	    e[i]={x,y,c};
	}
	cin>>k;
	for(int i=1;i<=k;i++)
	{
		int op;
		cin>>op;
		for(int j=1;j<=op;j++)
		{
			int x;
			cin>>x;
			v[i].push_back(x);
		}
	}
	int l=1,r=1e9;
	while(l<r)
	{
		int mid=(l+r)/2;
		if(check(mid)) r=mid;
		else l=mid+1;
	}
	cout<<l;
	
	return 0;
}

Python3 解法, 执行用时: 1811ms, 内存消耗: 37168K, 提交时间: 2023-06-25 17:27:59

ps = []
fps = {}
def rread(): 
    return int(input())
def fread(): 
    return [int(_x) for _x in input().split()]
def psth(s):
    if fps[s]!=s:
        fps[s]=psth(fps[s])
    return fps[s]
n,m=fread()
for i in range(1,n+1):
    fps[i]=i
for i in range(0,m):
    x,y,w=fread()
    ps.append((w,x,y))
ps.sort(reverse=True)
k=rread()
for i in range(0,k):
    a=list(map(int,input().split()))
    for j in range(2,a[0]+1):
        while psth(a[j])!=psth(a[1]):
            m=m-1
            w,x,y=ps[m]
            cx=psth(x)
            cy=psth(y)
            fps[cx]=cy
print(w)

详情