蓝书图论集合

ACM

蓝书里面的图论的题目

telephone line

二分加最短路
蓝书上面的二分总结的实在太好了
记住两种套路就可以了。

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int maxn = 1e3+10;
int G[maxn][maxn];
struct Edge{
    int v, weight;
};
struct qnode{
    int v;
    int w;
    bool operator < (const qnode &a)const {
        return w>a.w;
    }
};
bool vis[maxn];
int dis[maxn];
vector<Edge> edge[maxn];
int n, p, k;
const int INF = 1e9+10;
int dij(){
    memset(vis, 0, sizeof(vis));
    for(int i=0; i<maxn; i++) dis[i] = INF;
    priority_queue<qnode> pq;
    while(!pq.empty()) pq.pop();
    pq.push(qnode{1, 0});
    dis[1] = 0;
    while(!pq.empty()){
        qnode temp = pq.top();
        pq.pop();
        int u = temp.v;
        if(vis[u])continue;
        vis[u] = true;
        for(int i=0; i<edge[u].size(); i++){
            int v = edge[u][i].v;
            int weight = edge[u][i].weight;
            if(!vis[v]&&dis[v]>dis[u]+weight){
                dis[v] = dis[u]+weight;
                pq.push(qnode{v, dis[v]});
            }
        }
    }
    //cout<<"test:"<<dis[n]<<endl;
    return dis[n];
}
bool judge(int mid){
    for(int i=0; i<maxn; i++) edge[i].clear();
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            if(G[i][j]!=-1&&G[i][j]>mid){
                edge[i].push_back(Edge{j, 1});
            }
            else if(G[i][j]!=-1){
                edge[i].push_back(Edge{j, 0});
            }
        }
    }
    int ans = dij();
    return ans<=k?true:false;
}
int main()
{
    ios::sync_with_stdio(false);
    while(cin>>n>>p>>k){
        int u, v, w;
        memset(G, -1, sizeof(G));
        for(int i=0; i<p; i++){
            cin>>u>>v>>w;
            G[u][v] = w;
            G[v][u] = w;
        }
        int l = 0;
        int r = 1e6;
        int mid;
        for(int i=0; i<maxn; i++) edge[i].clear();
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                if(G[i][j]!=-1){
                    edge[i].push_back(Edge{j, G[i][j]});
                }
            }
        }
        int temp = dij();
        if(temp == INF){
            printf("-1\n");
            continue;
        }
        if(k == n-1){
            printf("0\n");
            continue;
        }
        int ans = -1;
        while(l<r){
            mid = (l+r)/2;
            //cout<<l<<" "<<mid<<" "<<r<<endl;
            if(judge(mid)) {
                //ans = mid;
                r = mid;
            }
            else l = mid+1;
        }
        cout<<l<<endl;
    }
    return 0;
}

闭包问题

