分类目录归档:图论

洛谷 车站分级

题号:P1983
算法标签:拓扑排序
洛谷题解地址:https://www.luogu.org/wiki/show?name=%E9%A2%98%E8%A7%A3+P1983
参考题解:作者: chenshaoqian 更新时间: 2016-09-25 21:08
作者: mangoyang 更新时间: 2016-09-24 17:20

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
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<list>
#include<stack>
using namespace std;
#define virtual_point_start 1000
int n, m;
int s[1005];
int virtual_point_ptr = virtual_point_start;
int indegree[3000];
int pass[1005][1005];
int path_dis[3000];
list<int> edge[3000];
vector<int> t_edge_to;
stack<int> cur_level;
bool execute(){
    while (!cur_level.empty())cur_level.pop();
    for (int i = 1; i <= n; i++){
        if (indegree[i] == 0){
            cur_level.push(i);
            indegree[i] = -1;
        }
    }
    for (int i = 1001; i <= virtual_point_ptr; i++){
        if (indegree[i] == 0){
            cur_level.push(i);
            indegree[i] = -1;
        }
    }
    if (cur_level.empty())return false;
    while (!cur_level.empty()){
        int cur = cur_level.top();
        cur_level.pop();
        for (list<int>::iterator iter = edge[cur].begin(); iter != edge[cur].end(); iter++){
            indegree[*iter]--;
            int point_dis = (cur <= 1000);
            path_dis[*iter] = max(path_dis[*iter],path_dis[cur] + point_dis);
        }
    }
    return true;
}
int main(){
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= m; i++){
        cin >> s[i];
        for (int j = 1; j <= s[i]; j++)cin >> pass[i][j];
        t_edge_to.clear();
        int ptr = 1;
        for (int j = pass[i][1]; j <= pass[i][s[i]]; j++){
            if (pass[i][ptr] == j)ptr++;
            else t_edge_to.push_back(j);
        }
        virtual_point_ptr++;
        for (vector<int>::iterator iter = t_edge_to.begin(); iter != t_edge_to.end(); iter++){
            edge[virtual_point_ptr].push_back(*iter);
            indegree[*iter]++;
        }
        for (int se = 1; se <= s[i]; se++){
            edge[pass[i][se]].push_back(virtual_point_ptr);
            indegree[virtual_point_ptr]++;
        }
    }
    while (execute());
    int ans = 0;
    for (int i = 1; i <= n; i++){
        ans = max(ans, path_dis[i]);
    }
    cout << ans+1;
}

CodeVS 1077 多源最短路 模版

从来没写过多源最短路,明天就NOIP初赛了,今天晚上写一下。。。。

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
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<queue>
#include<map>
#include<list>
#include<cstring>
#include<cassert>
#include<cmath>
using namespace std;
long long arr[105][105];
int n;
long long q;
int main(){
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= n; j++){
            cin >> arr[i][j];
        }
    }
    for (int k = 1; k <= n; k++){
        for (int i = 1; i <= n; i++){
            for (int j = 1; j <= n; j++){
                arr[i][j] = min(arr[i][j], arr[i][k] + arr[k][j]);
            }
        }
    }
    cin >> q;
    for (long long i = 1; i <= q; i++){
        int s, e;
        cin >> s >> e;
        cout << arr[s][e] << endl;
    }
    return 0;
}

洛谷/USACO 骑马修栅栏 Riding the Fences

洛谷题号:P2731
参考题解:作者: 约修亚_RK 更新时间: 2016-10-28 23:59
作者: 曹彦臣 更新时间: 2016-09-07 21:31
https://www.luogu.org/wiki/show?name=%E9%A2%98%E8%A7%A3+P2731

一开始用的是Fleury’s algorithm,T了1个点:

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
#include<iostream>
#include<string>
#include<algorithm>
#include<queue>
#include<list>
#include<cstring>
using namespace std;
int f, rk = 0, mnode = 0,ans;
int arr[505][505];
int path[10000];
int degree[505];
bool check(int num){
    for (int i = 1; i <= mnode; i++){
        for (int j = 1; j <= mnode; j++){
            if (arr[i][j]!=0)
                return false;
        }
    }
    ans = num;
    return true;
}
bool dfs(int node,int depth){
    path[depth] = node;
    bool flag = false;
    for (int i = 1; i <= mnode; i++){
        if (arr[node][i]){
            flag = true;
            arr[node][i]--;
            arr[i][node]--;
            if (dfs(i, depth + 1))return true;
            arr[node][i]++;
            arr[i][node]++;
        }
    }
    if (!flag&&check(depth))return true;
    path[depth] = 0;
    return false;
}
int main(){
    ios::sync_with_stdio(false);
    cin >> f;
    for (int i = 1; i <= f; i++){
        int u, v;
        cin >> u >> v;
        arr[u][v]++;
        arr[v][u]++;
        degree[u]++;
        degree[v]++;
        mnode = max(mnode, u);
        mnode = max(mnode, v);
    }
    bool odd = false;
    for (int i = 1; i <= mnode; i++){
        if (degree[i] % 2 == 1){
            odd = true;
            if (dfs(i, 1))break;
        }
    }
    if (!odd)dfs(1, 1);
    for (int i = 1; i <= ans; i++){
        cout << path[i] << endl;
    }
}

