Day8 图论相关知识的补遗

ACM

知识补遗

限制顶点度数的MST

poj1639 Picnic Planning
先构成一个森林，然后不断的增加度数，来减少花费。有点枚举边的意思。
可以当成模板来积累

ac code

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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
#include <cmath>
#include <map>
#include <algorithm>
using namespace std;
const int maxn = 105;
const int INF = 0x3f3f3f3f;
map<string, int> mp;
string s1, s2;
int w;
int n, k;
int m;
int ans = 0;
int cnt;
bool connect[maxn][maxn];
int minedge[maxn];
int key_point[maxn];
struct Edge{
    int u, v, w;
    Edge(){}
    Edge(int _u, int _v, int _w): u(_u), v(_v), w(_w){}
};
bool cmp(Edge a, Edge b){
    return a.w<b.w;
}
int fa[maxn];
int find_fa(int x){
    int a = x;
    while(x!=fa[x]){
        x = fa[x];
    }
    while(a!=fa[a]){
        int z = a;
        a = fa[a];
        fa[z] = x;
    }
    return x;
}
void uni(int u, int v){
    int fau = find_fa(u), fav = find_fa(v);
    if(fau!=fav) fa[fau] = fav;
}
int g[maxn][maxn];
vector<Edge> edge;
void kruskal(){
    sort(edge.begin(), edge.end(), cmp);
    for(int i=0; i<edge.size(); i++){
        int u=edge[i].u;
        int v = edge[i].v;
        int w = edge[i].w;
        if(u == 1 || v == 1) continue;
        int fau = find_fa(u), fav = find_fa(v);
        if(fau!=fav){
            fa[fau] = fav;
            ans+=w;
            connect[u][v] = connect[v][u] = true;
        }
    }
}
Edge dp[maxn];
void dfs(int u, int fa){
    for(int i=2; i<cnt; i++){
        //未连边
        if(i == fa||!connect[u][i]) continue;
        if(dp[i].w == -1){
            if(dp[u].w>g[u][i]) dp[i] = dp[u];
            else {
                dp[i].u = u;
                dp[i].v = i;
                dp[i].w = g[u][i];
            }
        }
        dfs(i, u);
    }
}
void solve(){
    for(int i=2; i<cnt; i++){
        if(g[1][i]!=INF){
            int group = find_fa(i);
            if(minedge[group]>g[1][i]){
                minedge[group] = g[1][i];
                key_point[group] = i;
            }
        }
    }
    for(int i=1; i<cnt; i++){
        if(minedge[i]!=INF){
            m++;
            connect[1][key_point[i]] = connect[key_point[i]][1] = true;
            ans+=g[1][key_point[i]];
        }
    }
    for(int i=m+1; i<=k; i++){
        for(int i=0; i<maxn; i++) dp[i].w = -1;
        //memset(dp, -1, sizeof(dp));
        dp[1].w = -INF;
        for(int j=2; j<cnt; j++){
            if(connect[1][j]) dp[j].w = -INF;
        }
        //cout<<"in"<<endl;
        dfs(1, -1);
        //cout<<"out"<<endl;
        int idx, minimum = INF;
        for(int j=2; j<cnt; j++){
            if(minimum>g[1][j]-dp[j].w){
                minimum = g[1][j]-dp[j].w;
                idx = j;
            }
        }
        //cout<<minimum<<endl;
        if(minimum>=0) break;
        connect[1][idx] = connect[idx][1] = true;
        int u=dp[idx].u, v = dp[idx].v;
        connect[u][v] = connect[v][u] = false;
        ans+=minimum;
    }
}
void init(){
    mp.clear();
    edge.clear();
    memset(g, 0x3f, sizeof(g));
    ans = 0;
    m=0;
    memset(connect, 0, sizeof(connect));
    memset(minedge, 0x3f, sizeof(minedge));
    mp["Park"] = 1;
    for(int i=0; i<maxn; i++) fa[i] = i;
}
int main()
{
    ios::sync_with_stdio(false);
    while(cin>>n){
        init();
        cnt = 2;
        for(int i=1; i<=n; i++){
            cin>>s1>>s2>>w;
            if(!mp[s1]) mp[s1] = cnt++;
            if(!mp[s2]) mp[s2] = cnt++;
            int u=mp[s1], v = mp[s2];
            g[u][v] = g[v][u] = min(w, g[u][v]);
            edge.push_back(Edge(u, v, w));
        }
        cin>>k;
        kruskal();
        //cout<<ans<<endl;
        solve();
        cout<<"Total miles driven: "<<ans<<"\n";
    }
    return 0;
}
``` 
```c++

