最小度限制生成树

Posted on 2011-05-23 21:05 Mato_No1 阅读(488) 评论(0)  编辑 收藏 引用 所属分类: 图算法
给出一个带边权连通无向图,当中指定一个点V0,要求这个图的一个生成树,使得树中V0点的度数(和V0点关联的边数)刚好为一个指定值P,求满足此条件的边权和最小的生成树。

【算法】(某神犇的论文里有详细证明,这里省略了囧……)
设l[i]为连接图中点V0与点i之间的边的长度(若有多条边取权值最小的,若没有边则为无穷大)。
(1)在图中删除点V0,新的图不一定是连通图,设其有B个连通块;
(2)若P<B则无解,否则转下一步;
(3)对这B个连通块分别求最小生成树,得到一个生成森林。然后在图中重新加入点V0,对每个连通块,找出该连通块内l值最小的点V',添加边(V0, V'),这样就得到了一棵初始的生成树,或者说,这是V0点度数为B的最小的生成树;
(4)然后就是不断往里面加入与V0相关联的边。从V0点开始,对整棵生成树BFS遍历,对每个点i,找到目前的生成树中从V0到i的路径上权值最大的边,设E_len[i]为这条边的权值,E_No[i]为这条边的编号(由于本沙茶使用的是DL边表,故记录编号),这个东东的求法很容易,省略;
(5)最后,枚举除V0点外的每个点,找到(E_len[i]-l[i])值最大的点i,然后在图中删除边E_No[i],加入边(V0, i),这样得到的仍然是原图的生成树,且V0的度数增加1;
(6)重复以上过程(P-B)次即得结果。

【实现注意】
为了编程实现更加方便,注意以下几点:
(1)一开始不加入V0,而不是加入了再删去(但各点l值要在输入时求出);
(2)一开始不用先求出B的值,而是先求出最小生成森林(用Kruskal,不断加边,直到加到不能再加为止)和初始生成树,再遍历初始生成树得到B值;
(3)由于涉及删边,一定要用DL边表。

