Cod sursa(job #1609323)

Utilizator king25Ionut Vasi king25 Data 22 februarie 2016 18:50:32
Problema Mesaj4 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.79 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream f("subarbore.in");
ofstream g("subarbore.out");
int n,m,t,suma,minim=200000000;
bool S[41],T[41];
vector<int> C(41,0);
vector<int> C1(41,0);
vector < pair < int,int > > M[41];
vector <int> Ns(10);
struct Muchie{
    int x,y,c;
};
vector <Muchie> G;
void APM(){
    for(int i=0;i<m;i++){
        if(S[G[i].x] && S[G[i].y]){
            if(C[G[i].x] != C[G[i].y]){
                int minim=min(C[G[i].x],C[G[i].y]),maxim=max(C[G[i].x],C[G[i].y]);
                suma+=G[i].c;
                replace(C.begin(),C.end(),maxim,minim);
            }
        }
    }
}
bool comp1(const Muchie & a ,const Muchie & b){
    return a.c<b.c;
}
void back(int k){
    int nod=NS[k];
    for(n==k){
        APM();
    }else{
        for(vector<int>::iterator it=M[nod].begin();it!=M[nod].end();it++){
            if(C[nod]!=C[(*it).first]){
                int minim=min(C[nod],C[(*it).first]),maxim=max(C[nod],C[(*it).first]);
                suma+=(*it).second;
                C[(*it).first]
                back(k+1);
                suma-=(*it).second;
            }
        }
    }
}
int main()
{
    int x,y,c;
    f>>n>>m;
    for(int i=0;i<m;i++){
        f>>x>>y>>c;
        Muchie m;
        m.x=x;
        m.y=y;
        m.c=c;
        G.push_back(m);
        M[x].push_back(make_pair(y,c));
        M[y].push_back(make_pair(x,c));
    }
    f>>t;
    for(int i=1;i<=n;i++){
        T[x]=false;
    }
    for(int i=0;i<t;i++){
        f>>x;
        NS.push_back(x);
        T[x]=true;
        S[x]=true;
    }

    for(int i=1;i<=n;i++){
        C1[i]=i;
    }
    C=C1;
    sort(G.begin(),G.end(),comp1);
    back(1);
    g<<minim;
    return 0;
}