生成树相关

自用笔记算法

生成树相关

最小瓶颈路

转跳链接

次小生成树

转跳链接

最小增量生成树(neuq 1132)

题目要求

给n-1条边构成一个最小生成树，然后q次询问，每次加入一条边，求新边和n-1条边构成的最小生成树

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<bits/stdc++.h>
#define maxn 1050
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
int n,q;
struct node{
	int to,w;
	node(int to,int w):to(to),w(w){}
};
vector<node>e[maxn];
int dis[maxn][maxn];
bool vis[maxn];
dfs(int k,int cur,int Max){
	for(int i=0;i<e[cur].size();i++){
		int next=e[cur][i].to;
		int w=e[cur][i].w;
		if(vis[next]) continue;
		vis[next]=1;
		dis[k][next]=max(Max,w);
		dfs(k,next,dis[k][next]);
	}
}
int Case=1;
int main(){
//	freopen("input.txt","r",stdin);
	while(scanf("%d",&n)!=EOF){
		for(int i=0;i<=n;i++) e[i].clear();
		mm(dis,0);
		int sum=0;
		for(int i=1;i<n;i++){
			int u,v,w;
			scanf("%d%d%d",&u,&v,&w);
			e[u].push_back(node(v,w));
			e[v].push_back(node(u,w));
			sum+=w;
		}
		for(int i=1;i<=n;i++){
			mm(vis,false);
			vis[i]=true;
			dfs(i,i,0);
		}
		scanf("%d",&q);
		 printf("Test #%d\n", ++Case);
		while(q--){
			int u,v,w;
			scanf("%d%d%d",&u,&v,&w);
			int ans=sum-dis[u][v]+min(dis[u][v],w);
			printf("%d\n",ans);
		}
	}
	return 0;
}

思路

白书P343
每次增加一条边，就会构成一个回路，去掉这个回路上权值最大的边，得到的就是最小生成树

最小有向生成树(poj 3164)

题目要求

n点m边
输入n个点的坐标和m条边的连接情况
求最小树形图

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include<bits/stdc++.h>
using namespace std;  
const int VN = 105;  
const int INF = 0x3f3f3f3f;  
template<typename Type>  
class Directed_MST{  
public:  
    void init(int _n){  
        n=_n;   
        ans = 0;  
        memset(vis, 0, sizeof(vis));  
        memset(inc, 0, sizeof(inc));  
        for(int i=0; i<=n; ++i){  
            w[i][i] = INF;  
            for(int j=i+1; j<=n; ++j) w[i][j]=w[j][i]=INF;  
        }  
    }  
    void insert(int u, int v, Type _w){  
        if(w[u][v]>_w) w[u][v] = _w;  
    }  
    Type directed_mst(int u){  
        dfs(u);  
        for(int i=1; i<=n; ++i){
        	if(!vis[i]) return -1;  
		}
        memset(vis, 0, sizeof(vis));  
        while(true){  
            for(int i=1; i<=n; ++i)if(i!=u&&!inc[i]){  
                w[i][i]=INF, pre[i] = i;  
                for(int j=1; j<=n; ++j)if(!inc[j] && w[j][i]<w[pre[i]][i]){  
                    pre[i] = j;  
                }  
            }  
            int i;  
            for(i=1; i<=n; ++i)if(i!=u&&!inc[i]){  
                int j=i, cnt=0;  
                while(j!=u && pre[j]!=i && cnt<=n) j=pre[j], ++cnt;  
                if(j==u || cnt>n) continue; 
                break;  
            }              
            if(i>n){    
                for(int i=1; i<=n; ++i)if(i!=u && !inc[i]) ans+=w[pre[i]][i];  
                return ans;  
            }  
            int j=i;  
            memset(vis, 0, sizeof(vis));  
            do{  
                ans += w[pre[j]][j], j=pre[j], vis[j]=inc[j]=true;  
            }while(j!=i);  
            inc[i] = false;
            for(int k=1; k<=n; ++k)if(vis[k]){ 
                for(int j=1; j<=n; ++j)if(!vis[j]){  
                    if(w[i][j] > w[k][j]) w[i][j] = w[k][j];  
                    if(w[j][k]<INF && w[j][k]-w[pre[k]][k] < w[j][i])  
                        w[j][i] = w[j][k] - w[pre[k]][k];  
                }    
            }  
        }  
        return ans;        
    }   
private:   
    void dfs(int u){  
        vis[u] = true;  
        for(int i=1; i<=n; ++i)if(!vis[i]&&w[u][i]<INF){  
            dfs(i);  
        }  
    }  
private:
    Type ans;   
    int n;        
    int pre[VN];   
    bool vis[VN];
    bool inc[VN];
    Type w[VN][VN];
};  
Directed_MST<double>G;  
double x[VN],y[VN];  
inline double getDist(double x1,double y1,double x2,double y2){  
    return sqrt(pow(x1-x2,2)+pow(y1-y2,2));  
}  
int main(){
//	freopen("input.txt","r",stdin);
    int n,m;  
    while(scanf("%d%d",&n,&m)!=EOF){  
        G.init(n);  
        for(int i=1;i<=n;i++) scanf("%lf%lf",&x[i],&y[i]);  
        for(int i=1;i<=m;i++){  
            int a,b;  
            scanf("%d%d",&a,&b);  
            if(a==b) continue;  
            G.insert(a,b,getDist(x[a],y[a],x[b],y[b]));  
        }  
        double ans=G.directed_mst(1);  
        if(ans<0) puts("poor snoopy");  
        else printf("%.2f\n",ans);  
    }  
    return 0;  
}

