POJ 1639 Picnic Planning：最小度限制生成树

题目链接：http://poj.org/problem?id=1639

题意：

　　给你一个无向图，n个节点，m条边，每条边有边权。

　　让你求一棵最小生成树，同时保证1号节点的度数<=k。

题解：

　　最小度限制生成树：

　　　　（1）不用与1号节点相连的边，跑一次kruskal，得到了deg个连通块。

　　　　（2）选取与1相连的deg条边，并使得边尽可能小，将1与这些连通块连起来，得到了一棵deg度最小生成树。

　　　　（3）利用当前的deg度最小生成树，求出deg+1度最小生成树。如此重复至k度最小生成树：

　　　　　　I. 在当前生成树上dfs求出：从1出发到i节点路径上的最大边dp[i]（除去与1相连的边）。

　　　　　　II. 枚举与1相连且不在生成树内的边，添加一条能使当前生成树变得最小的边。

　　　　　　III. 如果无论如何都无法将生成树变小，则已求出答案，退出循环。

AC Code:

 #include <iostream>

 #include <stdio.h>

 #include <string.h>

 #include <algorithm>

 #include <map>

 #define MAX_N 35

 #define MAX_M 905

 #define INF 1000000000

 using namespace std;

 struct Edge

 {

     int s;

     int t;

     int len;

     Edge(int _s,int _t,int _len)

     {

         s=_s;

         t=_t;

         len=_len;

     }

     Edge(){}

     friend bool operator < (const Edge &a,const Edge &b)

     {

         return a.len<b.len;

     }

 };

 int n=,m,k;

 int ans=,deg=;

 int par[MAX_N];

 int lnk[MAX_N];

 int minn[MAX_N];

 int a[MAX_N][MAX_N];

 bool flag[MAX_N][MAX_N];

 Edge dp[MAX_N];

 Edge edge[MAX_M];

 map<string,int> mp;

 int cal_id(const string &s)

 {

     if(mp.count(s)>) return mp[s];

     mp.insert(pair<string,int>(s,++n));

     return n;

 }

 void read()

 {

     cin>>m;

     string s1,s2;

     int v;

     memset(a,-,sizeof(a));

     cal_id("Park");

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

     {

         cin>>s1>>s2>>v;

         int id1=cal_id(s1);

         int id2=cal_id(s2);

         edge[i]=Edge(id1,id2,v);

         if(a[id1][id2]==-) a[id1][id2]=a[id2][id1]=v;

         else a[id1][id2]=a[id2][id1]=min(a[id1][id2],v);

     }

     cin>>k;

 }

 void init_union_find()

 {

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

     {

         par[i]=i;

     }

 }

 int find(int x)

 {

     return par[x]==x ? x : par[x]=find(par[x]);

 }

 void unite(int x,int y)

 {

     int px=find(x);

     int py=find(y);

     if(px==py) return;

     par[px]=py;

 }

 bool same(int x,int y)

 {

     return find(x)==find(y);

 }

 void kruskal()

 {

     init_union_find();

     sort(edge,edge+m);

     memset(flag,false,sizeof(flag));

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

     {

         Edge temp=edge[i];

         if(temp.s== || temp.t==) continue;

         if(!same(temp.s,temp.t))

         {

             ans+=temp.len;

             unite(temp.s,temp.t);

             flag[temp.s][temp.t]=flag[temp.t][temp.s]=true;

         }

     }

 }

 void cal_mdeg()

 {

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

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

     {

         if(a[][i]!=-)

         {

             int p=find(i);

             if(a[][i]<minn[p])

             {

                 minn[p]=a[][i];

                 lnk[p]=i;

             }

         }

     }

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

     {

         if(minn[i]<INF)

         {

             deg++;

             ans+=minn[i];

             flag[][lnk[i]]=flag[lnk[i]][]=true;

         }

     }

 }

 void dfs(int x,int p)

 {

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

     {

         if(flag[x][i] && i!=p)

         {

             if(dp[i].len==-)

             {

                 if(a[x][i]>dp[x].len) dp[i]=Edge(x,i,a[x][i]);

                 else dp[i]=dp[x];

             }

             dfs(i,x);

         }

     }

 }

 void cal_kdeg()

 {

     for(int j=deg+;j<=k;j++)

     {

         dp[]=Edge(-,-,-INF);

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

         {

             if(flag[][i]) dp[i]=Edge(-,-,-INF);

             else dp[i]=Edge(-,-,-);

         }

         dfs(,-);

         int dst,maxn=-INF;

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

         {

             if(a[][i]!=- && dp[i].len-a[][i]>maxn)

             {

                 maxn=dp[i].len-a[][i];

                 dst=i;

             }

         }

         if(maxn<=) return;

         int x=dp[dst].s,y=dp[dst].t;

         flag[x][y]=flag[y][x]=false;

         flag[][dst]=flag[dst][]=true;

         ans-=maxn;

     }

 }

 void solve()

 {

     kruskal();

     cal_mdeg();

     cal_kdeg();

 }

 void print()

 {

     cout<<"Total miles driven: "<<ans<<endl;

 }

 int main()

 {

     read();

     solve();

     print();

 }

巴特西

POJ 1639 Picnic Planning：最小度限制生成树

最新文章

热门文章