思路： 考虑环上所有边不同色，即，每种颜色任意出一条边，构成的图都是无环的。 我们将每个集合的点连向一个集合源点，共m个集合源点，每个点都往包含该店的集合源点连边，那么这就是一个并查集的过程，可以很轻松的知道什么时候会产生环，那么在这之前将点都排好序，就可以贪心的删除最优点了。
#pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h> using namespace std; typedef long long LL; const int N = 3e5 + 10; #define fi first #define se second #define pb push_back #define wzh(x) cerr<<#x<<'='<<x<<endl; int m,n; int a[N],b[N]; struct uzi{ int x,y; bool operator <(const uzi & t)const{ return a[y]+b[x]>a[t.y]+b[t.x]; } }p[N]; int cnt,f[N]; int find(int x){ return f[x]==x?x:(f[x]=find(f[x])); } int main() { ios::sync_with_stdio(false); cin>>m>>n; for(int i=1;i<=m;i++)cin>>a[i]; for(int i=1;i<=n;i++)cin>>b[i]; for(int i=1;i<=m;i++){ int s; cin>>s; for(int j=1;j<=s;j++){ cin>>p[++cnt].x; p[cnt].y=i; } } for(int i=1;i<=cnt+m;i++)f[i]=i; sort(p+1,p+1+cnt); LL ans=0; for(int i=1;i<=cnt;i++){ int x=find(p[i].x+m),y=find(p[i].y); if(x==y){ ans+=b[p[i].x]+a[p[i].y]; }else{ f[x]=y; } } cout<<ans<<'\n'; return 0; }