思路

白书P344
参考博客

la 5713

题目要求

白书P345
n个城市 每个城市有人口 城市与城市之间的权值是欧几里德距离 需要修一些道路使得这n个城市联通
可以选择一条道路的修建不需要钱 要求其余道路的权值尽可能小 并且选择的这条道路连接的2个城市人口尽可能多
输出总距离/两个城市的人口和 要求这个数值尽可能大

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include<bits/stdc++.h>
#define maxn 1050
#define inf 0x3f3f3f3f
using namespace std;
int t,n;
int p[maxn];
struct node{
	double x,y;
	int p;
}a[maxn];
struct Edge{
	int u,v;
	double dis;
	Edge(int u,int v,double dis):u(u),v(v),dis(dis){}
	bool operator < (const Edge& x) const{
		return dis<x.dis;
	}
};
vector<Edge>edges;
vector<int>G[maxn];
vector<double>C[maxn];
vector<int>pre_node;
double max_cost[maxn][maxn];
void init(){
	for(int i=1;i<=n;i++) p[i]=i;
	for(int i=0;i<=n;i++) G[i].clear();
	for(int i=0;i<=n;i++) C[i].clear();
	edges.clear();
	pre_node.clear();
	memset(max_cost,inf,sizeof(max_cost));
}
int find(int x){
	return x==p[x]?x:x=find(p[x]);
}
void dfs(int u,int fa,double cost){
	for(int i=0;i<pre_node.size();i++){
		int x=pre_node[i];
		max_cost[u][x]=max_cost[x][u]=max(max_cost[x][fa],cost);
	}
	pre_node.push_back(u);
	for(int i=0;i<G[u].size();i++){
		int x=G[u][i];
		if(x==fa) continue;
		dfs(x,u,C[u][i]);
	}
}
double kruskal(){
	double ans=0.0;
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			double d=sqrt((a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y));
			edges.push_back(Edge(i,j,d));
		}
	}
	sort(edges.begin(),edges.end());
	int cnt=0;
	for(int i=0;i<edges.size();i++){
		int u=edges[i].u;
		int v=edges[i].v;
		double d=edges[i].dis;
		int x=find(u);
		int y=find(v);
		if(x!=y){
			p[x]=y;
			G[u].push_back(v),G[v].push_back(u);
			C[u].push_back(d),C[v].push_back(d);
			ans+=d;
			if(++cnt==n-1) break;
		}
	}
	return ans;
}
int main(){
//	freopen("input.txt","r",stdin);
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		init();
		for(int i=1;i<=n;i++) scanf("%lf%lf%d",&a[i].x,&a[i].y,&a[i].p);
		double ans1=kruskal();
		double ans2=0;
		dfs(1,0,0.0);
		for(int i=1;i<=n;i++){
			for(int j=i+1;j<=n;j++){
				ans2=max(ans2,(double)(a[i].p+a[j].p)/(ans1-max_cost[i][j]));
			}
		}
		printf("%.2lf\n",ans2);
	}
	return 0;
}

思路

白书P345
n个城市需要联通 可以得到这是一棵树 所以先求出原图的最小生成树
并对生成树存图 C存的是从点x出发到相邻点的欧几里德距离
枚举删除的边的范围i和j 预处理出pre_cost[i][j]表示i到j点范围内权值最大的边
把这条边删除即可 即最小生成树的权值减去该边的权值 n²的复杂度就可以枚举出答案
dfs的预处理用pre_node记录之前遍历过的所有点 也是n²的复杂度
注意存生成树的时候如果存双向边 C中u和v也都要存d 因为走到fa时可以一起跳过
如果存单向边没有这个问题

uva 11865

题目要求

