分类目录归档:图论

洛谷 P4779 【模板】单源最短路径(标准版)

SPFA 40;Dijkstra AC.
这个Dijkstra是没问题的版本,有问题的参见:https://renjikai.com/luogu-p1339/

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
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#define ll long long
#define pii pair<int,int>
#define PINF 0x7fffffff
#define NINF 0x80000000
using namespace std;
int t, c, ts;
struct edge {
    long long v, w;
    edge(int vv, int ww) { v = vv; w = ww; }
    bool operator < (const edge& e2) const{
        return w > e2.w;
    }
};
vector<edge> edges[100005];
long long dis[100005];
bool inqueue[100005];
bool visited[100005];
void SPFA() {
    queue<int> q;
    dis[ts] = 0;
    inqueue[ts] = true;
    q.push(ts);
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        inqueue[node] = false;
        for (int i = 0; i < edges[node].size(); i++) {
            if (dis[edges[node][i].v] > dis[node] + edges[node][i].w) {
                dis[edges[node][i].v] = dis[node] + edges[node][i].w;
                if (!inqueue[edges[node][i].v])q.push(edges[node][i].v);
            }
        }
    }
}
void dijkstra() {
    priority_queue<edge> pq;
        dis[ts] = 0;
    pq.push(edge(ts,0));
    while (!pq.empty()) {
        edge e = pq.top();
        pq.pop();
        if (visited[e.v])continue;
        visited[e.v] = true;
        //dis[e.v] = e.w;
        for (int i = 0; i < edges[e.v].size(); i++) {
            if (!visited[edges[e.v][i].v] && dis[edges[e.v][i].v] > dis[e.v] + edges[e.v][i].w) {
                //有可能存在一种情况:虽然没有轮到点i成为离已处理完毕的点集最近的点,但点i的距离值已经由其它处理中或处理完毕的点多次更新,所以松弛的第二个条件必须加入
                dis[edges[e.v][i].v] = dis[e.v] + edges[e.v][i].w;
                pq.push(edge(edges[e.v][i].v, dis[edges[e.v][i].v]));
            }
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin >> t >> c >> ts;
    for (int i = 1; i <= c; i++) {
        int rs, re, ci;
        cin >> rs >> re >> ci;
        edges[rs].push_back(edge(re, ci));
    }
    memset(dis, 0x7f, sizeof(dis));
    //SPFA();
    dijkstra();
    for(int i=1;i<=t;i++)cout << dis[i]<<" ";
}

20190524更新,又写了一次Dijkstra ^v^

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<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<string>
#include<queue>
#include<cstring>
#include<iomanip>
using namespace std;
int n, m, s;
struct edge {
    int g, w;
    edge(int g, int w) :g(g), w(w) {}
    bool operator < (const edge& e1) const{
        return this->w > e1.w;
    }
};
vector<edge> edges[100005];
int dis[100005];
bool visited[100005];
void dijkstra() {
    memset(dis, 0x7f, sizeof(dis));
    priority_queue<edge> pq;
    pq.push(edge(s, 0));
    while (!pq.empty()) {
        edge node = pq.top();
        pq.pop();
        if (visited[node.g])continue;
        visited[node.g] = true;
        if (node.w >= dis[node.g])continue;
        dis[node.g] = node.w;
        for (int i = 0; i < edges[node.g].size(); i++) {
            edge & curE = edges[node.g][i];
            if(!visited[curE.g])pq.push(edge(curE.g, node.w + curE.w));
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> s;
    for (int i = 1; i <= m; i++) {
        int f, g, w;
        cin >> f >> g >> w;
        edges[f].push_back(edge(g, w));
    }
    dijkstra();
    for (int i = 1; i <= n; i++) {
        if (dis[i] == 0x7f7f7f7f)cout << "2147483647 ";
        else cout << dis[i] << " ";
    }
}

洛谷 P1339 [USACO09OCT]热浪Heat Wave

头一次用dijkstra写题也是想试验一下,priority_queue的小根堆用的不熟。。让人不知所以。。。
应该有个这样的小窍门。pq的默认是搞大根堆的,直接想非常不好想,写排序规则的地方只写<号,然后写成“假设你就要把大数排在前面,即顺着pq排序规则走的规则,然后把符号一反即可”。 两种方法代码里都有: 注意!该题中的Dijkstra算法错误,请勿继续使用!错误问题在堆判断dis时不能做到实时动态更新,而将dis插入到堆排序的结构体中可以使得堆中重复插入点相同,路径值不同的结构体值,这样点同路径值小的可以传到堆顶,大的在到顶时被忽略。
没问题的版本参见:https://renjikai.com/luogu-p4779/

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
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#define ll long long
#define pii pair<int,int>
#define PINF 0x7fffffff
#define NINF 0x80000000
using namespace std;
int t, c, ts, te;
struct edge {
    int v, w;
    edge(int vv, int ww) { v = vv; w = ww; }
};
vector<edge> edges[2505];
int dis[2505];
bool inqueue[2505];
//bool visited[2505];
/*
struct cmp {
    bool operator () (int i1, int i2) {
        return dis[i1] > dis[i2];
    }
};
*/

void SPFA() {
    queue<int> q;
    dis[ts] = 0;
    inqueue[ts] = true;
    q.push(ts);
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        inqueue[node] = false;
        for (int i = 0; i < edges[node].size(); i++) {
            if (dis[edges[node][i].v] > dis[node] + edges[node][i].w) {
                dis[edges[node][i].v] = dis[node] + edges[node][i].w;
                if (!inqueue[edges[node][i].v])q.push(edges[node][i].v);
            }
        }
    }
}
/*
void dijkstra() {
    priority_queue<int,vector<int>,cmp> pq;
    dis[ts] = 0;
    pq.push(ts);
    while (!pq.empty()) {
        int node = pq.top();
        pq.pop();
        if (visited[node])continue;
        visited[node] = true;
        for (int i = 0; i < edges[node].size(); i++) {
            if (!visited[edges[node][i].v] && dis[edges[node][i].v] > dis[node] + edges[node][i].w) {
                //有可能存在一种情况:虽然没有轮到点i成为离已处理完毕的点集最近的点,但点i的距离值已经由其它处理中或处理完毕的点多次更新,所以松弛的第二个条件必须加入,这也是为什么cmp必须要用实时的数据
                dis[edges[node][i].v] = dis[node] + edges[node][i].w;
                pq.push(edges[node][i].v);
            }
        }
    }
}
*/

int main() {
    ios::sync_with_stdio(false);
    cin >> t >> c >> ts >> te;
    for (int i = 1; i <= c; i++) {
        int rs, re, ci;
        cin >> rs >> re >> ci;
        edges[rs].push_back(edge(re, ci));
        edges[re].push_back(edge(rs, ci));
    }
    memset(dis, 0x7f, sizeof(dis));
    SPFA();
    //dijkstra();
    cout << dis[te];
}

洛谷 P1341 无序字母对

本题涉及欧拉回路/欧拉路径。
参考:https://blog.csdn.net/qq_34454069/article/details/77779300
http://www.cnblogs.com/zmin/p/6947266.html
https://www.cnblogs.com/shao0099876/p/7366852.html

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<algorithm>
#include<vector>
#define ll long long
#define pii pair<int,int>
#define PINF 0x7fffffff
#define NINF 0x80000000
using namespace std;
int n;
struct e {
    char t;
    int bool_v;
    e(char t1, int v1) { t = t1; bool_v = v1; }
    bool operator < (const e& e2) const {
        return t < e2.t;
    }
};
vector<e> edge[130];
vector<char> path;
int degree[130];
bool visited[3000];
void dfs(char node) {
    for (int i = 0; i < edge[node].size(); i++) {
        if (visited[edge[node][i].bool_v])continue;
        visited[edge[node][i].bool_v] = true;
        dfs(edge[node][i].t);
    }
    path.push_back(node);
}
int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        char c1, c2;
        cin >> c1 >> c2;
        degree[c1]++;
        degree[c2]++;
        edge[c1].push_back(e(c2, i));
        edge[c2].push_back(e(c1, i));
    }
    for (char i = 0; i <= 126; i++) {
        if (edge[i].size() > 1)sort(edge[i].begin(), edge[i].end());
    }
    int odd = 0;//奇
    char s = -1;
    for (char i = 127; i >= 0; i--) {
        if (degree[i] % 2 == 0 && degree[i] > 0) {
            if (odd == 0)s = i;
        }
        else if (degree[i] % 2 == 1) {
            odd++;
            s = i;
        }
    }
    if (!(odd == 0 || odd == 2)) {
        cout << "No Solution";
        return 0;
    }
    dfs(s);
    for (int i = path.size() - 1; i >= 0; i--) {
        cout << path[i];
    }
}

可能确实不大好理解这个代码,然后就做了一个简易的例子来说明这个问题。

洛谷 P2921 [USACO08DEC]在农场万圣节Trick or Treat on the Farm

今后需要改良一下拓扑排序,不要一遍一遍扫。只要抓到一个入度为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
#include<iostream>
#include<algorithm>
#define ll long long
#define pii pair<int,int>
#define PINF 0x7fffffff
#define NINF 0x80000000
using namespace std;
int n;
int nxt[100005];
bool visited[100005];
int allocated[100005];
int alloc_ptr = 0;
int allocate_dis[100005];
int chainDis[100005];
int inDegree[100005];
inline void removeInDegree(int node) {
    if (inDegree[node] != 0)return;
    inDegree[node]--;
    inDegree[nxt[node]]--;
    removeInDegree(nxt[node]);
}
inline int dfsRing(int alloc, int node) {
    if (visited[node])return 0;
    visited[node] = true;
    allocated[node] = alloc;
    return 1 + dfsRing(alloc, nxt[node]);
}
inline int dfsToRing(int node) {
    if (chainDis[node] != 0)return chainDis[node];
    if (allocated[node])return chainDis[node] = allocate_dis[allocated[node]];
    else return chainDis[node] = 1 + dfsToRing(nxt[node]);
}
int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> nxt[i];
        inDegree[nxt[i]]++;
    }
    for (int i = 1; i <= n; i++) {
        if (inDegree[i] == 0)removeInDegree(i);
    }
    for (int i = 1; i <= n; i++) {
        if (inDegree[i] <= 0 || allocated[i]) continue;
        alloc_ptr++;
        allocate_dis[alloc_ptr] = dfsRing(alloc_ptr, i);
    }
    for (int i = 1; i <= n; i++) {
        if (allocated[i])cout << allocate_dis[allocated[i]] << endl;
        else cout << dfsToRing(i) << endl;
    }
}