【代码】(PKU1639,注意这题是求V0度数不超过给定值P的最小生成树,简单改装即可):
#include <iostream>
#include 
<stdio.h>
#include 
<string>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re2(i, l, r) for (int i=l; i<r; i++)
const int MAXN = 30, MAXM = 5000, MAXLEN = 20, INF = ~0U >> 2;
struct edge {
    
int a, b, len, pre, next;
} ed[MAXM 
+ MAXM];
struct edge0 {
    
int a, b, len;
} ed0[MAXM];
int n, m, m0 = 0, P, B = 0, l[MAXN], u[MAXN], B_No[MAXN], q[MAXN], E_No[MAXN], E_len[MAXN], res = 0;
string NAMELIST[MAXN];
bool vst[MAXN];
void add_edge0(int a, int b, int len)
{
    ed0[m0].a 
= a; ed0[m0].b = b; ed0[m0++].len = len;
}
void init_d()
{
    re(i, n) ed[i].a 
= ed[i].pre = ed[i].next = i;
    
if (n % 2) m = n + 1else m = n;
}
void add_edge(int a, int b, int len)
{
    ed[m].a 
= a; ed[m].b = b; ed[m].len = len; ed[m].pre = ed[a].pre; ed[m].next = a; ed[a].pre = m; ed[ed[m].pre].next = m++;
    ed[m].a 
= b; ed[m].b = a; ed[m].len = len; ed[m].pre = ed[b].pre; ed[m].next = b; ed[b].pre = m; ed[ed[m].pre].next = m++;
}
void del_edge(int No)
{
    ed[ed[No].pre].next 
= ed[No].next; ed[ed[No].next].pre = ed[No].pre;
    ed[ed[No 
^ 1].pre].next = ed[No ^ 1].next; ed[ed[No ^ 1].next].pre = ed[No ^ 1].pre;
}
void init()
{
    n 
= 1; NAMELIST[0= "Park"int m_;
    scanf(
"%d"&m_); char ch = getchar(), s01[MAXLEN], s02[MAXLEN]; int No1, No2, l0, tmp;
    re(i, MAXN) l[i] 
= INF;
    re(i, m_) {
        scanf(
"%s %s %d", s01, s02, &l0); ch = getchar();
        No1 
= -1; re(j, n) if (NAMELIST[j] == s01) {No1 = j; break;} if (No1 == -1) NAMELIST[No1 = n++= s01;
        No2 
= -1; re(j, n) if (NAMELIST[j] == s02) {No2 = j; break;} if (No2 == -1) NAMELIST[No2 = n++= s02;
        
if (No1 > No2) {tmp = No1; No1 = No2; No2 = tmp;}
        
if (No1) add_edge0(No1, No2, l0); else if (l0 < l[No2]) l[No2] = l0;
    }
    scanf(
"%d"&P);
}
int cmp(const void *s1, const void *s2)
{
    
return ((edge0 *)s1)->len - ((edge0 *)s2)->len;
}
int find_root(int x)
{
    
int r = x, r0 = x, tmp;
    
while (u[r] >= 0) r = u[r];
    
while (u[r0] >= 0) {tmp = u[r0]; u[r0] = r; r0 = tmp;}
    
return r;
}
void uni(int r1, int r2)
{
    
int sum = u[r1] + u[r2];
    
if (u[r1] >= u[r2]) {u[r1] = r2; u[r2] = sum;} else {u[r2] = r1; u[r1] = sum;}
}
void prepare()
{
    qsort(ed0, m0, 
12, cmp);
    re2(i, 
1, n) u[i] = -1; init_d();
    
int x1, x2, l0, r1, r2;
    re(i, m0) {
        x1 
= ed0[i].a; x2 = ed0[i].b; l0 = ed0[i].len; r1 = find_root(x1); r2 = find_root(x2);
        
if (r1 != r2) {uni(r1, r2); add_edge(x1, x2, l0); res += l0;}
    }
    re2(i, 
1, n) B_No[i] = -1;
    
int Best, Best_No;
    re2(i, 
1, n) if (B_No[i] == -1) {
        B_No[i] 
= B; Best = l[i]; Best_No = q[0= i;
        
int j, k;
        
for (int front=0, rear=0; front<=rear; front++) {
            j 
= q[front];
            
for (int p=ed[j].next; p != j; p=ed[p].next) {
                k 
= ed[p].b;
                
if (B_No[k] == -1) {
                    B_No[k] 
= B; q[++rear] = k; if (l[k] < Best) {Best = l[k]; Best_No = k;}
                }
            }
        }
        add_edge(
0, Best_No, Best); res += Best; B++;
    }
}
void solve()
{
    vst[
0= 1;
    re2(P0, B, P) {
        re2(i, 
1, n) {E_len[i] = INF; vst[i] = 0;} q[0= 0;
        
int i, j, l0;
        
for (int front=0, rear=0; front<=rear; front++) {
            i 
= q[front];
            
for (int p=ed[i].next; p != i; p=ed[p].next) {
                j 
= ed[p].b; l0 = ed[p].len;
                
if (!vst[j]) {
                    vst[j] 
= 1; q[++rear] = j;
                    
if (E_len[i] > l0) {E_len[j] = E_len[i]; E_No[j] = E_No[i];} else {E_len[j] = l0; E_No[j] = p;}
                }
            }
        }
        
int Best = 0, Best_No, Best_v;
        re2(i, 
1, n) {
            l0 
= E_len[i] - l[i];
            
if (l0 > Best) {Best = l0; Best_No = E_No[i]; Best_v = i;};
        }
        
if (Best) {del_edge(Best_No); add_edge(0, Best_v, l[Best_v]); res -= Best;} else break;
    }
}
void pri()
{
    printf(
"Total miles driven: %d\n", res);
}
int main()
{
    init();
    prepare();
    solve();
    pri();
    
return 0;
}


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理