白书P347

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define maxn 105
#define maxm 10050
using namespace std;  
int t,n,m,cost;
struct node{
	int u,v,b,c;
}a[maxm];
struct MDST{
	int n;
	int w[maxn][maxn]; 
	int vis[maxn];    
	int ans;           
	int removed[maxn]; 
	int cid[maxn];     
	int pre[maxn];     
	int iw[maxn];     
	int max_cid;      
	void init(int n){
		this->n=n;
		for(int i=0;i<n;i++)
			for(int j=0;j<n;j++) w[i][j]=INF;
	}
	void AddEdge(int u,int v,int cost){
		w[u][v]=min(w[u][v],cost); 
	}
	int dfs(int s){   
		vis[s]=1;
		int ans=1;
		for(int i=0;i<n;i++)
			if(!vis[i] && w[s][i]<INF) ans+=dfs(i);
		return ans;
	}
	bool cycle(int u){   
		max_cid++;
		int v=u;
		while(cid[v]!=max_cid) {cid[v]=max_cid;v=pre[v];}
		return v==u;
	}
	void update(int u){   
		iw[u]=INF;
		for(int i=0;i<n;i++){
			if(!removed[i] && w[i][u]<iw[u]){
				iw[u]=w[i][u];
				pre[u]=i;
			}
		}
	}
	bool solve(int s){    
		memset(vis,0,sizeof(vis));
		if(dfs(s)!=n) return false;
		memset(removed,0,sizeof(removed));
		memset(cid,0,sizeof(cid));
		for(int u=0;u<n;u++) update(u);
		pre[s]=s; iw[s]=0; 
		ans=max_cid=0;
		for(;;){
			bool have_cycle=false;
			for(int u=0;u<n;u++) if(u!=s && !removed[u] && cycle(u)){
				have_cycle=true;
				int v=u;
				do{
					if(v!=u) removed[v]=1;
					ans+=iw[v];
					for(int i=0;i<n;i++) if(cid[i]!=cid[u] && !removed[i]){
						if(w[i][v]<INF) w[i][u]=min(w[i][u],w[i][v]-iw[v]);
						w[u][i]=min(w[u][i],w[v][i]);
						if(pre[i]==v) pre[i]=u;
					}
					v=pre[v];
				} while(v!=u);        
				update(u);
				break;
			}
			if(!have_cycle) break;
		}
		for(int i=0;i<n;i++){
			if(!removed[i]) ans+=iw[i];
		}
		return true;
	}
}g;
int main(){
//	freopen("input.txt","r",stdin);
    scanf("%d",&t);
    while(t--){
    	scanf("%d%d%d",&n,&m,&cost);
    	for(int i=1;i<=m;i++) scanf("%d%d%d%d",&a[i].u,&a[i].v,&a[i].b,&a[i].c);
		int l=0,r=1000000,ans=-1;
		while(l<=r){
    		int mid=l+r>>1;
    		g.init(n);
    		for(int i=1;i<=m;i++){
    			if(a[i].b>=mid) g.AddEdge(a[i].u,a[i].v,a[i].c);
			}
			if(!g.solve(0)){
				r=mid-1;
				continue;
			}
			int tot=g.ans;
			if(tot<=cost) ans=mid,l=mid+1;
			else r=mid-1;
		}
		if(ans==-1) puts("streaming not possible.");
		else printf("%d kbps\n",ans);
	}
    return 0;  
}

思路

可以想到有向图生成树(树形图) 固定0为起点
题目要求最小带宽最大 所以我们二分最小带宽
每次把带宽大于等于mid的边建图 带入模版
如果构不成生成树(经不过所有的点) 我们把最小带宽调小
否则判断总花费与cost的大小来二分

本文标题:生成树相关

文章作者:Hippopmonkey

发布时间:2017-10-15, 16:26:31

最后更新:2017-10-28, 01:59:11

原始链接:http://xuboming8.github.io/2017/10/15/生成树相关/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 生成树相关
    1. 1.1. 最小瓶颈路
    2. 1.2. 次小生成树
    3. 1.3. 最小增量生成树(neuq 1132)
      1. 1.3.1. 题目要求
      2. 1.3.2. 参考AC代码
      3. 1.3.3. 思路
    4. 1.4. 最小有向生成树(poj 3164)
      1. 1.4.1. 题目要求
      2. 1.4.2. 参考AC代码
      3. 1.4.3. 思路
    5. 1.5. la 5713
      1. 1.5.1. 题目要求
      2. 1.5.2. 参考AC代码
      3. 1.5.3. 思路
    6. 1.6. uva 11865
      1. 1.6.1. 题目要求
      2. 1.6.2. 参考AC代码
      3. 1.6.3. 思路
|