后来改用Hierholzer’s algorithm,A了。

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
int f, rk = 0, mnode = 0,ans;
int arr[505][505];
int path[10000];
int degree[505];
bool check(int num){
    for (int i = 1; i <= mnode; i++){
        for (int j = 1; j <= mnode; j++){
            if (arr[i][j]!=0)
                return false;
        }
    }
    ans = num;
    return true;
}
void Euler(int node){ //新版本
    for (int i = 1; i <= mnode; i++){
        while (arr[node][i] > 0){
            arr[node][i]--;
            arr[i][node]--;
            Euler(i);
        }
    }
    path[++ans] = node;
}
int main(){
    ios::sync_with_stdio(false);
    cin >> f;
    for (int i = 1; i <= f; i++){
        int u, v;
        cin >> u >> v;
        arr[u][v]++;
        arr[v][u]++;
        degree[u]++;
        degree[v]++;
        mnode = max(mnode, u);
        mnode = max(mnode, v);
    }
    bool odd = false;
    for (int i = 1; i <= mnode; i++){
        if (degree[i] % 2 == 1){
            odd = true;
            Euler(i);
            break;
        }
    }
    if (!odd)Euler(1);
    for (int i = ans; i >=1; i--){
        cout << path[i] << endl;
    }
}

洛谷 牛的旅行 Cow Tours

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
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<utility>
#include<algorithm>
#include<map>
#include<queue>
#include<vector>
#include<list>
#include<functional>
#include<string>
#define INF 0x7fffffff
using namespace std;
int n;
int posx[200], posy[200];
double arr[200][200];
double sglgdis[200];
inline double distance(int x1, int y1, int x2, int y2) { //最后开根号,函数中未开根号
    return sqrt((double)(x1 - x2)*(x1 - x2) + (double)(y1 - y2)*(y1 - y2));
}
void floyd() {
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (arr[i][j] > arr[i][k] + arr[k][j]) {
                    arr[i][j] = arr[i][k] + arr[k][j];
                }
            }
        }
    }
}

int main() {
    for (int i = 0; i <= 199; i++) {
        for (int j = 0; j <= 199; j++) {
            arr[i][j] = INF;
        }
    }
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &posx[i], &posy[i]);
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            int t;
            scanf("%1d", &t);
            arr[i][j] = (t||i==j) ? distance(posx[i], posy[i], posx[j], posy[j]) : INF;
            if (i == j)arr[i][j] = 0;
        }
    }
    floyd();
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (arr[i][j] != INF&&arr[i][j] > sglgdis[i]) {
                sglgdis[i] = arr[i][j];
            }
        }
    }
    double mmm = INF;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (arr[i][j] < INF)continue;
            double t = sglgdis[i] + sglgdis[j] + distance(posx[i], posy[i], posx[j], posy[j]);
            if (t < mmm)mmm = t;
        }
    }
    for (int i = 1; i <= n; i++) {
        if (sglgdis[i] > mmm)mmm = sglgdis[i];
    }
    printf("%.6lf\n", mmm);
}

USACO Section 2.3 Controlling Companies

STDIN/STDOUT

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
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<utility>
#include<algorithm>
#include<map>
#include<vector>
#include<list>
#include<functional>
#include<string>
using namespace std;
int u[10005], v[10005], w[10005], first[105], nxt[10005];
int n, m;
bool control[105],visited[105];
int percentage[105];
void dfs(int node) {
    if (visited[node])return;
    visited[node] = true;
    for (int e = first[node]; e != -1; e = nxt[e]) {
        percentage[v[e]] += w[e];
        if (percentage[v[e]] > 50) {
            control[v[e]] = true;
            dfs(v[e]);
        }
    }
}
int main() {
    memset(first, -1, sizeof(first));
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> u[i] >> v[i] >> w[i];
        nxt[i] = first[u[i]];
        first[u[i]] = i;
        m = max(m, max(u[i], v[i]));
    }
    for (int i = 1; i <= m; i++) {
        memset(visited, false, sizeof(visited));
        memset(control, false, sizeof(control));
        memset(percentage, 0, sizeof(percentage));
        dfs(i);
        for (int j = 1; j <= m; j++) {
            if (i != j&&control[j])cout << i << " " << j << endl;
        }
    }
}

