Euler sétás gráf feladat

Euler sétás gráf feladat
2020-04-20T12:54:33+02:00
2020-04-20T12:59:26+02:00
2022-10-15T21:16:41+02:00
%R%
Szép napot!
Adott alább egy feladat,a tavalyi IOI válogató 14. feladata.
Feladatleírás és segítség csatolva.Sajnos egyszerre csak egyet enged.
A feladat röviden: adott egy dominóhalmaz,adjunk hozzá úgy dominókat hogy sorba lehessen őket rakni,és a hozzáadott dominókon a pöttyök száma a lehető legkisebb legyen.
Dominók=élek
Egyoldalt levő pöttyök száma=csúcsok sorszámai amiket az él összeköt.
Pl a (3,4) dominó a 3. és 4. csúcsokat köti össze.
Csak egész pötty van,a pöttyök száma 1 és K közötti.
Sorba úgy lehet rakni a dominókat,hogy az egymás melleti,de különböző dominón levő pöttyök száma egyezzen pl.: (2,1)(1,7)(7,7)(7,3)(3,2)
A dominókat szabad megfordítani.
Ehhez a feladathoz segítséget kértem,és kaptam,és próbáltam a programot a segítség alapjára építeni.
Az algoritmus:
Legyen S azon csúcsok halmaza melyekből új élet kell húznunk(1-et vagy 2-őt)
Ehhez 2 szabályt tartunk szem előtt:
Minden komponensből menjen ki él.
Minden páratlan fokú csúcsból menjen ki 1 él.
Azaz s nek 2 féle eleme lehet: páratlan fokú,és páros,méghozzá egy olyan komponensből amiben nincs páratlan,és ő a legkisebb,az ilyenek triviálisan 2 szer szerepelnek s ben.
Tehát az
1
1 2
3 4
3 4
bemeneten az 1 es egyszer,a kettes egyszer,a hármas 2 szer a 4 es 0 szor szerepel.

A csúcsokat unio-holvan szerűen tárolom,azaz mindnek van egy szülője, az ősöknek saját maguk.
Beolvasásnál(a,b) amelyik csúcs őse a kisebb,annak rendelem alá a másik ősét.
A holvan művelet:Addig lépked vissza a szülőkön amíg az aktuális csúcs szülője nem maga,így könnyen és aránylag gyorsan meg lehet határozni,hogy két csúcs egy komponensbe tartozik e.Azaz egy komponens minden tagja egy azonos őshöz vezet.
A fentebbi szabályokat úgy teljesítem, hogy alapból minden csúcsnak van egy s változója ami 1.Ez jelzi hogy hányszor szerepel s ben. A beolvasás után minden csúcsra végrehajtom:
-Ha páratlan fokú,akkor az ha páros az őse,az ős nem lehet s ben azaz s=0.
(mivel páros csak akkor lehet ha nincs páratlan fokú a komponensben.)
-Ha páros és ős ,és még nincs nullázva akkor s=2
-Különben s=0

Mivel a feladat megoldásának feltétele hogy a végén a gráf összefüggő legyen,és a páratlan fokú csúcsok száma 2 vagy 0 legyen,ezért 2-őt kihagyhatunk S ből.
Értelemszerűen a 2 legnagyobbat,ez nem kivitelezhető ha egy komponensben vannak és az adott komponensben a páratlan fokú csúcsok száma 2.(azaz csak ők vannak benne páratlanként).
Ez le van nagyon jól írva ,nem ismétlem.

Namost, ha megvan az S halmaz,akkor a következőt csináltam.Sorba vettem a csúcsokat amik S részei,és kerestem nekik egy olyan csúcsot amik szintén s részei,de másik komponensből valók.
Ennek a műveletnek a végén a gráfnak összefüggőnek kell lennie,mivel minden komponensben legalább 2 s tag csúcs van,kivéve a 2 t vagy ahonnan a maximálisok ki lettek véve
(ha 2 szer volt benne akkor már csak egyszer van,ha egyszer volt akkor 0 szor)
Azaz ha 2 komponens csatlakozik akkor a keletkezettnek ugyanúgy 2  vagy több s tagja lesz,így a gráf össze fog függeni.
A végén a megmaradt s tagokat tetszés szerint összekötjük.
Hol itt a hiba? :)
Mester 60/100 at ad rá,hibás kimenetek miatt.(tehát nincs lassúság, se memória hiba)
Gyanítom hogy valamit nem vettem észre,vagy van olyan lehetőség amire nem figyeltem fel,de eddig hiába teszteltem,mindenre tökéletesn működött.
Kód:

