本文主要是介绍poj-3114-Countries in War-tarjan缩点建图+dij求最短路，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
tarjan缩点建图，用了一上午的时间写好了模版。
但是在求最短路的时候不小心使用了floyd，乃至超时。
这不科学。。按照正常的时间复杂度，应该超时不了的。
下午比赛，晚上把之修改为dij，最后通过了~~
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<stack>
#include<vector>
#include<iostream>
#define tar_maxn 1100000
#define INF 99999999
using namespace std;
struct Graph_tar
{struct g_edge{int l,r,v,next;}node_tar[tar_maxn];//初始边struct g_ans{int l,r,v,next;}node_ans[tar_maxn];//建图之后的边int belong[tar_maxn];//老图中的点属于新图中的哪个点int head_tar[tar_maxn];//老图中的边的归属int head_ans[tar_maxn];//新图中的边的归属int vis_tar[tar_maxn];//tarjan判断此边是否存在int dfn[tar_maxn],low[tar_maxn],instack[tar_maxn];int edge_ans;int edge_num,times;int piece;//得到新图的点数int mps[1100][1100];//新图任意两点间的距离stack<int>qq;void init(){//初始化，得到的图从1开始for(int i=0;i<tar_maxn;i++){head_ans[i]=head_tar[i]=-1;instack[i]=vis_tar[i]=dfn[i]=low[i]=belong[i]=0;}for(int i=0;i<1001;i++)for(int j=0;j<1001;j++){mps[i][j]=INF;}edge_num=0,times=1,edge_ans=0;while(!qq.empty())qq.pop();piece=1;}void in_add(int l,int r,int v){//加入初始边node_tar[edge_num].l=l;node_tar[edge_num].r=r;node_tar[edge_num].v=v;node_tar[edge_num].next=head_tar[l];head_tar[l]=edge_num++;}void ans_add(int l,int r,int v){//加入建图边node_ans[edge_ans].l=l;node_ans[edge_ans].r=r;node_ans[edge_ans].v=v;node_ans[edge_ans].next=head_ans[l];head_ans[l]=edge_ans++;}void tarjan(int x){//tarjan算法进行缩点，求的边双联通dfn[x]=low[x]=times++;instack[x]=1;qq.push(x);for(int i=head_tar[x];i!=-1;i=node_tar[i].next){int y=node_tar[i].r;if(vis_tar[i])continue;vis_tar[i]=1;if(!dfn[y]){tarjan(y);low[x]=min(low[x],low[y]);}else if(instack[y]){low[x]=min(low[x],dfn[y]);}}if(low[x]==dfn[x]){int y=-1;while(x!=y){y=qq.top();qq.pop();instack[y]=0;belong[y]=piece;}piece++;}}void get_new_bl(int st,int ed,int n){//得到新图，图中的所有边都存在，两个点之间或许存在多条边for(int x=st;x<=ed;x++){for(int i=head_tar[x];i!=-1;i=node_tar[i].next){int y=node_tar[i].r;if(belong[x]!=belong[y])ans_add(belong[x],belong[y],node_tar[i].v);}}}void get_new_max(int st,int ed,int n){//得到新图，任意两点之间最多存在一条边，如果有多条，取最大的一条for(int x=st;x<=ed;x++){for(int i=head_tar[x];i!=-1;i=node_tar[i].next){int y=node_tar[i].r;if(mps[belong[x]][belong[y]]==INF)mps[belong[x]][belong[y]]=node_tar[i].v;else mps[belong[x]][belong[y]]=max(mps[belong[x]][belong[y]],node_tar[i].v);}}for(int i=1;i<piece;i++){for(int j=1;j<piece;j++){if(i==j)continue;if(mps[i][j]!=INF)ans_add(i,j,mps[i][j]);}}}void get_new_min(int st,int ed,int n){//得到新图，任意两点之间最多存在一条边，如果有多条，取最小的一条for(int x=st;x<=ed;x++){for(int i=head_tar[x];i!=-1;i=node_tar[i].next){int y=node_tar[i].r;if(mps[belong[x]][belong[y]]==INF)mps[belong[x]][belong[y]]=node_tar[i].v;else{mps[belong[x]][belong[y]]=min(mps[belong[x]][belong[y]],node_tar[i].v);};}}for(int i=1;i<piece;i++){for(int j=1;j<piece;j++){if(i==j)continue;if(mps[i][j]!=INF)ans_add(i,j,mps[i][j]);}}}void start(int st,int ed,int n,int leap){//开始函数，传递开始节点，终止节点，节点数，得到新图的状态for(int i=st;i<=ed;i++)if(!dfn[i])tarjan(i);if(leap==0)get_new_bl(st,ed,n);if(leap==1)get_new_max(st,ed,n);if(leap==2)get_new_min(st,ed,n);}}G;
int dp[1001][1001];
void dos()
{for(int k=1;k<G.piece;k++){for(int i=1;i<G.piece;i++){for(int j=1;j<G.piece;j++){if(i==j){G.mps[i][j]=0;continue;}if(G.mps[i][k]+G.mps[k][j]<G.mps[i][j])G.mps[i][j]=G.mps[i][k]+G.mps[k][j];}}}
}
void dij(int x,int y){if(x==y){cout<<"0"<<endl;return;}int nums=G.piece;int vis[1001];int dis[1001];for(int i=0;i<nums;i++){vis[i]=0;dis[i]=INF;}dis[x]=0;while(1){int minn=INF;int u;for(int i=1;i<nums;i++){if((!vis[i])&&dis[i]<minn){minn=dis[i];u=i;}}if(minn==INF)break;for(int i=G.head_ans[u];i!=-1;i=G.node_ans[i].next){int j=G.node_ans[i].r;int val=G.node_ans[i].v;if((!vis[j])&&dis[j]>dis[u]+val)dis[j]=dis[u]+val;}vis[u]=1;}if(dis[y]!=INF){printf("%d\n",dis[y]);}else printf("Nao e possivel entregar a carta\n");
}
int main()
{int n,k,m;int a,b,c;while(scanf("%d%d",&n,&k)&&(n)){memset(dp,-1,sizeof(dp));G.init();while(k--){scanf("%d%d%d",&a,&b,&c);G.in_add(a,b,c);}G.start(1,n,n,2);// dos();cin>>m;while(m--){scanf("%d%d",&a,&b);a=G.belong[a];b=G.belong[b];// if(G.mps[a][b]!=INF)cout<<G.mps[a][b]<<endl;// else cout<<"Nao e possivel entregar a carta"<<endl;dij(a,b);}cout<<endl;}return 0;
}
这篇关于poj-3114-Countries in War-tarjan缩点建图+dij求最短路的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
