各位看到不足之处一定要留言指正啊!!!
###Picnic Planning POJ - 1639
第一开始没发现,这个题的数据太水了,后来不删边也能过,于是第一次提交就A了, 后来写其他题发现算法不对, 才发现被这一题坑了
最小
题目大意
有若干个点, m条路, 给出路的起点,终点,权值,并且有一个点的度数有限制小于等于K, 求这棵树最小的权值和是多少
题目解读
抽象出来就是由限制的最小生成树
限制就是某个结点的度数小于等于K
如何求解此类问题最小K度限制生成树;
具体实现步骤如下
算法顺序
1 首先利用kruskal 算法求出各连通分量的最小生成树权值的和,并记录有边(这个有边指的是该边被选出来)相连的点
2 在计算各连通分量到指定点的最小距离, 并记录谁与指定点相连
结果 构成了最小m度生成树,并求出了值,并且记录了与谁相连接
3 搜索建立初始化动态规划初始值
4 遍历求得最小权值
5 求出最小M+1 度生成树
6 直到k
7 算出从m到k这些生成树中的最小值
代码
#define me(ar) memset(ar,0,sizeof(ar)) const int INF = 1e8; //...................................................... const int LEN = 30; int K; int cnt; struct Road { int x,y; int weight; bool operator <(const Road &a) const { return weight < a.weight; } } road[LEN*LEN+10];//邻接表存边,Kruskal 算法要用 int Matrix[LEN][LEN];//邻接矩阵 int sign[LEN][LEN];//记录那些边是相连的 int vis[LEN];//记录是否相连 int F[LEN];//并查集所用 int Father[LEN];//由i到i+1度限制生成树需要用动态规划求解,用来状态转移 int Best[LEN];//Best[i] 指的是由当前节点到park这些边中最长边是多少 int Find(int x)//并查集所用Find函数 { return x == F[x]?x:F[x] = Find(F[x]); } void Dfs(int x)//Dfs动态规划记忆化搜索 { // vis[x] = 1; for(int i = 1;i <= cnt; ++i ) { if(sign[i][x]&!vis[i])//如果有边相连并且下一个节点没有被访问 { if(x==0) { Best[i] = -INF;//与park 直接相连的边不能删除 } else { Best[i] = max(Best[x],Matrix[x][i]);//状态转移方程 } Father[i] = x; vis[i] = 1; Dfs(i); } } } int main(void) { int N; while(cin>>N) { //初始化并查集数组 for(int i = 0;i < LEN; ++i) F[i] = i; me(sign);//初始化标记数组 me(vis); //初始化邻接矩阵 for(int i = 0;i < LEN; ++i) for(int j = 0;j < LEN; ++j) Matrix[i][j] = INF; cnt = 0;//用来记录共有多少个节点 set<string> se; map<string,int> ma;//将地点编号 ma["Park"] = 0;//将park 加入节点 se.insert("Park"); string s1,s2; int a,b; int weight = 0; for(int i = 0; i < N; ++i) { cin>>s1>>s2>>weight; if(se.find(s1)!=se.end()) a = ma[s1];//如果节点已编号,则直接使用 else a = ma[s1] = ++cnt,se.insert(s1);//如果没有编号,编号 if(se.find(s2)!=se.end()) b = ma[s2]; else b = ma[s2] = ++cnt,se.insert(s2); Matrix[a][b] = Matrix[b][a] = weight; road[i].x = a; road[i].y = b; road[i].weight = weight; } //cout<<se.size()<<endl; cin>>K;//最小k度生成树 int ans = 0;//kruskal 算法求最小生成树 sort(road,road+N); for(int i = 0;i < N; ++i) { int x = road[i].x; int y = road[i].y; weight = road[i].weight; if(x==0||y==0)//去除掉park这个点 continue; int xx = Find(x); int yy = Find(y); if(xx!=yy) { F[xx] = F[yy]; ans += weight; sign[x][y] = sign[y][x] = 1; } } int Min[LEN];//用来记录每一个最小生成树到park点的最小路径 for(int i = 0;i < LEN; ++i) Min[i] = INF;//初始化 int index[LEN];//用来记录最小路径的点 for(int i = 1;i <= cnt; ++i) { if(Matrix[i][0]<Min[Find(i)]) { Min[Find(i)] = Matrix[i][0]; index[Find(i)] = i; } } //// cout<<se.size()<<endl; int m = 0;//用来记录除去park点即0点之后共有多少个连通分量 for(int i = 1;i <= cnt; ++i) { if(Min[i] != INF) { ans += Min[i]; sign[index[i]][0] = sign[0][index[i]] = 1;//将这个最小路径的点与park相连 m++; } } int MMin = ans; for(int i = m + 1; i <= K; ++i)//从m+1到K求最小i度生成树 { me(vis); vis[0] = 1; Dfs(0); int select = -1;//select用来记录选择哪个与park点相连是最小的 int sum = INF; for(int i = 1;i <= cnt; ++i) { if(!sign[0][i] && Matrix[0][i] != INF) { if(Matrix[i][0]-Best[i]<sum) { select = i; sum = Matrix[i][0]-Best[i]; } } } if(select == -1)//如果找不到,就跳出循环 break; ans += sum; sign[select][0] = sign[0][select] = 1; MMin = min(MMin,ans); for(int i = select; i != 0; i = Father[i]) { if(Matrix[Father[i]][i]==Best[select]) { sign[i][Father[i]] = sign[Father[i]][i] = 0; break; } } } printf("Total miles driven: %d\n",MMin); // cout<<MMin<<endl; } return 0; } 类似题目
####Arctic Network POJ - 2349
const int LEN = 500+100;
int S,P;
double Matrix[LEN][LEN];
int sign[LEN][LEN];
int vis[LEN];
int x[LEN];
int y[LEN];
double dis[LEN];
int Father[LEN];
double Best[LEN];
void Dfs(int x)
{
// cout<<1<<endl;
for(int i = 1; i <= P; ++i)
{
if(!vis[i]&&sign[i][x])
{
if(x==0)
Best[i] = -INF;
else
Best[i] = max(Best[x],Matrix[x][i]);
vis[i] = 1;
Dfs(i);
Father[i] = x;
}
}
}
int main(void)
{
int N;
cin>>N;
while(N--)
{
cin>>S>>P;
me(sign);
me(vis);
for(int i = 1; i <= P; ++i)
{
scanf("%d %d",&x[i],&y[i]);
}
Matrix[0][1] = Matrix[1][0] = 0;
sign[0][1] = sign[1][0]= 1;
for(int i = 2; i <= P; ++i)
Matrix[0][i] = Matrix[i][0] = INF;
for(int i = 1; i <= P; ++i)
{
for(int j = i+1; j <= P; ++j)
{
Matrix[i][j] = Matrix[j][i] = sqrt((double)((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])));
}
}
//prim算法求解
vis[1] = 1;
int Left = P - 1;
for(int i = 1; i <= P; ++i)
{
dis[i] = Matrix[1][i];
Father[i] = 1;
}
double Min = INF;
int index = 0;
while(Left--)//prim算法
{
Min = INF;
for(int i = 1; i <= P; ++i)
{
if(!vis[i]&&dis[i]<Min)
{
Min = dis[i];
index = i;
}
}
vis[index] = 1;
if(Min == INF)
break;
sign[index][Father[index]] = sign[Father[index]][index] = 1;
for(int i = 1; i <= P; ++i)
{
if(!vis[i]&&Matrix[index][i]<dis[i])
{
dis[i] = Matrix[index][i];
Father[i] = index;
}
}
}
double Max;
for(int k = 2; k <= S; ++k)
{
me(vis);
vis[0] = 1;
Father[0] = -1;
Dfs(0);
Max = -INF;
index = 0;
for(int i = 1; i <= P; ++i)
{
if(Max<Best[i])
{
Max =Best[i];
index = i;
}
}
sign[index][0] = sign[0][index] = 1;//将边加进去
for(int i = index; Father[i] != -1; i = Father[i] )//删边
{
if(Max == Matrix[Father[i]][i])
{
sign[i][Father[i]] = sign[Father[i]][i] = 0;
break;
}
}
}
me(vis);
vis[0] = 1;
// Father[0] = -1;
Dfs(0);
Max = -INF;
index = 2;
for(int i = 1; i <= P; ++i)
{
if(Max<Best[i])
{
Max =Best[i];
index = i;
}
}
if(Max == -INF)
cout<<0<<endl;
else
printf("%.2f\n",Max);
}
return 0;
}
京公网安备 11010502036488号