Untitled
// ThonqRiu #include <bits/stdc++.h> #define endl '\n' #define maxn 100005 #define MOD 100000000000007 #define Task "bai1" #define ll long long using namespace std; int kU,kV,root[maxn],q,t,k,s,n,m; map <pair<int,int>,int> mp; struct phuba{ int u,v,w,pos; }; phuba a[maxn],b[maxn]; bool cmp(phuba &a, phuba &b){ if(a.w != b.w) return a.w < b.w; return true; } int getRoot(int u){ if(root[u] == 0) return u; return(root[u] = getRoot(root[u])); } void Kruskal(){ mp.clear(); fill(root+1,root+n+1,0); sort(a+1,a+m+1,cmp); for(int i = 1; i<=m; i++){ int p = getRoot(a[i].u); int q = getRoot(a[i].v); if(p != q){ root[p] = q; mp[{a[i].u,a[i].v}] = 1; } } } void inp(){ cin >> n >> m >> q; for(int i = 1; i <= m; i++){ cin >> a[i].u >> a[i].v >> a[i].w; a[i].pos = i; b[i] = a[i]; } while(q--){ cin >> k >> s; kU = a[k].u; kV = a[k].v; for(int i = 1; i<=m; i++) a[i] = b[i]; while(s--){ int K,W; cin >> K >> W; a[K].w = W; } Kruskal(); if(mp[{kU,kV}]) cout << "NO" << endl; else cout << "YES" << endl; } } int main() { ios_base:: sync_with_stdio(0); cin.tie(nullptr); if(fopen(Task".inp","r")){ freopen(Task".inp","r",stdin); } cin >> t; while(t--) inp(); }
Leave a Comment