http://acm.hdu.edu.cn/showproblem.php?pid=2433

?

題意：

求刪除任意一條邊后，任意兩點對的最短路之和

?

以每個點為根節點求一個最短路樹，

只需要記錄哪些邊在最短路樹上，記錄整棵樹的dis和

如果刪除的邊不在最短路樹上，累加記錄的dis和

否則，重新bfs求dis和

因為最短路樹上有n-1條邊，n棵樹，所以只有（n-1）*n條邊需要重新bfs

時間復雜度為n*n*m

?

求橋是 對面的low>自己的dfn，我求了一年假的橋

my god ！ ?(????)

?

#include<queue> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm>using namespace std;#define N 101 #define M 3001int n,m;int tot; int front[N],nxt[M<<1],to[M<<1];bool use[N][M],ok[M]; int sum[N],dis[N]; queue<int>q;int dfn[N],low[N]; bool bridge[M];void read(int &x) {x=0; char c=getchar();while(!isdigit(c)) c=getchar();while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); } }void add(int u,int v) {to[++tot]=v; nxt[tot]=front[u]; front[u]=tot;to[++tot]=u; nxt[tot]=front[v]; front[v]=tot; }void tarjan(int u,int pre) {dfn[u]=low[u]=++tot;for(int i=front[u];i;i=nxt[i]){if(i==(pre^1)) continue;if(!dfn[to[i]]) {tarjan(to[i],i);low[u]=min(low[u],low[to[i]]);if(low[to[i]]>dfn[u]) bridge[i>>1]=true;}else low[u]=min(low[u],dfn[to[i]]);} }void bfs(int s) {memset(dis,0,sizeof(dis));sum[s]=0;q.push(s);int now;while(!q.empty()){now=q.front();q.pop();for(int i=front[now];i;i=nxt[i])if(to[i]!=s && !dis[to[i]]){use[s][i>>1]=true;dis[to[i]]=dis[now]+1;sum[s]+=dis[to[i]];q.push(to[i]);}} }int bfs2(int s) {int ans=0;memset(dis,0,sizeof(dis));q.push(s);int now;while(!q.empty()){now=q.front();q.pop();for(int i=front[now];i;i=nxt[i])if(ok[i>>1] && to[i]!=s && !dis[to[i]]){dis[to[i]]=dis[now]+1;ans+=dis[to[i]];q.push(to[i]);}}return ans; }void solve() {int ans; memset(ok,true,sizeof(ok));for(int i=1;i<=m;++i){if(bridge[i]) {puts("INF");continue;}ans=0; for(int j=1;j<=n;++j)if(!use[j][i]) ans+=sum[j];else{ok[i]=false;ans+=bfs2(j);ok[i]=true;}printf("%d\n",ans);} }void clear() {tot=1;memset(front,0,sizeof(front));memset(dfn,0,sizeof(dfn));memset(bridge,false,sizeof(bridge));memset(use,false,sizeof(use)); }int main() {int u,v;while(scanf("%d",&n)!=EOF){clear();read(m);for(int i=1;i<=m;++i){read(u); read(v);add(u,v);}for(int i=1;i<=n;++i) bfs(i);tot=0;tarjan(1,0);bool tag=false;for(int i=1;i<=n;++i)if(!dfn[i]){tag=true;break;} if(!tag) solve();else for(int i=1;i<=m;++i) puts("INF");} }

Travel

Time Limit: 10000/2000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3388????Accepted Submission(s): 1160

Problem Description One day, Tom traveled to a country named BGM. BGM is a small country, but there are N (N <= 100) towns in it. Each town products one kind of food, the food will be transported to all the towns. In addition, the trucks will always take the shortest way. There are M (M <= 3000) two-way roads connecting the towns, and the length of the road is 1.
??????Let SUM be the total distance of the shortest paths between all pairs of the towns. Please write a program to calculate the new SUM after one of the M roads is destroyed.

?

Input The input contains several test cases.
??????The first line contains two positive integers N, M. The following M lines each contains two integers u, v, meaning there is a two-way road between town u and v. The roads are numbered from 1 to M according to the order of the input.
??????The input will be terminated by EOF.

?

Output Output M lines, the i-th line is the new SUM after the i-th road is destroyed. If the towns are not connected after the i-th road is destroyed, please output “INF” in the i-th line.

?

Sample Input 5 4 5 1 1 3 3 2 5 4 2 2 1 2 1 2

?

Sample Output INF INF INF INF 2 2

轉載于:https://www.cnblogs.com/TheRoadToTheGold/p/8436823.html

總結

以上是生活随笔為你收集整理的hdu 2433 Travel的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。