洛谷 寻找道路

题号:P2296

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
#include<iostream>
#include<cstring>
#include<queue>
#define MapLoop(e,node) for(int e=first[node];e!=-1;e=_next[e])
#define MapLoopRvs(e,node) for(int e=first_rvs[node];e!=-1;e=_next_rvs[e])
using namespace std;
int n,m,s,t;
int first[10005],u[200005],v[200005],_next[200005];//两个图,一个正图,一个反图
int first_rvs[10005],u_rvs[200005],v_rvs[200005],_next_rvs[200005];
int _distance[10005];
bool OK[10005],OK2[10005];
bool visited[10005];
bool inqueue[10005];
queue<int> q,q1;
void bfs(int node){//反图用来遍历与终点不联通的点
    q1.push(node);
    visited[node]=true;
    OK[node]=true;
    while(!q1.empty()){
        int cur=q1.front();
        q1.pop();
        OK[cur]=true;
        MapLoopRvs(e,cur){
            if(!visited[v_rvs[e]]){
                visited[v_rvs[e]]=true;
                q1.push(v_rvs[e]);
            }
        }
    }
    memcpy(OK2,OK,sizeof(OK));//将与终点不联通的点的邻接点全部删除
    for(int i=1;i<=n;i++){
        if(OK[i]==false){
            MapLoopRvs(e,i){
                OK2[v_rvs[e]]=false;
            }
        }
    }
    memcpy(OK,OK2,sizeof(OK));
}
void SPFA(){//SPFA求最短路
    int cnt=0;
    memset(_distance,0x7f,sizeof(_distance));
    q.push(s);
    _distance[s]=0;
    inqueue[s]=true;
    while(!q.empty()){
        int cur=q.front();
        q.pop();
        inqueue[cur]=false;
        MapLoop(e,cur){
            if(_distance[v[e]]>_distance[u[e]]+1&&OK[v[e]]){//注意只能要没有删去的点
                _distance[v[e]]=_distance[u[e]]+1;
                if(!inqueue[v[e]]){
                    inqueue[v[e]]=true;
                    q.push(v[e]);
                    cnt++;
                }
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    memset(first,-1,sizeof(first));
    memset(first_rvs,-1,sizeof(first_rvs));
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>u[i]>>v[i];
        v_rvs[i]=u[i];
        u_rvs[i]=v[i];
        if(u[i]==v[i]){
            i--;
            m--;
            continue;
        }
        _next[i]=first[u[i]];
        first[u[i]]=i;
        _next_rvs[i]=first_rvs[u_rvs[i]];//建反图
        first_rvs[u_rvs[i]]=i;
    }
    cin>>s>>t;
    bfs(t);
    SPFA();
    if(_distance[t]>1e9)cout<<"-1";
    else cout<<_distance[t];
}

洛谷 [SCOI2005] 繁忙的都市 题解

题目描述

城市C是一个非常繁忙的大都市,城市中的道路十分的拥挤,于是市长决定对其中的道路进行改造。城市C的道路是这样分布的:城市中有n个交叉路口,有些交叉路口之间有道路相连,两个交叉路口之间最多有一条道路相连接。这些道路是双向的,且把所有的交叉路口直接或间接的连接起来了。每条道路都有一个分值,分值越小表示这个道路越繁忙,越需要进行改造。但是市政府的资金有限,市长希望进行改造的道路越少越好,于是他提出下面的要求:

1.改造的那些道路能够把所有的交叉路口直接或间接的连通起来。

2.在满足要求1的情况下,改造的道路尽量少。

3.在满足要求1、2的情况下,改造的那些道路中分值最大的道路分值尽量小。

任务:作为市规划局的你,应当作出最佳的决策,选择那些道路应当被修建。

输入输出格式

输入格式:
第一行有两个整数n,m表示城市有n个交叉路口,m条道路。接下来m行是对每条道路的描述,u, v, c表示交叉路口u和v之间有道路相连,分值为c。(1≤n≤300,1≤c≤10000)

输出格式:
两个整数s, max,表示你选出了几条道路,分值最大的那条道路的分值是多少。

输入输出样例

输入样例#1:

4 5
1 2 3
1 4 5
2 4 7
2 3 6
3 4 8
输出样例#1:

3 6

写了两种方法:
一种邻接表,一种邻接矩阵,都是Prim算法.
继续阅读

洛谷 最短网络 Agri-Net 题解

题目背景

农民约翰被选为他们镇的镇长!他其中一个竞选承诺就是在镇上建立起互联网,并连接到所有的农场。当然,他需要你的帮助。

题目描述

约翰已经给他的农场安排了一条高速的网络线路,他想把这条线路共享给其他农场。为了用最小的消费,他想铺设最短的光纤去连接所有的农场。

你将得到一份各农场之间连接费用的列表,你必须找出能连接所有农场并所用光纤最短的方案。每两个农场间的距离不会超过100000

输入输出格式

输入格式:

第一行: 农场的个数,N(3<=N<=100)。

第二行..结尾: 后来的行包含了一个N*N的矩阵,表示每个农场之间的距离。理论上,他们是N行,每行由N个用空格分隔的数组成,实际上,他们限制在80个字符,因此,某些行会紧接着另一些行。当然,对角线将会是0,因为不会有线路从第i个农场到它本身。

输出格式:

只有一个输出,其中包含连接到每个农场的光纤的最小长度。

输入输出样例

输入样例#1:

4
0 4 9 21
4 0 8 17
9 8 0 16
21 17 16 0
输出样例#1:

28

说明

题目翻译来自NOCOW。

USACO Training Section 3.1
继续阅读

Vijos P1767YYB喋血 题解

背景
话说上次YYB写强化的时候没有写好,于是hwz怒了。
描述
Hwz把YYB放到了一个迷宫之中,这个迷宫由n个节点构成,两个节点之间可能存在多条无向边,YYB的起点为1号节点,终点为n号节点。有m条无向边,对于每一条无向边,存在一个喋血值(∈N*,且≤100),即走过这条边的花费。另外,还有k个节点上有治疗药,即若YYB走到这个节点上时(不妨称这个点为治愈点),他身上所累积的喋血值会归零。YYB希望以最小的喋血值走完迷宫。
格式
输入格式
第1行n,m,k分别表示有n个节点,m条无向边,以及k个治愈点。
第2行到m+1行 每一行有一个x,y,z表示x到y有一条喋血值为z的无向边
第n+2行 有k个整数,分别为治愈点的号数
PS:保证数据中没有负权回路。保证治愈点不重复。
输出格式
一行minblood 表示YYB走完迷宫的最小喋血值
当然,如果无法走出迷宫,输出Oh no!
样例1
样例输入1

1
2
3
4
5
3 3 1
1 2 100
2 3 1
1 3 3
2

样例输出1

1
1

提示
范围:
对于100%的数据
1≤n≤5000,1≤k≤n,1≤m≤25000
继续阅读

Vijos P1053Easy sssp 题解

描述
输入数据给出一个有N(2 <= N <= 1,000)个节点,M(M <= 100,000)条边的带权有向图.
要求你写一个程序, 判断这个有向图中是否存在负权回路. 如果从一个点沿着某条路径出发, 又回到了自己, 而且所经过的边上的权和小于0, 就说这条路是一个负权回路.
如果存在负权回路, 只输出一行-1;
如果不存在负权回路, 再求出一个点S(1 <= S <= N)到每个点的最短路的长度. 约定: S到S的距离为0, 如果S与这个点不连通, 则输出NoPath.
格式
输入格式
第一行: 点数N(2 <= N <= 1,000), 边数M(M <= 100,000), 源点S(1 <= S <= N);
以下M行, 每行三个整数a, b, c表示点a, b(1 <= a, b <= N)之间连有一条边, 权值为c(-1,000,000 <= c <= 1,000,000)
输出格式
如果存在负权环, 只输出一行-1, 否则按以下格式输出
共N行, 第i行描述S点到点i的最短路:
如果S与i不连通, 输出NoPath;
如果i = S, 输出0;
其他情况输出S到i的最短路的长度.
样例1
样例输入1

1
2
3
4
5
6
7
8
9
6 8 1
1 3 4
1 2 6
3 4 -7
6 4 2
2 4 5
3 6 3
4 5 1
3 5 4

样例输出1

1
2
3
4
5
6
0
6
4
-3
-2
7

限制
Test5 5秒
其余 1秒
提示
做这道题时, 你不必为超时担心, 不必为不会算法担心, 但是如此“简单”的题目, 你究竟能ac么?
我TM都要死了,在八十中同学的好心帮助下才做出。
继续阅读