UVa 11710 - Expensive subway

#include<bits/stdc++.h>
#define mx 100009
using namespace std;
map<string,int>mp;
bool visited[79809];
vector<string>v;
vector<int>g[79809];
int ct;
void dfs(int n)
{
    visited[n]=1;
    for(int i=0;i<g[n].size();i++)
    {
        int m=g[n][i];
        if(!visited[m])
        {
            ct++;
            dfs(m);
        }
    }
}
struct edge
{
    int u,v,w;
    bool operator < (const edge& p) const
    {
        return w<p.w;
    }
};
int pr[mx];
vector<edge>e;
int fnd(int r)
{
    return (pr[r]==r)?r:fnd(pr[r]);
}
int mst(int n)
{
    sort(e.begin(),e.end());
    for(int i=1;i<=n;i++)
    {
        pr[i]=i;
    }
    int cnt=0,s=0;
    for(int i=0;i<(int)e.size();i++)
    {
        int u=fnd(e[i].u);
        int v=fnd(e[i].v);
        if(u!=v)
        {
            pr[u]=v;
            cnt++;
            s+=e[i].w;
            if(cnt==n-1)
                break;
        }
    }
    return s;
}
int main()
{
    int i,j,k,l,m,n;
    while(cin>>n>>m)
    {
        if(n==0&&m==0)
            break;
        else
        {
            mp.clear();
            e.clear();
            v.clear();
            string s;
            for(i=0;i<79809;i++)
            {
                g[i].clear();
            }
            memset(visited,0,sizeof(visited));
            for(i=0;i<n;i++)
            {
                cin>>s;
                v.push_back(s);
            }
            int num=1;
            for(i=0;i<m;i++)
            {
                string from,to;
                int u,v,w;
                cin>>from>>to>>w;
                if(mp[from]!=0)
                {
                    u=mp[from];
                }
                if(mp[to]!=0)
                {
                    v=mp[to];
                }
                if(!mp[from])
                {
                    u=num;
                    mp[from]=num;
                    num++;
                }
                if(!mp[to])
                {
                    v=num;
                    mp[to]=num;
                    num++;
                }
                edge get;
                get.u=u;
                get.v=v;
                get.w=w;
                e.push_back(get);
                swap(u,v);
                get.u=u;
                get.v=v;
                get.w=w;
                e.push_back(get);
                g[u].push_back(v);
                g[v].push_back(u);
            }
            string st;
            cin>>st;
            int start=mp[st];
            ct=1;
            dfs(start);
            if(ct!=n)
            {
                cout<<"Impossible"<<endl;
                continue;
            }
            cout<<mst(n)<<endl;
        }
    }
    return 0;
}

UVa 11631 - Dark roads

#include<bits/stdc++.h>
#define mx 200009
using namespace std;
typedef long long ll;
struct edge
{
    ll u,v,w;
    bool operator < (const edge& p) const
    {
        return w<p.w;
    }
};
ll pr[mx];
vector<edge>e;
ll fnd(ll r)
{
    return (pr[r]==r)?r:fnd(pr[r]);
}
ll mst(ll n)
{
    sort(e.begin(),e.end());
    //reverse(e.begin(),e.end());
    for(ll i=1;i<=n;i++)
    {
        pr[i]=i;
    }
    ll cnt=0,s=0;
    for(int i=0;i<(ll)e.size();i++)
    {
        ll u=fnd(e[i].u);
        ll v=fnd(e[i].v);
        if(u!=v)
        {
            pr[u]=v;
            cnt++;
            s+=e[i].w;
            if(cnt==n-1)
                break;
        }
    }
    return s;
}
int main()
{
    //ofstream o("op.txt");
    while(1)
    {
        ll n,m,sum=0;
        scanf("%lld %lld",&n,&m);
        if(n==0&&m==0)
            break;
        for(int i=1;i<=m;i++)
        {
            ll u,v,w;
            scanf("%lld%lld%lld",&u,&v,&w);
            sum+=w;
            edge get;
            get.u=u+1;
            get.v=v+1;
            get.w=w;
            e.push_back(get);
        }
        printf("%lld\n",sum-mst(n));
        e.clear();
    }
    return 0;
}

UVa 10034 - Freckles

#include<bits/stdc++.h>
#define mx 100009
using namespace std;
typedef long long ll;
struct edge
{
    int u,v;
    double w;
    bool operator < (const edge& p) const
    {
        return w<p.w;
    }
};
int pr[mx];
vector<edge>e;
int fnd(int r)
{
    return (pr[r]==r)?r:fnd(pr[r]);
}
double mst(int n)
{
    sort(e.begin(),e.end());
    for(int i=1;i<=n;i++)
    {
        pr[i]=i;
    }
    int cnt=0;
    double s=0.0;
    for(int i=0;i<(int)e.size();i++)
    {
        int u=fnd(e[i].u);
        int v=fnd(e[i].v);
        if(u!=v)
        {
            pr[u]=v;
            cnt++;
            s+=e[i].w;
            if(cnt==n-1)
                break;
        }
    }
    return s;
}
int main()
{
    ll i,j,k,l,m,n,test;
    cin>>test;
    for(k=1;k<=test;k++)
    {

        cin>>n;
        vector< pair<double,double> >v;
        v.clear();
        e.clear();
        for(i=1;i<=n;i++)
        {
            double x,y;
            cin>>x>>y;
            v.push_back(make_pair(x,y));
        }
        for(i=0;i<n;i++)
        {
            for(j=i+1;j<n;j++)
            {
                double x1,x2,y1,y2;
                double d=sqrt((v[i].first-v[j].first)*(v[i].first-v[j].first)+(v[i].second-v[j].second)*(v[i].second-v[j].second));
                double u,v;
                edge get;
                get.u=i+1;
                get.v=j+1;
                get.w=d;
                e.push_back(get);
            }
        }
        printf("%.2f\n",mst(n));
        if(k<test)
            printf("\n");
    }
    return 0;
}

UVa 357 - Let Me Count The Ways

#include<bits/stdc++.h>
#define mod 100000007
using namespace std;
typedef long long ll;
ll arr[300009],coin[6]={0,1,5,10,25,50};
int main()
{
    ll i,j,k,l,m,n,test,make;
    while(cin>>make)
    {
        n=5;
        memset(arr,0,sizeof(arr));
        arr[0]=1;
        ll sum=0;
        for(i=1;i<=n;i++)
        {
            for(j=coin[i];j<=make;j++)
            {
                arr[j]=(arr[j])+(arr[j-coin[i]]);
            }
        }
        cout<<"There ";
        if(arr[make]<=1)
            cout<<"is only ";
        else
            cout<<"are ";
        cout<<arr[make]<<" ";
        if(arr[make]<=1)
            cout<<"way";
        else
            cout<<"ways";
        cout<<" to produce "<<make<<" cents change."<<endl;
    }
    return 0;
}