死活调不对。。。
先mark

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
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int maxn = 30;
int ll[maxn], rr[maxn];
int d[maxn][maxn];
int d1[maxn][maxn];
int n, m;
bool cmp(int a, int b){
    return a>b;
}
bool judge(int mid){
    int bb[maxn][maxn];
    memset(bb, 0, sizeof(bb));
    for(int i=0; i<mid; i++){
        bb[ll[i]][rr[i]] = 1;
    }
    for(int k=0; k<n; k++){
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(i == j) continue;
                bb[i][j] |= bb[i][k]&bb[k][j];
            }
        }
    }
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(i == j) continue;
            if(bb[i][j] == 1&&bb[j][i] == 1){
                return true;
            }
        }
    }
    return false;
}
bool judge1(int mid){
    int bb[maxn][maxn];
    memset(bb, 0, sizeof(bb));
    for(int i=0; i<mid; i++){
        bb[ll[i]][rr[i]] = 1;
    }
    for(int k=0; k<n; k++){
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(i == j) continue;
                bb[i][j] |= bb[i][k]&bb[k][j];
            }
        }
    }
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(i == j) continue;
            if(bb[i][j] == 1&&bb[j][i] == 1){
                return false;
            }
            else if(bb[i][j] == 0&&bb[j][i] == 0){
                return false;
            }
        }
    }
    return true;
}
int main(){
    //ios::sync_with_stdio(false);
    while(cin>>n>>m&&n+m){
        char a, b;
        getchar();
        memset(d, 0, sizeof(d));
        for(int i=0; i<m; i++){
            scanf("%c<%c", &a, &b);
            getchar();
            d[a-'A'][b-'A'] = 1;
            ll[i] = a-'A';
            rr[i] = b-'A';
            //cout<<a<<" "<<b<<endl;
        }
        for(int i=0; i<n ;i++){
            for(int j=0; j<n; j++){
                d1[i][j] = d[i][j];
            }
        }
        for(int k=0; k<n; k++){
            for(int i=0; i<n; i++){
                for(int j=0; j<n; j++){
                    d[i][j] |= d[i][k]&d[k][j];
                }
            }
        }
        int type = -1;
        for(int i=0; i<n; i++){
            for(int j=0; j<n ;j++){
                if(d[i][j] == 1&&d[j][i] == 1){
                    type = 1;
                    break;
                }
            }
            if(type == 1) break;
        }
        if(type == -1){
            for(int i=0; i<n; i++){
            for(int j=0; j<n ;j++){
                if(i == j) continue;
                if(d[i][j] == 0&&d[j][i] == 0){
                    type = 0;
                    break;
                }
            }
            if(type == 0) break;
            }
        }
        if(type == -1){
            type = 2;
        }
        int tot[maxn];
        memset(tot, 0, sizeof(tot));
        if(type == 0){
            printf("Sorted sequence cannot be determined.\n");
        }
        else if(type == 2){
            int l=0;
            int r = 26;
            int mid;
            while(l<r){
                mid = (l+r)/2;
                if(judge1(mid)) r = mid;
                else l = mid+1;
            }
            for(int i=0; i<n; i++){
                for(int j=0; j<n; j++){
                    if(i == j) continue;
                    if(d[i][j] == 1){
                        tot[i]++;
                    }
                }
            }
            printf("Sorted sequence determined after %d relations: ", l);
            int mx = -1;
            bool vis[27];
            memset(vis, 0, sizeof(vis));
            for(int i=0; i<n; i++){
                mx = -1;
                for(int j=0; j<n; j++){
                    if(!vis[j]){
                        mx = max(tot[j], mx);
                    }
                }
                for(int j=0; j<n; j++){
                    if(!vis[j]&&mx == tot[j]){
                        printf("%c", j+'A');
                        vis[j] = true;
                        break;
                    }
                }
            }
            printf(".\n");
        }
        else{
            int l=0;
            int r = 26;
            int mid=0;
            while(l<r){
                mid = (l+r)/2;
                if(judge(mid)) r = mid;
                else l = mid+1;
            }
            printf("Inconsistency found after %d relations.\n", l);
        }
    }
    return 0;
}

最优比率树

注意哪里需要优化，能先算出来的东西尽量提到外面，二分的时候里面尽量的不要有循环

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
const int maxn = 1e3+10;
int n;
struct Node{
    int x, y, h;
}node[maxn];
double G[maxn][maxn];
double chang[maxn][maxn];
int cost[maxn][maxn];
const int INF = 0x3f3f3f3f;
bool vis[maxn];
double lowc[maxn];
double prim(double mid){
    double ans = 0;
    memset(vis, 0, sizeof(vis));
    vis[0] = true;
    for(int i=1; i<n; i++) lowc[i] = (cost[0][i])-mid*chang[0][i];
    for(int i=1; i<n; i++){
        double minc = INF;
        int p  = -1;
        for(int j=0; j<n; j++){
            if(!vis[j]&&minc>lowc[j]){
                minc = lowc[j];
                p = j;
            }
        }
        if(p == -1) return -1;
        ans += minc;
        vis[p] = true;
        for(int j=0; j<n; j++){
            double temp = cost[p][j]-mid*chang[p][j];
            if(!vis[j]&&lowc[j]>temp){
                lowc[j] = temp;
            }
        }
    }
    //cout<<ans<<endl;
    return ans;
}
bool judge(double mid){
    double ans = prim(mid);
    return ans<0;
}
int main()
{
    while(scanf("%d", &n)!=EOF&&n){
        int x, y, h;
        for(int i=0; i<n; i++){
            scanf("%d%d%d", &node[i].x, &node[i].y, &node[i].h);
        }
        double r = 1e2;
        for(int i=0; i<n; i++){
            for(int j=i+1; j<n; j++){
                chang[i][j] = chang[j][i] = sqrt(1.0*(node[i].x-node[j].x)*(node[i].x-node[j].x)+
                            1.0*(node[i].y-node[j].y)*(node[i].y-node[j].y));
                cost[i][j] = cost[j][i] = abs(node[i].h-node[j].h);
            }
        }
        double l = 0;
        double mid;
        while(r-l>1e-5){
            mid = (l+r)/2;
            if(judge(mid)) r = mid;
            else l = mid;
        }
        printf("%.3f\n", mid);
    }
    return 0;
}

