#include<cstdio> #include<vector> #include<queue> using namespace std; unsigned long long int osad=0; int masa [200005]; pair<int,int> sekw [200000]; pair<int,int> mix [500000]; struct reakc { int mix_no; reakc* next; reakc(int m_no) {mix_no=m_no; next=NULL; } }; struct ff { reakc* first; reakc* last; }; ff fio2[200005]; void join2(int a, int b) { reakc *fa,*fb; reakc *temp=NULL; reakc *last=NULL; int ta, tb; int mini; fa=fio2[a].first; fb=fio2[b].first; while(fa&&fb) { ta=fa->mix_no; tb=fb->mix_no; if(tb==ta) { mini=(masa[mix[ta].first]<masa[mix[ta].second])?masa[mix[ta].first]:masa[mix[ta].second]; osad+=mini*2; masa[mix[ta].first]-=mini; masa[mix[ta].second]-=mini; reakc * g=fa; fa=fa->next;//Tutaj pasowałoby jeszcze zniszczyć poprzednie delete g; g= fb; fb=fb->next; delete g; } else { if(temp) { if(ta<tb) {/*if (masa[mix[ta].first]>0&&masa[mix[ta].second]>0) */{last->next=fa;last=fa;}; fa=fa->next;last->next=NULL;} else {/*if (masa[mix[tb].first]>0&&masa[mix[tb].second]>0)*/{last->next=fb;last=fb;}; fb=fb->next;last->next=NULL;} } else { if(ta<tb) {/*if (masa[mix[ta].first]>0&&masa[mix[ta].second]>0)*/ {temp=fa;last=fa;}; fa=fa->next;} else {/*if (masa[mix[tb].first]>0&&masa[mix[tb].second]>0)*/{ temp=fb;last=fb;}; fb=fb->next;} } } } if(fa) {if(temp) last->next=fa;else temp=fa;last=fio2[a].last;} if(fb) {if(temp) last->next=fb;else temp=fb;last=fio2[b].last;} fio2[b].first=temp; fio2[b].last=last; } int main() { int n, m, k, t1, t2; scanf("%d %d %d", &n, &m, &k); for (int i=1; i<=n; i++) {scanf("%d", &masa[i]);fio2[i].first=fio2[i].last=NULL;} for (int i=0; i<m; i++) scanf("%d %d", &sekw[i].first, &sekw[i].second); for (int i=0; i<k; i++) { scanf("%d %d", &mix[i].first, &mix[i].second); reakc* t=new reakc(i); if(fio2[mix[i].first].first==NULL ) fio2[mix[i].first].first=t; else fio2[mix[i].first].last->next=t; fio2[mix[i].first].last=t; t=new reakc(i); if(fio2[mix[i].second].first==NULL ) fio2[mix[i].second].first=t; else fio2[mix[i].second].last->next=t; fio2[mix[i].second].last=t; } for(int i=0; i<m; i++) join2(sekw[i].first, sekw[i].second); printf("%llu", osad); return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 | #include<cstdio> #include<vector> #include<queue> using namespace std; unsigned long long int osad=0; int masa [200005]; pair<int,int> sekw [200000]; pair<int,int> mix [500000]; struct reakc { int mix_no; reakc* next; reakc(int m_no) {mix_no=m_no; next=NULL; } }; struct ff { reakc* first; reakc* last; }; ff fio2[200005]; void join2(int a, int b) { reakc *fa,*fb; reakc *temp=NULL; reakc *last=NULL; int ta, tb; int mini; fa=fio2[a].first; fb=fio2[b].first; while(fa&&fb) { ta=fa->mix_no; tb=fb->mix_no; if(tb==ta) { mini=(masa[mix[ta].first]<masa[mix[ta].second])?masa[mix[ta].first]:masa[mix[ta].second]; osad+=mini*2; masa[mix[ta].first]-=mini; masa[mix[ta].second]-=mini; reakc * g=fa; fa=fa->next;//Tutaj pasowałoby jeszcze zniszczyć poprzednie delete g; g= fb; fb=fb->next; delete g; } else { if(temp) { if(ta<tb) {/*if (masa[mix[ta].first]>0&&masa[mix[ta].second]>0) */{last->next=fa;last=fa;}; fa=fa->next;last->next=NULL;} else {/*if (masa[mix[tb].first]>0&&masa[mix[tb].second]>0)*/{last->next=fb;last=fb;}; fb=fb->next;last->next=NULL;} } else { if(ta<tb) {/*if (masa[mix[ta].first]>0&&masa[mix[ta].second]>0)*/ {temp=fa;last=fa;}; fa=fa->next;} else {/*if (masa[mix[tb].first]>0&&masa[mix[tb].second]>0)*/{ temp=fb;last=fb;}; fb=fb->next;} } } } if(fa) {if(temp) last->next=fa;else temp=fa;last=fio2[a].last;} if(fb) {if(temp) last->next=fb;else temp=fb;last=fio2[b].last;} fio2[b].first=temp; fio2[b].last=last; } int main() { int n, m, k, t1, t2; scanf("%d %d %d", &n, &m, &k); for (int i=1; i<=n; i++) {scanf("%d", &masa[i]);fio2[i].first=fio2[i].last=NULL;} for (int i=0; i<m; i++) scanf("%d %d", &sekw[i].first, &sekw[i].second); for (int i=0; i<k; i++) { scanf("%d %d", &mix[i].first, &mix[i].second); reakc* t=new reakc(i); if(fio2[mix[i].first].first==NULL ) fio2[mix[i].first].first=t; else fio2[mix[i].first].last->next=t; fio2[mix[i].first].last=t; t=new reakc(i); if(fio2[mix[i].second].first==NULL ) fio2[mix[i].second].first=t; else fio2[mix[i].second].last->next=t; fio2[mix[i].second].last=t; } for(int i=0; i<m; i++) join2(sekw[i].first, sekw[i].second); printf("%llu", osad); return 0; } |