3.化学竞赛的大奖
(prize.pas/c/cpp)
【问题描述】
XYX 在 CChO(全国化学奥林匹克竞赛)比赛中获得了大奖,奖品是一张特殊的机票。
使用这张机票,可以在任意一个国家内的任意城市之间的免费飞行,只有跨国飞行时才
会有额外的费用。XYX 获得了一张地图,地图上有城市之间的飞机航班和费用。已知从
每个城市出发能到达所有城市,两个城市之间可能有不止一个航班。一个国家内的每两
个城市之间一定有不止一条飞行路线, 而两个国家的城市之间只 有一条飞行路线。 XYX
想知道, 从每个城市出发到额外费用最大的城市, 以便估算出出行的费用, 请你帮助他。
当然,你不能通过乘坐多次一个航班增加额外费用, 也就是必须沿费用最少的路线飞
行。
【输入】
第一行,两个整数 N,M,表示地图上有 N 个城市,M 条航线。
接下来 M 行,每行三个整数 a,b,c,表示城市 a,b 之间有一条费用为 c 的航线。
【 输出】
共 N 行,第 i 行为从城市 i 出发到达每个城市额外费用的最大值。
随便写了写
全封装了
不太好写
但是过编译了……
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<set>
#define M 20005
#define N 2005
using namespace std;
int x,y,z;
struct GG{
vector<int>G[N];
set<pair<int,int> >cutedge;
int n,m,low[N],dfn[N];
bool is_cut[N];
int father[N];
int vis[N];
int ans[N];
int dis[N];
int fa[N];
int tim;
struct Edge1{
int to,next,v;
}edge1[M],edge[M];
int head[N],head1[N],tot;
void add1(int a,int b,int c){
edge1[++tot].to=b;
edge1[tot].next=head[a];
edge1[tot].v=c;
head[a]=tot;
edge1[++tot].to=a;
edge1[tot].next=head[b];
edge1[tot].v=c;
head[b]=tot;
}
void add2(int a,int b,int c){
edge[++tot].to=b;
edge[tot].next=head1[a];
edge[tot].v=c;
head1[a]=tot;
edge[++tot].to=a;
edge[tot].next=head1[b];
edge[tot].v=c;
head[b]=tot;
}
GG(){
scanf("%d%d",&n,&m);
push_up_all_the_edges(m);
tim=tot=0;
memset(dfn,-1,sizeof(dfn));
memset(father,0,sizeof(father));
memset(low,-1,sizeof(low));
memset(is_cut,false,sizeof(is_cut));
for(int i=1;i<N;++i)fa[i]=i;
count();
}
void push_up_all_the_edges(int sum){
for(int i=1;i<=m;++i){
scanf("%d%d%d",&x,&y,&z);
push(x,y);add1(x,y,z);
}
}
void shrinkpoint(){
tot=0;
for(int i=1;i<=n;++i)
if(!vis[i])
DFS(i);
for(int i=i;i<=n;++i)
for(int j=head[i];j;j=edge1[j].next)
if(cutedge.count(make_pair(i,edge1[j].to)))
add2(fa[i],fa[edge1[j].to],edge1[j].v);
}
void diameter(){
memset(dis,0x3f,sizeof(dis));dis[1]=0;
int a=dfs(1,1);
memset(dis,0x3f,sizeof(dis));dis[a]=0;
for(int i=1;i<=n;++i)
ans[i]+=dis[i];
int b=dfs(a,a);
for(int i=1;i<=n;++i)
ans[i]+=dis[i];
}
int dfs(int s,int k){
for(int i=head1[s];i;i=edge[i].next){
dis[edge[i].to]=dis[s]+edge[i].v;
if(dis[edge[i].to]>dis[k])k=edge[i].to;
dfs(edge[i].to,k);
}
}
void Dp(){
diameter();
for(int i=1;i<=n;++i)
printf("%d
",ans[i]);
}
void work(){
shrinkpoint();
Dp();
}
void push(int a,int b){
G[a].push_back(b);
G[b].push_back(a);
}
void Tarjan(int i,int Father){
father[i]=Father;
dfn[i]=low[i]=tim++;
for(int j=0;j<G[i].size();++j){
int k=G[i][j];
if(dfn[k]==-1){
Tarjan(k,i);
low[i]=min(low[i],low[k]);
}
else if(Father!=k)
low[i]=min(low[i],dfn[k]);
}
}
void count(){
int rootson=0;
Tarjan(1,0);
for(int i=2;i<=n;++i){
int v=father[i];
if(v==1)rootson++;
else{
if(low[i]>=dfn[v])is_cut[v]=true;
if(low[i]>=dfn[v])is_cut[v]=true;
}
}
if(rootson>1)is_cut[1]=true;
for(int i=1;i<=n;++i)
if(is_cut[i])
printf("%d
",i);
for(int i=1;i<=n;++i){
int v=father[i];
if(v>0&&low[i]>dfn[v])
cutedge.insert(make_pair(v,i));
}
}
int find(int s){
if(fa[s]!=s)
fa[s]=find(fa[s]);
return fa[s];
}
void DFS(int i){
for(int j=0;j<G[i].size();++j){
if(!cutedge.count(make_pair(i,G[i][j]))){
if(find(i)!=find(G[i][j]))fa[i]=G[i][j];
DFS(G[i][j]);
};
}
}
};
int n1,n2,m1,m2;
int main(){
GG now=GG();
now.work();
return 0;
}