patrol

题解

当k=1时，求树的直径然后减掉\(l-1\).
当k=2时，很简单，我们在做k=1之后把最长链上的边权全部修改为-1，再跑一遍最长链就可以了。可能有人会疑问，那-1的边又被选了那不是相当于还是选进去两次了吗？但是考虑第一次算这条边的时候加了一，第二次的时候加的是-1，相当于是这条边没有产生任何贡献。

还是好好学学别人的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
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
#include <set>
#include <cmath>
#include <stack>
using namespace std;
const int INF = 1e9+10;
const int maxn = 1e5+10;
struct Edge{
    int v;
    int weight;
};
vector<Edge> edge[maxn];
int n, k;
void init(){
    for(int i=0; i<maxn; i++) edge[i].clear();
    return ;
}
bool vis[maxn];
int dis[maxn];
int bfs(int s){
    memset(vis, 0, sizeof(vis));
    for(int i=0; i<n; i++) dis[i] = -maxn-10;
    dis[s] = 0;
    vis[s] = true;
    queue<int> q;
    while(!q.empty()) q.pop();
    int p = -1;
    q.push(s);
    while(!q.empty()){
        int u = q.front();
        q.pop();
        for(int i=0; i<edge[u].size(); i++){
            Edge e = edge[u][i];
            int v = e.v;
            int weight = e.weight;
            if(vis[v]) continue;
            else {
                if(dis[v]<dis[u]+weight){
                    dis[v] = dis[u]+weight;
                    vis[v] = true;
                    q.push(v);
                }
            }
        }
    }
    int ans = -1;
    for(int i=1; i<=n; i++){
        if(ans<dis[i]){
            p = i;
            ans = dis[i];
        }
    }
    return p;
}
stack<int> ans;
bool dfs(int s, int t, int p){
    if(s == t){
        ans.push(t);
        return true;
    }
    for(int i=0; i<edge[s].size(); i++){
        Edge e = edge[s][i];
        int v = e.v;
        if(v == p) continue;
        if(dfs(v, t, s)){
            ans.push(s);
            return true;
        }
    }
    return false;
}
int order[maxn];
int tot;
int main()
{
    scanf("%d%d", &n, &k);
    int u, v;
    init();
    for(int i=0; i<n-1; i++){
        scanf("%d%d", &u, &v);
        edge[u].push_back(Edge{v, 1});
        edge[v].push_back(Edge{u, 1});
    }
    int p = bfs(1);
    int q = bfs(p);
    int ans1 = dis[q];
    if(k == 1){
        printf("%d\n", 2*(n-1)-(dis[q]-1));
    }
    else{
        while(!ans.empty()) ans.pop();
        dfs(q, p, -1);
        tot = 0;
        while(!ans.empty()){
            order[tot++] = ans.top();
            ans.pop();
        }
        for(int i=0; i<tot-1; i++){
            for(int j=0; j<edge[order[i]].size(); j++){
                Edge &temp = edge[order[i]][j];
                if(temp.v == order[i+1]){
                    temp.weight = -1;
                    for(int k=0; k<edge[order[i+1]].size(); k++){
                        Edge &temp1 = edge[order[i+1]][k];
                        if(temp1.v == order[i]){
                            temp1.weight = -1;
                        }
                    }
                }
            }
        }
        int p1 = bfs(1);
        int q1 = bfs(p1);
        printf("%d\n", 2*(n-1)-(ans1-1)-(dis[q1]-1));
    }
    return 0;
}

未解决的问题

本文标题:蓝书图论集合

文章作者:Babydragon

发布时间:2018-05-16, 15:42:44

最后更新:2018-05-22, 19:58:21

原始链接:http://baolintian.github.io/2018/05/16/蓝书图论集合/

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

文章目录
  1. 1. telephone line
    1. 1.1. ac code
  2. 2. 闭包问题
  3. 3. 最优比率树
  4. 4. patrol
    1. 4.1. 题解
    2. 4.2. 还是怎么都调不对的code
  5. 5. 未解决的问题
{{ live2d() }}