POJ 1639 Picnic Planning(K-On-Spanning Tree + map 구성)

사고방식: 기본적으로 도한으로 그림을 만드는 템플릿 문제이고 그림을 만들 때 MAP를 사용했다. 마지막으로 폭력으로 모든 가능성을 열거하고 동태적인 계획을 쓰지 않았다.

#include<stdio.h>
#include<string.h>
#include<map>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
#define INF 0x7ffffff
const int N=30;
char str1[N];
char str2[N];
int mpt[N][N];
bool edge[N][N];
int dist[N];
int vis[N];
bool mark[N];
int pre[N];
int father[N];
int best[N];
int n,k;
int end;
void init()
{
    for(int i=0;i<N;i++)
    {
        for(int j=0;j<N;j++)
        {
            mpt[i][j]=INF;
        }
    }
}
void dfs(int x)
{
    for(int i=1;i<=end;i++)
    {
        if(edge[i][x]&&mark[i])
        {
            father[i]=x;
            mark[i]=false;
            dfs(i);
        }
    }
}
int prim(int s)
{
    memset(mark,0,sizeof(mark));
    memset(pre,0,sizeof(pre));
    for(int i=2;i<=end;i++)
    {
        dist[i]=mpt[s][i];
        pre[i]=s;
    }
    mark[s]=true;
    vis[s]=true;
    int sum=0;
    int v=0;
    for(int i=2;i<end;i++)
    {
        int minx=INF;
        for(int j=2;j<=end;j++)
        {
            if(!vis[j]&&!mark[j]&&minx>dist[j])
            {
                minx=dist[j];
                v=j;
            }
        }
        if(minx>=INF)break;
        vis[v]=true;
        mark[v]=true;
        edge[pre[v]][v]=edge[v][pre[v]]=true;
        sum+=minx;
        for(int j=2;j<=end;j++)
        {
            if(!vis[j]&&!mark[j]&&mpt[v][j]<dist[j])
            {
                dist[j]=mpt[v][j];
                pre[j]=v;
            }
        }
    }
    int minx=INF;
    int root=-1;
    //   V0      
    for(int i=1;i<=end;i++)
    {
        if(mark[i]&&mpt[i][1]<minx)
        {
            minx=mpt[i][1];
            root=i;
        }
    }
    mark[root]=false;
    dfs(root);// ROOT      
    father[root]=1;
    return sum+minx;
}

void solve()
{
    memset(vis,0,sizeof(vis));
    vis[1]=true;
    int m=0;
    int mst=0;
    for(int i=2;i<=end;i++)
    {
        if(vis[i]==0)
        {
            vis[i]=true;
            m++;
            mst+=prim(i);
        }
    }
    int cost;
    int v=0;
    for(int p=m+1;p<=k;p++)
    {
        cost=INF;
        for(int i=2;i<=end;i++)
        {
            if(mpt[i][1]<INF&&father[i]!=1)
            {
                int w=0;
                int fi=i;
                while(father[fi]!=1)
                {
                    w=max(w,mpt[fi][father[fi]]);
                    fi=father[fi];
                }
                if(mpt[i][1]-w<cost)
                {
                    cost=mpt[i][1]-w;
                    v=i;
                }
            }
        }
        father[v]=1;
        mst=min(mst,mst+cost);
    }
    printf("Total miles driven: %d
",mst);
}
int main()
{
    scanf("%d",&n);
    map<string,int>m;
    int cnt=2;
    int len;
    m["Park"]=1;
    init();
    for(int i=1;i<=n;i++)
    {
        cin>>str1>>str2>>len;
        if(m[str1]==0)m[str1]=cnt++;
        if(m[str2]==0)m[str2]=cnt++;
        if(len<mpt[m[str1]][m[str2]])
        {
            mpt[m[str1]][m[str2]]=len;
            mpt[m[str2]][m[str1]]=len;
        }
    }
    end=cnt-1;
    scanf("%d",&k);
    solve();
    return 0;
}