BCD

这三道题分别是01分数规划，最优比率生成树、最优比率环
下面有一个非常详细的博客：
三种模型的总结

B

二分答案就可以了

C 最优比率生成树

二分答案，然后用prime跑最小生成树

D 最优比率环

二分答案，用SPFA判断是否存在负环
参考博客

ac code

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
#include<cstdio>
#include<cstring>
#include<queue>
#define eps 1e-3
#define MAXN 1010
using namespace std;
struct T
{
	int v;
	int w;
	int next;
}edge[5005];
int cnt,head[MAXN];
void add_edge(int u,int v,int w)
{
	edge[cnt].v = v;
	edge[cnt].w = w;
	edge[cnt].next = head[u];
	head[u] = cnt++;
}
int n,m;
int w[MAXN];
double dis[MAXN];
bool inque[MAXN];
int vis[MAXN];
bool SPFA(double R)//SPFA判断负权环
{
	queue<int> myque;
	memset(inque,0,sizeof inque);
	memset(vis,0,sizeof vis);
	for(int i = 1; i <= n; i++)
		dis[i] = 1e15;
	myque.push(1);
	dis[1] = 0;
	inque[1] = 1;
	vis[1]++;
	while(!myque.empty())
	{
		int u = myque.front();
		myque.pop();
		inque[u] = 0;
		for(int i = head[u]; i != -1; i = edge[i].next)
		{
			int v = edge[i].v;
			int y = edge[i].w;
			if(dis[u] + R*y - w[u] < dis[v])
			{
				dis[v] = dis[u] + R*y - w[u];
				if(!inque[v])
				{
					myque.push(v);
					inque[v] = 1;
					vis[v]++;
					if(vis[v] > n) return 1;
				}
			}
		}
	}
	return 0;
}
int main()
{
	memset(head,-1,sizeof head);
	scanf("%d%d",&n,&m);
	for(int i = 1; i <= n; i++)
		scanf("%d",&w[i]);
	for(int i = 1; i <= m; i++)
	{
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		add_edge(a,b,c);
	}
	double l = 0,r = 10000,mid;
	while(r - l > eps)
	{
		mid = (l+r)/2;
		if(SPFA(mid)) l = mid;//由于我们是把权值取反了的，因此题解中的R过大变成了R过小
		else r = mid;
	}
	printf("%.2f\n",l);
	return 0;
}

E 比较难的最小生成树(还没有写)

F 裸最小树形图

把原来的代码数据类型改为double就可以了。
注意用%f输出（垃圾poj

ac code

1
2

G、H最小点覆盖

最小点覆盖的定义是用最少的点数，去覆盖所有的边。
最小覆盖=最大匹配

I 最小路径覆盖

最小路径覆盖= n-最大匹配
这题若两个人之间时间没有冲撞，就连一条边

J最大独立集

选出若干个点，使得它们之间没有任何的连边
这道题我们首先要判断每一个序号对应的是男还是女（黑白染色）。但是最后我们并没有这样做，而是直接将最大的二分匹配的答案除以2，最后的答案就是n-匹配数/2

k

一个二分图的题，但是处理的过程比较的麻烦，待补

L 六人定理

6个人中，必有三个人之间是好朋友，或者完全不认识。
我们只要暴力的去同图大小为3,4,5的图就行了，6以上的必然是存在的