#include <iostream> #include <vector> using namespace std; struct csucs { unsigned short int fokszam; int szulo;//unio-holvan szerű adatstruktúrát használok short int s;//1-ha páratlan és s halmaz eleme,minden más esetben 0 }; int os(int a,csucs csucsok[]) //ős meghatározása { while(csucsok[a].szulo!=a) { a=csucsok[a].szulo; } return a; } int main() { cin.tie(NULL); ios_base::sync_with_stdio(false); short int t; cin>>t; for(int z=0;z<t;z++) { int e,n; cin>>e>>n; csucs csucsok[n]; unsigned short int* prtln=new unsigned short int[100000];//ha a komponensben ez a csúcs az ős akkor mutatja a komponensbeli páratlan fokú csúcsok számát for(int i=0;i<n;i++) { csucsok[i].fokszam=0; csucsok[i].s=1; csucsok[i].szulo=i; prtln[i]=0; } int ela,elb,osa,osb; for(int i=0;i<e;i++) { cin>>ela>>elb; ela--; elb--; csucsok[ela].fokszam++; csucsok[elb].fokszam++; osa=os(ela,csucsok); osb=os(elb,csucsok); if(osa<osb) //így a komponensben mindig a legkisebb lesz legfelül,ez később hasznos lesz { csucsok[osb].szulo=osa; } else { csucsok[osa].szulo=osb; } } if(n==1) { cout<<"0 0"<<endl; continue; } for(int i=0;i<n;i++) { if(csucsok[i].fokszam==0)//az ilyen csúcsok lényegtelenek a feladat szempontjából { csucsok[i].s=0; continue; } osa=os(i,csucsok); if(csucsok[i].fokszam%2==1) { prtln[osa]++; if(csucsok[osa].fokszam%2==0) { csucsok[osa].s=0; //párosként már nem lehet s ben,mivel van páratlan a komponensben } } else { if(csucsok[i].szulo!=i)//ha páros ,és nem ős,akkor elvesszük az s tagságát,ha ős akkor a páratlanok miatt elveszíti,ha kell { csucsok[i].s=0; } else { if(csucsok[i].s==1) { csucsok[i].s=2; } } } } //3 vagy 2 maximum kikeresése int* max=new int[3]; max[2]=-1; max[1]=-1; max[0]=-1; int maxdb; maxdb=0; for(int i=n-1;i>-1;i--) { if(csucsok[i].s!=0) { max[maxdb]=i; maxdb++; if(maxdb==3) { break; } } } //kiértékelés if(max[1]==-1 ) { cout<<"0 0"<<endl; continue; } if(max[2]==-1) { if(csucsok[max[1]].fokszam%2==1)//2 lehetőség: 1. egy komponens 2 páratlannal, 2 komponens csupa párossal. { cout<<"0 0"<<endl; continue; } } osa=os(max[0],csucsok); if(osa==os(max[1],csucsok) && prtln[osa]==2 ) { if(2*osa<max[1]-max[2])//mintamegoldásba le van írva { csucsok[max[0]].s--; csucsok[max[1]].s--; csucsok[osa].s=2; } else { csucsok[max[0]].s--; csucsok[max[2]].s--; } } else { csucsok[max[0]].s--; csucsok[max[1]].s--; } delete [] max; int i; unsigned int osszeg=0; vector<int>sa;//megoldás, sa-sb párok lesznek a megoldás dominók vector<int>sb; int honnan=1; int j; for(i=0;i<n;i++)//csak különböző komponensbeliek összekötése { if(csucsok[i].s==0) { continue; } osa=os(i,csucsok); for(j=honnan;j<n;j++) { if(csucsok[j].s!=0 && os(j,csucsok)!=osa)//ha nem egy komponensben vannak és mindkettőnek van még s-e. { sa.push_back(i+1); sb.push_back(j+1); osszeg=osszeg+i+j+2; csucsok[i].s--; csucsok[j].s--; csucsok[os(j,csucsok)].szulo=osa; honnan=j+1; if(csucsok[i].s==0) { break; } continue; } } if(j==n) { break; } } for(;i<n;i++)//tetszés szerinti összekötögetés { if(csucsok[i].s==0) { continue; } for(j=i+1;;j++) { if(csucsok[j].s==1) { sa.push_back(i+1); sb.push_back(j+1); osszeg=osszeg+j+i+2; csucsok[i].s--; csucsok[j].s--; break; } } } cout<<osszeg<<" "<<sa.size()<<" "; int s=sa.size(); for(int i=0;i<s;i++) { cout<<sa[i]<<" "<<sb[i]<<" "; } cout<<endl; delete []prtln; } return 0; }
Elnézést,az oldal lenyelte a tabokat :(
Mutasd a teljes hozzászólást!
Csatolt állomány

Tetszett amit olvastál? Szeretnél a jövőben is értesülni a hasonló érdekességekről?
abcd