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:

  1 #include <iostream>
  2 #include <stdio.h>
  3 #include <string.h>
  4 #include <algorithm>
  5 #include <map>
  6 #define MAX_N 35
  7 #define MAX_M 905
  8 #define INF 1000000000
  9 
 10 using namespace std;
 11 
 12 struct Edge
 13 {
 14     int s;
 15     int t;
 16     int len;
 17     Edge(int _s,int _t,int _len)
 18     {
 19         s=_s;
 20         t=_t;
 21         len=_len;
 22     }
 23     Edge(){}
 24     friend bool operator < (const Edge &a,const Edge &b)
 25     {
 26         return a.len<b.len;
 27     }
 28 };
 29 
 30 int n=0,m,k;
 31 int ans=0,deg=0;
 32 int par[MAX_N];
 33 int lnk[MAX_N];
 34 int minn[MAX_N];
 35 int a[MAX_N][MAX_N];
 36 bool flag[MAX_N][MAX_N];
 37 Edge dp[MAX_N];
 38 Edge edge[MAX_M];
 39 map<string,int> mp;
 40 
 41 int cal_id(const string &s)
 42 {
 43     if(mp.count(s)>0) return mp[s];
 44     mp.insert(pair<string,int>(s,++n));
 45     return n;
 46 }
 47 
 48 void read()
 49 {
 50     cin>>m;
 51     string s1,s2;
 52     int v;
 53     memset(a,-1,sizeof(a));
 54     cal_id("Park");
 55     for(int i=0;i<m;i++)
 56     {
 57         cin>>s1>>s2>>v;
 58         int id1=cal_id(s1);
 59         int id2=cal_id(s2);
 60         edge[i]=Edge(id1,id2,v);
 61         if(a[id1][id2]==-1) a[id1][id2]=a[id2][id1]=v;
 62         else a[id1][id2]=a[id2][id1]=min(a[id1][id2],v);
 63     }
 64     cin>>k;
 65 }
 66 
 67 void init_union_find()
 68 {
 69     for(int i=1;i<=n;i++)
 70     {
 71         par[i]=i;
 72     }
 73 }
 74 
 75 int find(int x)
 76 {
 77     return par[x]==x ? x : par[x]=find(par[x]);
 78 }
 79 
 80 void unite(int x,int y)
 81 {
 82     int px=find(x);
 83     int py=find(y);
 84     if(px==py) return;
 85     par[px]=py;
 86 }
 87 
 88 bool same(int x,int y)
 89 {
 90     return find(x)==find(y);
 91 }
 92 
 93 void kruskal()
 94 {
 95     init_union_find();
 96     sort(edge,edge+m);
 97     memset(flag,false,sizeof(flag));
 98     for(int i=0;i<m;i++)
 99     {
100         Edge temp=edge[i];
101         if(temp.s==1 || temp.t==1) continue;
102         if(!same(temp.s,temp.t))
103         {
104             ans+=temp.len;
105             unite(temp.s,temp.t);
106             flag[temp.s][temp.t]=flag[temp.t][temp.s]=true;
107         }
108     }
109 }
110 
111 void cal_mdeg()
112 {
113     memset(minn,0x3f,sizeof(minn));
114     for(int i=2;i<=n;i++)
115     {
116         if(a[1][i]!=-1)
117         {
118             int p=find(i);
119             if(a[1][i]<minn[p])
120             {
121                 minn[p]=a[1][i];
122                 lnk[p]=i;
123             }
124         }
125     }
126     for(int i=2;i<=n;i++)
127     {
128         if(minn[i]<INF)
129         {
130             deg++;
131             ans+=minn[i];
132             flag[1][lnk[i]]=flag[lnk[i]][1]=true;
133         }
134     }
135 }
136 
137 void dfs(int x,int p)
138 {
139     for(int i=1;i<=n;i++)
140     {
141         if(flag[x][i] && i!=p)
142         {
143             if(dp[i].len==-1)
144             {
145                 if(a[x][i]>dp[x].len) dp[i]=Edge(x,i,a[x][i]);
146                 else dp[i]=dp[x];
147             }
148             dfs(i,x);
149         }
150     }
151 }
152 
153 void cal_kdeg()
154 {
155     for(int j=deg+1;j<=k;j++)
156     {
157         dp[1]=Edge(-1,-1,-INF);
158         for(int i=2;i<=n;i++)
159         {
160             if(flag[1][i]) dp[i]=Edge(-1,-1,-INF);
161             else dp[i]=Edge(-1,-1,-1);
162         }
163         dfs(1,-1);
164         int dst,maxn=-INF;
165         for(int i=2;i<=n;i++)
166         {
167             if(a[1][i]!=-1 && dp[i].len-a[1][i]>maxn)
168             {
169                 maxn=dp[i].len-a[1][i];
170                 dst=i;
171             }
172         }
173         if(maxn<=0) return;
174         int x=dp[dst].s,y=dp[dst].t;
175         flag[x][y]=flag[y][x]=false;
176         flag[1][dst]=flag[dst][1]=true;
177         ans-=maxn;
178     }
179 }
180 
181 void solve()
182 {
183     kruskal();
184     cal_mdeg();
185     cal_kdeg();
186 }
187 
188 void print()
189 {
190     cout<<"Total miles driven: "<<ans<<endl;
191 }
192 
193 int main()
194 {
195     read();
196     solve();
197     print();
198 }