ac code

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m, k;
bool M[55][55];
const int MOD = 1e9+7;
ll pow_mod(int a, int b){
	ll ans = 1;
	while (b){
		if (b & 1) ans = ((ll)ans*a) % MOD;
		a = ((ll)a*a) % MOD;
		b >>= 1;
	}
	return ans;
}
int C(int n, int m){
	ll p = 1, q = 1;
	while (m){
		p = (p*n) % MOD;
		q = (q*m) % MOD;
		m--;
		n--;
	}
	return (p * pow_mod(q, MOD - 2)) % MOD;
}
inline bool check3(int a, int b, int c){
	return (M[a][b] & M[b][c] & M[c][a]) || (!M[a][b] & !M[b][c] & !M[c][a]);
}
inline bool check4(int a, int b, int c, int d){
	if ((M[a][b] & M[b][c] & M[c][a]) || (!M[a][b] & !M[b][c] & !M[c][a])) return true;
	if ((M[a][b] & M[b][d] & M[d][a]) || (!M[a][b] & !M[b][d] & !M[d][a])) return true;
	if ((M[a][c] & M[c][d] & M[d][a]) || (!M[a][c] & !M[c][d] & !M[d][a])) return true;
	if ((M[b][c] & M[c][d] & M[d][b]) || (!M[b][c] & !M[c][d] & !M[d][b])) return true;
	return false;
}
inline bool check5(int a, int b, int c, int d, int e){
	if ((M[a][b] & M[b][c] & M[c][a]) || (!M[a][b] & !M[b][c] & !M[c][a])) return true;
	if ((M[a][b] & M[b][d] & M[d][a]) || (!M[a][b] & !M[b][d] & !M[d][a])) return true;
	if ((M[a][c] & M[c][d] & M[d][a]) || (!M[a][c] & !M[c][d] & !M[d][a])) return true;
	if ((M[b][c] & M[c][d] & M[d][b]) || (!M[b][c] & !M[c][d] & !M[d][b])) return true;
	if ((M[e][a] & M[e][b] & M[a][b]) || (!M[e][a] & !M[e][b] & !M[a][b])) return true;
	if ((M[e][a] & M[e][c] & M[a][c]) || (!M[e][a] & !M[e][c] & !M[a][c])) return true;
	if ((M[e][a] & M[e][d] & M[a][d]) || (!M[e][a] & !M[e][d] & !M[a][d])) return true;
	if ((M[e][b] & M[e][c] & M[b][c]) || (!M[e][b] & !M[e][c] & !M[b][c])) return true;
	if ((M[e][b] & M[e][d] & M[b][d]) || (!M[e][b] & !M[e][d] & !M[b][d])) return true;
	if ((M[e][c] & M[e][d] & M[c][d]) || (!M[e][c] & !M[e][d] & !M[c][d])) return true;
	return false;
}
int main(){
	int _;
	cin>>_;
	for(int kase = 1; kase <= _; kase++){
		cin >> n >> m;
		memset(M, 0, sizeof(M));
		while (m--){
			int u, v;
			cin >> u >> v;
			M[u][v] = M[v][u] = 1;
		}
		int ans = 0;
		for (int a = 1; a <= n; a++)
		for (int b = a + 1; b <= n; b++)
		for (int c = b + 1; c <= n; c++)
			ans += check3(a, b, c);
		for (int a = 1; a <= n; a++)
		for (int b = a + 1; b <= n; b++)
		for (int c = b + 1; c <= n; c++)
		for (int d = c + 1; d <= n; d++)
			ans += check4(a, b, c, d);
		for (int a = 1; a <= n; a++)
		for (int b = a + 1; b <= n; b++)
		for (int c = b + 1; c <= n; c++)
		for (int d = c + 1; d <= n; d++)
		for (int e = d + 1; e <= n; e++)
			ans += check5(a, b, c, d, e);
		for (int i = 6; i <= n; i++)
			ans = (ans + C(n, i)) % MOD;
		printf("Case #%d: %d\n", kase, ans);
	}
	return 0;
}

未解决的问题

本文标题:Day8 图论相关知识的补遗

文章作者:Babydragon

发布时间:2018-08-11, 20:29:27

最后更新:2018-08-13, 10:13:44

原始链接:http://baolintian.github.io/2018/08/11/Day8-图论相关知识的补遗/

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

文章目录
  1. 1. 限制顶点度数的MST
    1. 1.0.1. ac code
  • 2. BCD
    1. 2.1. B
    2. 2.2. C 最优比率生成树
    3. 2.3. D 最优比率环
      1. 2.3.1. ac code
  • 3. E 比较难的最小生成树(还没有写)
  • 4. F 裸最小树形图
    1. 4.1. ac code
  • 5. G、H最小点覆盖
  • 6. I 最小路径覆盖
  • 7. J最大独立集
  • 8. k
  • 9. L 六人定理
    1. 9.1. ac code
  • 10. 未解决的问题
    • {{ live2d() }}