Pagini recente » Cod sursa (job #685649) | Cod sursa (job #2709740) | Cod sursa (job #997239) | Cod sursa (job #364343) | Cod sursa (job #595476)
Cod sursa(job #595476)
#include<fstream>
using namespace std;
int n,m,ns;
struct Muchie{int x,y,cost;};
Muchie G[400010];
int arbore[200010],c[200010];
char s[1000];
inline bool Ordonare(const Muchie A,const Muchie B)
{
if(A.cost==B.cost)
{
if(A.x==B.x)
return A.y<B.y;
return A.x<B.x;
}
return A.cost<B.cost;
}
void Initializari()
{
int i,j,x,y,z;
bool minus;
//parsez citirea
ifstream fin("apm.in");
fin.getline(s,999);
ns=strlen(s);
//pentru n
n=s[0]-'0';
i=1;
while(s[i]>='0' && s[i]<='9')
{
n=n*10+(s[i]-'0');
i++;
}
i++;
//pentru m
m=s[i]-'0';
i++;
while(s[i]>='0' && s[i]<='9' && i<ns)
{
m=m*10+(s[i]-'0');
i++;
}
for(i=1;i<=m;i++)
{
fin.getline(s,999);
ns=strlen(s);
minus=false;
//pentru G[i].x
x=s[0]-'0';
j=1;
while(s[j]>='0' && s[j]<='9')
{
x=x*10+(s[j]-'0');
j++;
}
j++;
//pentru G[i].y
y=s[j]-'0';
j++;
while(s[j]>='0' && s[j]<='9')
{
y=y*10+(s[j]-'0');
j++;
}
j++;
//pentru G[i].cost
if(s[j]=='-')
{
j++;
minus=true;
}
z=s[j]-'0';
j++;
while(s[j]>='0' && s[j]<='9' && j<ns)
{
z=z*10+(s[j]-'0');
j++;
}
G[i].x=x;
G[i].y=y;
if(minus==true)
G[i].cost=-z;
else
G[i].cost=z;
}
fin.close();
for(i=1;i<=n;i++)
c[i]=i;
}
void Kruskal()
{
int i,j,minim,maxim,nr=0; //nr = numarul de muchii selectate
for(i=1;nr<n-1;i++)
{
if(c[G[i].x]!=c[G[i].y]) //daca muchia nu ar forma cicluri cu cele deja selectate
{
arbore[++nr]=i; //selectez muchia i
//unific cele doua componente conexe
if(c[G[i].x]<c[G[i].y])
{
minim=c[G[i].x];
maxim=c[G[i].y];
}
else
{
minim=c[G[i].y];
maxim=c[G[i].x];
}
for(j=1;j<=n;j++)
if(c[j]==maxim)
c[j]=minim;
}
}
}
void AfisareArbore()
{
ofstream fout("apm.out");
int i,cost=0;
for(i=1;i<n;i++)
{
cost+=G[arbore[i]].cost;
}
fout<<cost<<"\n"<<n-1<<"\n";
for(i=1;i<n;i++)
{
fout<<G[arbore[i]].x<<' '<<G[arbore[i]].y<<"\n";
}
fout.close();
}
int main()
{
Initializari();
sort(G+1,G+m+1,Ordonare); //sortez muchiile crescator dupa cost
Kruskal(); //determin arborele partial de cost minim
//selectand n-1 muchii de cost minim,care nu formeaza cicluri
AfisareArbore(); //afisez APM
return 0;
}