洛谷 P2661 信息传递

小小的激动一下,自己做出来的。。
然后有个警醒,如果不是顺其自然简化的条件判断表达式(例如!flag,是flag==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
#include<iostream>
#include<cstring>
#include<algorithm>
#define ll long long
#define pii pair<int,int>
#define PINF 0x7fffffff
#define NINF 0x80000000
using namespace std;
int n;
int To[200005];
int inDegree[200005];
int getRing(int node) {
    if (!inDegree[node])return 0;
    inDegree[node] = 0;
    return 1 + getRing(To[node]);
}
int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> To[i];
        inDegree[To[i]]++;
    }
    int flag = 0;
    do {
        flag = 0;
        for (int i = 1; i <= n; i++) {
            if (inDegree[i]==0) {
                inDegree[i]--;
                inDegree[To[i]]--;
                flag++;
            }
        }
    } while (flag!=0);
    int mmin = 0x7fffffff;
    for (int i = 1; i <= n; i++) {
        if (inDegree[i] > 0)mmin = min(mmin, getRing(i));
    }
    cout << mmin;
}

洛谷 车站分级

题号: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;
}

20180814更新:
题解:https://www.luogu.org/blog/24212/solution-p1983
主要是借鉴了一个开一个二维数组判断边是否加重的问题。
还有一个最重要的就是“由停车的站向不停车的站连边”问题,总是考虑不到。

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
#include<iostream>
#include<vector>
using namespace std;
int n,m;
bool visited[1002][1002];
int inDegree[1002],grades[1002];
vector<int> edges[1002];
vector<int> railStation;
vector<int> unStopStation;
vector<int> curGrade;
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        railStation.clear();
        unStopStation.clear();
        int num;
        cin>>num;
        for(int j=1;j<=num;j++){
            int t;
            cin>>t;
            railStation.push_back(t);
        }
        for(int j=0;j<railStation.size()-1;j++){
            for(int k=railStation[j]+1;k<railStation[j+1];k++){
                unStopStation.push_back(k);
            }
        }
        for(int j=0;j<railStation.size();j++){
            for(int k=0;k<unStopStation.size();k++){
                if(visited[railStation[j]][unStopStation[k]])continue;
                visited[railStation[j]][unStopStation[k]]=true;
                edges[railStation[j]].push_back(unStopStation[k]);
                inDegree[unStopStation[k]]++;
            }
        }
    }
    int maxV=0;
    do{
        curGrade.clear();
        for(int i=1;i<=n;i++){
            if(inDegree[i]==0){
                curGrade.push_back(i);
                inDegree[i]--;
            }
        }
        for(int i=0;i<curGrade.size();i++){
            grades[curGrade[i]]++;
            for(int j=0;j<edges[curGrade[i]].size();j++){
                grades[edges[curGrade[i]][j]]=max(grades[edges[curGrade[i]][j]],grades[curGrade[i]]);
                inDegree[edges[curGrade[i]][j]]--;
            }
            maxV=max(maxV,grades[curGrade[i]]);
        }
    }while(curGrade.size());
    cout<<maxV;
}

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;
        }
    }
}