度限制最小生成树 POJ 1639 贪心+DFS+prim

很好的解题报告：

http://blog.csdn.net/new_c_yuer/article/details/6365689

注意两点：

1.预处理环中权值最大的边····

2.可以把去掉度限制后的点看成是连通的，权值为无穷远的点也看做是连通的，反正后面肯定会替换出来的····

我的代码没有预处理出权值最大的边，但是第2点事做到了的，这样便于代码的实现·····

贴代码：

 #include <cstdio>

 #include <iostream>

 #include <map>

 #include <string>

 #include <algorithm>

 #define INF 0x3f3f3f3f

 #define N 505

 using namespace std;

 map<string,int> ma;

 map<string,int>::iterator it;

 int n,k;//点的个数，度数限制

 bool flag;

 long long int ans;//最后的结果

 bool in[N][N],vis[N];//加入最小生成树中的边

 int edge[N][N],pre[N], next[N],lowcost[N];//边，确定哪些边被加入了最小生成树中，存环中的边，求最小生成树

 int Find(char c[])

 {

     it = ma.find(c);

     if(it != ma.end())

         return it->second;

     ma[c] = ++n;

     return n;

 }

 //用prim函数求一次去掉度限制的点后的最小生成树

 void prim()

 {

     lowcost[] = -;

     for(int i=; i<=n; ++i)

     {

         lowcost[i] = edge[][i];

         pre[i] = ;

     }

     for(int i=; i<=n; ++i)

     {

         int v;

         int minum=INF;

         for(int j=; j<=n; ++j)

         {

             if(lowcost[j] != - && minum >= lowcost[j])

             {

                 minum = lowcost[j];

                 v = j;

             }

         }

         lowcost[v] = -;

         ans += edge[v][pre[v]];

         in[v][pre[v]] = in[pre[v]][v] = ;

         for(int j=; j<=n; ++j)

         {

             if(lowcost[j] != - &&  lowcost[j] > edge[j][v] )

             {

                 lowcost[j] = edge[j][v];

                 pre[j] = v;

             }

         }

     }

 }

 //dfs找出环

 void dfs(int x)

 {

     if(x == )

     {

         flag = true;

         return;

     }

     vis[x] = ;

     for(int i = n; i >= ; --i)

     {

         if(in[x][i] && !vis[i] && !flag)

         {

             next[x] = i;

             dfs(i);

         }

     }

 }

 //找环上权值最大的边

 void findMax(int x,int &s,int &e,int &maxnum)

 {

     memset(vis,,sizeof(vis));

     flag = false;

     dfs(x);

     maxnum = edge[][x];

     int ne = x;

     while(next[ne] != )

     {

         if(edge[ne][next[ne]] > maxnum)

         {

             maxnum = edge[ne][next[ne]];

             s = ne;

             e = next[ne];

         }

         ne  = next[ne];

     }

 }

 //找度限制为k的最小生成树

 void kTree()

 {

     int minum = INF;

     int v;

     for(int i=; i<=n; ++i)

     {

         if(edge[][i] < minum)

         {

             minum = edge[][i];

             v =  i;

         }

     }

     in[v][] = in[][v] = ;

     ans += edge[][v];

     for(int t=; t<k; ++t)

     {

         minum = INF;

         v = -;

         int s,e,m;

         for(int i=; i<=n; ++i)

         {

             if(!in[][i] && edge[][i] < INF)

             {

                 int ss,ee,maxnum;

                 findMax(i,ss,ee,maxnum);

                 if(edge[][i] - maxnum < minum)

                 {

                     minum = edge[][i] - maxnum ;

                     s = ss;

                     e = ee;

                     m = minum;

                     v= i;

                 }

             }

         }

         if(v == -) break;

         if(minum >=  ) break;

         in[][v] = ;

         in[v][] = ;

         in[s][e] = ;

         in[e][s] =;

         ans += minum;

     }

     printf("Total miles driven: %d\n",ans);

 }

 // 初始化输入

 void initScan()

 {

     int m;

     ma["Park"] = n;

     scanf("%d",&m);

     memset(edge,0x3f,sizeof(edge));

     for(int i=; i<m; ++i)

     {

         char a1[N],a2[N];

         int u,v,w;

         scanf("%s %s %d",a1,a2,&w);

         u = Find(a1);

         v = Find(a2);

         edge[u][v] = w;

         edge[v][u] = edge[u][v];

     }

     scanf("%d",&k);

 }

 int main()

 {

     initScan();

     prim();

     kTree();

     return ;

 }