[C] 2013腾讯马拉松初赛 ACM 湫湫系列故事——设计风景线 →→→→→进入此内容的聊天室

来自 , 2020-08-16, 写在 C, 查看 170 次.

/*
 
2013腾讯马拉松初赛第2场
 
1005 湫湫系列故事——设计风景线
________________________________________
Time Limit: 3 Seconds   Memory Limit: 65536K
________________________________________
 
随着杭州西湖的知名度的进一步提升，园林规划专家湫湫希望设计出一条新的经典观光线路，根据老板马小腾的指示，新的风景线最好能建成环形，如果没有条件建成环形，那就建的越长越好。
现在已经勘探确定了n个位置可以用来建设，在它们之间也勘探确定了m条可以设计的路线以及他们的长度。请问是否能够建成环形的风景线？如果不能，风景线最长能够达到多少？
其中，可以兴建的路线均是双向的，他们之间的长度均大于0。
 
Input
 
测试数据有多组，每组测试数据的第一行有两个数字n, m，其含义参见题目描述；
接下去m行，每行3个数字u v w，分别代表这条线路的起点，终点和长度。
 
[Technical Specification]
1. n<=100000  
2. m <= 1000000
3. 1<= u, v <= n 
4. w <= 1000
 
Output
 
对于每组测试数据，如果能够建成环形（并不需要连接上去全部的风景点），那么输出YES，否则输出最长的长度，每组数据输出一行。
 
Sample Input
 
3 3
1 2 1
2 3 1
3 1 1
 
Sample Output
 
YES
 
*/
 
/*
解题报告：
首先做这题的时候很纠结，不知道题目中说的环形是什么，是要所有的路都用上还是怎么样。经过一番思考后，觉得应该是判环。
我就直接想到了双联通分量了。至于最长路，就是如果不存在双联通分量的情况，必然是几棵树了。就是求一下树的直径。
经过一番YY之后，就开始写了。
 
先求双联通，然后再BFS，求树直径。交上去之后RE掉了，当时也不确定自己算法正确性，有想过要用加栈的方法。可是没去试。后来和别人讨论了，他让我加了，结果就这么过了。
我看到别人的代码这么短的。
我看了别人的做法原来他们是用并查集来判环的。学习了。
PS：以后递归溢出要加#pragma comment(linker, "/STACK:36777216")//开大点
栈这个试试。
*/
 
#include<string.h>
#include<map>
#include<algorithm>
#include<math.h>
#include<stdio.h>
#pragma comment(linker, "/STACK:36777216")//开大点栈
using namespace std;
const int MAX = 1100000 * 2;
 
const double EPS = 1.0e-8;
bool dblcmp(double x) {
    if(fabs(x) < EPS)return 0;
    return x < 0 ? -1 : 1;
}
 
const int MAXN = 110000;
const int MAXM = 1100000 * 2;
struct EDGE {
    int v, next, d;
} edge[MAXM];
int E;
int  com[MAXN], DN, CN, h[MAXN], d[MAXN], stk[MAXN], top;
int head[MAXN];
void  DFS(int  t, int f) {
    int  i, ed;
    stk[top++] = t;
    d[t] = DN--;
    h[t] = d[t];
    for(i = head[t]; i != -1; i = edge[i].next) {
        ed = edge[i].v;
        if(ed != f) {
            if(d[ed] == 0) {
                DFS(ed, t);
                if(h[ed] > h[t]) h[t] = h[ed];
            }
            if(com[ed] == 0 && h[t] < d[ed])
                h[t] = d[ed];
        }
    }
    if(h[t] == d[t]) {
        com[t] = ++CN;
        while(stk[top - 1] != t) {
            com[stk[top - 1]] = CN;
            top--;
        }
        top--;
    }
}
 
void SCC(int N) {
    int  i;
    CN = 0;
    DN = N;
    top = 0;
    memset(com, 0, sizeof(int) * (N + 2));
    memset(h, 0, sizeof(int) * (N + 2));
    memset(d, 0, sizeof(int) * (N + 2));
    for(i = 1; i <= N; i++) {
        if(com[i] == 0)
            DFS(i, -1);
    }
}
void add(int s, int t, int d) {
    edge[E].v = t;
    edge[E].d = d;
    edge[E].next = head[s];
    head[s] = E++;
}
typedef __int64 lld;
int vis[MAXN];
int q[MAXN];
int dis[MAXN];
map<lld, int>mp;
int BFS(int s, int CS, int &ans) {
    int rear = 0, front = -1;
    int i, v;
    dis[s] = 0;
    vis[s] = CS;
    q[0] = s;
    while(rear != front) {
        front++;
        s = q[front];
        for(i = head[s]; i != -1; i = edge[i].next) {
            v = edge[i].v;
            if(vis[v] == CS)continue;
            dis[v] = edge[i].d + dis[s];
            vis[v] = CS;
            rear++;
            q[rear] = v;
        }
    }
    int ind = s;
    int tmp = dis[s];
    for(i = 1; i <= rear; i++) {
        v = q[i];
        if(dis[v] > tmp) {
            tmp = dis[v];
            ind = v;
        }
    }
    if(tmp > ans)ans = tmp;
    return ind;
}
bool dig(char x) {
    return x >= '0' && x <= '9';
}
int getval() {
    int ret = 0, sign = 1;
    char c;
    while(!dig(c = getchar()) && c != '-');
    if(c == '-')sign = -1;
    else ret = c - '0';
    while(dig(c = getchar()))ret = ret * 10 + c - '0';
    return ret * sign;
}
int main() {
    int i, n, m, j;
    int k, CS = 1;
    while(scanf("%d%d", &n, &m) != EOF) {
        //mp.clear();
        memset(head, -1, sizeof(int) * (n + 5));
        E = 0;
        bool flag = false;
        while(m--) {
            //scanf("%d%d%d",&i,&j,&k);
            i = getval();
            j = getval();
            k = getval();
            if(i == j)continue; //
            //if(i>j)swap(i,j);
            //lld tmp=(lld)(i)*(lld)(1000000)+(lld)(j);
            //mp[tmp]++;
            //if(mp[tmp]>1)flag=true;
            add(i, j, k);
            add(j, i, k);
 
        }
        if(flag) {
            puts("YES");
            continue;
        }
        CS++;
        SCC(n);
        //printf("CN=%d\n",CN);
        if(CN != n) {
            puts("YES");
            continue;
        }
 
        memset(vis, -1, sizeof(int) * (n + 2));
        int ans = 0;
        int tmp, j;
        for(i = 1; i <= n; i++) {
            if(vis[i] == -1) {
                j = BFS(i, CS, ans);
                CS++;
 
                j = BFS(j, CS, ans);
                CS++;
            }
        }
 
        printf("%d\n", ans);
    }
    return 0;
}

回复 "2013腾讯马拉松初赛 ACM 湫湫系列故事——设计风景线"

这儿你可以回复上面这条便签

作者你的名字是？

标题给你的便签一个标题。

语言你的便签是以

你的便签在这儿输入便签内容

2013腾讯马拉松初赛第2场

1005 湫湫系列故事——设计风景线
________________________________________
Time Limit: 3 Seconds   Memory Limit: 65536K
________________________________________

随着杭州西湖的知名度的进一步提升，园林规划专家湫湫希望设计出一条新的经典观光线路，根据老板马小腾的指示，新的风景线最好能建成环形，如果没有条件建成环形，那就建的越长越好。
现在已经勘探确定了n个位置可以用来建设，在它们之间也勘探确定了m条可以设计的路线以及他们的长度。请问是否能够建成环形的风景线？如果不能，风景线最长能够达到多少？
其中，可以兴建的路线均是双向的，他们之间的长度均大于0。

Input

测试数据有多组，每组测试数据的第一行有两个数字n, m，其含义参见题目描述；
接下去m行，每行3个数字u v w，分别代表这条线路的起点，终点和长度。

[Technical Specification]
1. n<=100000  
2. m <= 1000000
3. 1<= u, v <= n 
4. w <= 1000

Output

对于每组测试数据，如果能够建成环形（并不需要连接上去全部的风景点），那么输出YES，否则输出最长的长度，每组数据输出一行。

Sample Input

3 3
1 2 1
2 3 1
3 1 1

Sample Output

YES

/*
解题报告：
首先做这题的时候很纠结，不知道题目中说的环形是什么，是要所有的路都用上还是怎么样。经过一番思考后，觉得应该是判环。
我就直接想到了双联通分量了。至于最长路，就是如果不存在双联通分量的情况，必然是几棵树了。就是求一下树的直径。
经过一番YY之后，就开始写了。

先求双联通，然后再BFS，求树直径。交上去之后RE掉了，当时也不确定自己算法正确性，有想过要用加栈的方法。可是没去试。后来和别人讨论了，他让我加了，结果就这么过了。
我看到别人的代码这么短的。
我看了别人的做法原来他们是用并查集来判环的。学习了。
PS：以后递归溢出要加#pragma comment(linker, "/STACK:36777216")//开大点
栈这个试试。
*/

#include<string.h>
#include<map>
#include<algorithm>
#include<math.h>
#include<stdio.h>
#pragma comment(linker, "/STACK:36777216")//开大点栈
using namespace std;
const int MAX = 1100000 * 2;

const double EPS = 1.0e-8;
bool dblcmp(double x) {
    if(fabs(x) < EPS)return 0;
    return x < 0 ? -1 : 1;
}

const int MAXN = 110000;
const int MAXM = 1100000 * 2;
struct EDGE {
    int v, next, d;
} edge[MAXM];
int E;
int  com[MAXN], DN, CN, h[MAXN], d[MAXN], stk[MAXN], top;
int head[MAXN];
void  DFS(int  t, int f) {
    int  i, ed;
    stk[top++] = t;
    d[t] = DN--;
    h[t] = d[t];
    for(i = head[t]; i != -1; i = edge[i].next) {
        ed = edge[i].v;
        if(ed != f) {
            if(d[ed] == 0) {
                DFS(ed, t);
                if(h[ed] > h[t]) h[t] = h[ed];
            }
            if(com[ed] == 0 && h[t] < d[ed])
                h[t] = d[ed];
        }
    }
    if(h[t] == d[t]) {
        com[t] = ++CN;
        while(stk[top - 1] != t) {
            com[stk[top - 1]] = CN;
            top--;
        }
        top--;
    }
}

void SCC(int N) {
    int  i;
    CN = 0;
    DN = N;
    top = 0;
    memset(com, 0, sizeof(int) * (N + 2));
    memset(h, 0, sizeof(int) * (N + 2));
    memset(d, 0, sizeof(int) * (N + 2));
    for(i = 1; i <= N; i++) {
        if(com[i] == 0)
            DFS(i, -1);
    }
}
void add(int s, int t, int d) {
    edge[E].v = t;
    edge[E].d = d;
    edge[E].next = head[s];
    head[s] = E++;
}
typedef __int64 lld;
int vis[MAXN];
int q[MAXN];
int dis[MAXN];
map<lld, int>mp;
int BFS(int s, int CS, int &ans) {
    int rear = 0, front = -1;
    int i, v;
    dis[s] = 0;
    vis[s] = CS;
    q[0] = s;
    while(rear != front) {
        front++;
        s = q[front];
        for(i = head[s]; i != -1; i = edge[i].next) {
            v = edge[i].v;
            if(vis[v] == CS)continue;
            dis[v] = edge[i].d + dis[s];
            vis[v] = CS;
            rear++;
            q[rear] = v;
        }
    }
    int ind = s;
    int tmp = dis[s];
    for(i = 1; i <= rear; i++) {
        v = q[i];
        if(dis[v] > tmp) {
            tmp = dis[v];
            ind = v;
        }
    }
    if(tmp > ans)ans = tmp;
    return ind;
}
bool dig(char x) {
    return x >= '0' && x <= '9';
}
int getval() {
    int ret = 0, sign = 1;
    char c;
    while(!dig(c = getchar()) && c != '-');
    if(c == '-')sign = -1;
    else ret = c - '0';
    while(dig(c = getchar()))ret = ret * 10 + c - '0';
    return ret * sign;
}
int main() {
    int i, n, m, j;
    int k, CS = 1;
    while(scanf("%d%d", &n, &m) != EOF) {
        //mp.clear();
        memset(head, -1, sizeof(int) * (n + 5));
        E = 0;
        bool flag = false;
        while(m--) {
            //scanf("%d%d%d",&i,&j,&k);
            i = getval();
            j = getval();
            k = getval();
            if(i == j)continue; //
            //if(i>j)swap(i,j);
            //lld tmp=(lld)(i)*(lld)(1000000)+(lld)(j);
            //mp[tmp]++;
            //if(mp[tmp]>1)flag=true;
            add(i, j, k);
            add(j, i, k);

}
        if(flag) {
            puts("YES");
            continue;
        }
        CS++;
        SCC(n);
        //printf("CN=%d\n",CN);
        if(CN != n) {
            puts("YES");
            continue;
        }

memset(vis, -1, sizeof(int) * (n + 2));
        int ans = 0;
        int tmp, j;
        for(i = 1; i <= n; i++) {
            if(vis[i] == -1) {
                j = BFS(i, CS, ans);
                CS++;

j = BFS(j, CS, ans);
                CS++;
            }
        }

printf("%d\n", ans);
    }
    return 0;
}

创建短链接创建一个较短的URL，连接到这个便签

私人私人便签不会显示在最近列表中

保存期限我们应该什么时候删除这张便签？

防滥用键入这些字符

Code666 (代码贴、代码片段)

[C] 2013腾讯马拉松初赛 ACM 湫湫系列故事——设计风景线 →→→→→进入此内容的聊天室

回复 "2013腾讯马拉松初赛 ACM 湫湫系列故事——设计风景线"