会python真的可以为所欲为0(回)
398天前
这里还有人吗1(回)
583天前这里还有人吗0(回)
583天前
每天面对着电脑屏幕，敲打键盘。我所面对的并不只是代码，而是一种生活方式。0(回)
808天前到处都是羊，不想上班0(回)
888天前
鸽子
0(回)
892天前/* |
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; |
} |
