http://poj.org/problem?id=3114
?題目大意：
n個間諜 他們之間傳送信息需要一定的時間
一個聯通分量里面的間諜屬于一個國家，之間的信息傳遞不需要時間
然后問你從一個間諜傳一個信息到另一個間諜那需要最少時間 也可能傳不到
聯通縮點+最短路
縮點所得到的新圖 可能是因為有重邊或是太稠密 用鄰接表容易超時
基本步驟：
1，輸入去重邊
2，Tarjan縮點
3，重新調整縮點后間諜之間的信息傳遞時間
4，最短路
注意： 圖有可能不完全連通
代碼及其注釋：
#include<iostream>
#include<cstring>
#include<stack>
#include<cstdio>
#include<math.h>
#include<algorithm>
#include<queue>
using namespace std;
const int M=1000000002;
const int N=515;
struct node
{
struct tt *next;
}mem[N];
struct node1
{
struct tt *next;
}remem[N];
struct tt
{
struct tt *next;
int j;
};
bool in[N];
bool visited[N];
int deep;
stack<int>str;
int dfn[N];
int low[N];
int uppoint[N];
int time[N][N];
inline void build(int i,int j)
{
struct tt *t=new tt;
t->j=j;
t->next=mem[i].next;
mem[i].next=t;
}
inline void Clearlist(int n)
{
for(int i=1;i<=n;++i)
{
mem[i].next=NULL;
}
}
void Tarjan(int x)//縮點
{
++deep;
dfn[x]=low[x]=deep;
visited[x]=true;
in[x]=true;
str.push(x);
struct tt *t=mem[x].next;
while(t!=NULL)
{
if(visited[t->j]==false)
{
Tarjan(t->j);
low[x]=min(low[x],low[t->j]);
}else if(in[t->j]==true)
{
low[x]=min(low[x],dfn[t->j]);
}
t=t->next;
}
if(low[x]==dfn[x])
{
while(str.top()!=x)
{
uppoint[str.top()]=x;
in[str.top()]=false;
str.pop();
}
uppoint[str.top()]=x;
in[str.top()]=false;
str.pop();
}
}
void dfs(int x)//調整縮點后有用點之間的信息傳遞時間
{
visited[x]=true;
struct tt *t=mem[x].next;
while(t!=NULL)
{
if(uppoint[x]!=uppoint[t->j])
{
time[uppoint[x]][uppoint[t->j]]=min(time[uppoint[x]][uppoint[t->j]],time[x][t->j]);
}
if(!visited[t->j])
{
dfs(t->j);
}
t=t->next;
}
}
int mintime(int st,int nd,int n)//求最短路
{
if(st==nd)
return 0;
int dist[N];
memset(visited,false,sizeof(visited));
for(int i=1;i<=n;++i)
if(time[st][i]==-1)
dist[i]=M;
else
dist[i]=time[st][i];
visited[st]=true;
for(int w=1;w<n;++w)
{
int MIN=M;int k=-1;
for(int i=1;i<=n;++i)
{
if(!visited[i]&&dist[i]<MIN)
{
MIN=dist[i];k=i;
}
}
if(k==-1)
break;
if(k==nd)
break;
visited[k]=true;
for(int i=1;i<=n;++i)
{
if(dist[i]>dist[k]+time[k][i])
dist[i]=dist[k]+time[k][i];
}
}
return dist[nd];
}
int main()
{
int n,m,q;
while(scanf("%d %d",&n,&m)!=EOF)
{
if(n==0&&m==0)
break;
for(int i=1;i<=n;++i)//初始化
{
for(int j=i;j<=n;++j)
time[i][j]=time[j][i]=M;
}
while(m--)
{
int i,j,k;
scanf("%d %d %d",&i,&j,&k);
if(time[i][j]>k)//去重邊
time[i][j]=k;
}
for(int i=1;i<=n;++i)
{
for(int j=1;j<=n;++j)
{
if(time[i][j]!=M)//建原圖
build(i,j);
}
}
memset(dfn,-1,sizeof(dfn));
memset(visited,false,sizeof(visited));
memset(in,false,sizeof(in));
memset(uppoint,-1,sizeof(uppoint));
while(!str.empty())
str.pop();
deep=0;
for(int i=1;i<=n;++i)
{
if(dfn[i]==-1)//因為圖有可能不完全聯通
Tarjan(i);
}
memset(visited,false,sizeof(visited));
for(int i=1;i<=n;++i)
{
if(!visited[i])//因為圖有可能不完全聯通
{
dfs(i);
}
}
for(int i=1;i<=n;++i)
{
for(int j=1;j<=n;++j)
{
if(i!=uppoint[i]||j!=uppoint[j])//處理一下非聯通縮點之間的信息傳遞時間
time[i][j]=M;
}
}
scanf("%d",&q);
while(q--)
{
int i,j,k;
scanf("%d %d",&i,&j);
i=uppoint[i];j=uppoint[j];
k=mintime(i,j,n);
if(k==M)
printf("Nao e possivel entregar a carta\n");
else
printf("%d\n",k);
}
printf("\n");
Clearlist(n);
}
return 0;
}
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
