Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<fstream>
- #include<algorithm>
- #include<vector>
- #include<cstring>
- #define N 10005
- using namespace std;
- ifstream fin ("zapada.in");
- ofstream fout ("zapada.out");
- int n,m,k,a,b,c;
- int cost;
- int t[N],viz[N],rang[N];
- struct T{int a,b,c;};
- vector<T>mc,v;
- bool comp(T x, T y){return x.c<y.c;}
- int Rad(int x)
- {
- while(x!=t[x])x=t[x];
- return x;
- }
- void Uneste(int x, int y)
- {
- if(rang[x]>rang[y])t[y]=x;
- else{
- t[x]=y;
- if(rang[x]==rang[y])
- rang[y]++;
- }
- }
- int main()
- {
- fin>>n>>m>>k;
- for(int i=1;i<=m;i++)
- {
- fin>>a>>b>>c;
- mc.push_back({a,b,c});
- }
- sort(mc.begin(), mc.end(),comp);
- for(int i=1;i<=n;i++)t[i]=i;
- for(int i=0;i<m;i++)
- {
- int rx=Rad(mc[i].a);
- int ry=Rad(mc[i].b);
- if(rx!=ry)
- {
- Uneste(rx, ry);
- v.push_back(mc[i]);
- cost+=mc[i].c;
- }
- }
- fout<<cost<<"\n";
- while(k--)
- {
- fin>>a>>b>>c;
- if(v[v.size()-1].c>c)
- {
- v.push_back({a,b,c});
- for(int i=v.size()-1;i>0;i--)
- if(v[i].c<v[i-1].c)swap(v[i],v[i-1]);
- else break;
- mc=v;
- v.clear();
- cost=0;
- for(int i=1;i<=n;i++){t[i]=i; rang[i]=0;}
- for(int i=0;i<n;i++)
- {
- int rx=Rad(mc[i].a);
- int ry=Rad(mc[i].b);
- if(rx!=ry)
- {
- Uneste(rx,ry);
- v.push_back(mc[i]);
- cost+=mc[i].c;
- }
- }
- fout<<cost<<"\n";
- }
- else fout<<cost<<"\n";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement