【NOIP2012模拟11.5】小A 的作业

Description 小A 的老师给小A 布置了这样一份作业：某个城市x 是“重要”的，当且仅当存在两个点a，b(a<>x,b<>x)，当x 不能通过时，a->b 的最短路径的值改变了，现在告诉你N 个城市和M 条连接城市之间的路径，求出哪些点是重要的。小A 忙着去找小N 所以没空做业。请帮助小A 算出哪些城市是重要的。如果不存在就输出”No important cities.”给出的是一个无向图。 Input 第一行两个整数N, M，N 表示城市数，M 表示城市间的道路数。 以下N 行，每行三个整数a,b,c。表示城市a 到城市b 之间存在一条长度为c 的道路。 两个城市间可能存在多条道路。 Output 一行，按升序输出哪些城市是重要的，2 个数中间用空格分开 Sample Input 4 4 1 2 1 2 3 1 4 1 2 4 3 2 Sample Output 2 Data Constraint Hint 60%数据中N<=100 100%数据中N<=200,M<=N*N,0<=c<=10000

The Solution

其实这道题的本质是问你从a点到b点的最短路有没有多条路，这样就可以直接Floyd或者是dijkstra+堆优化。dis[j]>dis[i]+a[i,j] 则记录下j的必经点中为i，若dis[i]+a[i,j]=dis[j]，则说明有多个路径到j,再记录一下即可。

CODE

#include <cstdio> #include <iostream> #include <cmath> #include <algorithm> #include <cstring> #define fo(i,a,b) for (int i=a;i<=b;i++) #define fd(i,a,b) for (int i=a;i>=b;i--) #define N 205 #define INF 2147483647 using namespace std; int f[N][N],a[N][N]; bool bz[N]; int main() { freopen("data.in","r",stdin); int n,m; scanf("%d%d",&n,&m); fo(i,1,n) fo(j,1,n) f[i][j] = INF; fo(i,1,m) { int x,y,z; scanf("%d%d%d",&x,&y,&z); if (x==y) continue; if (f[x][y]>z) f[x][y] = z,f[y][x] = z; } fo(k,1,n) fo(i,1,n) if (f[k][i] != INF ) { fo(j,1,n) if (i != j && f[k][j] != INF) { if (f[k][i] + f[k][j] < f[i][j]) { f[j][i] = f[i][j] = f[k][i] + f[k][j]; a[i][j] = a[j][i] = k; } else if (f[k][i] + f[k][j] == f[i][j]) a[i][j] = 0; } } fo(i,1,n) fo(j,1,n) if (a[i][j] != 0 && a[i][j] != i && a[i][j] != j) bz[a[i][j]] = true; int Flag = false; fo(i,1,n) if (bz[i]) { printf("%d ",i); Flag = true; } if (!Flag) printf("No important cities."); //return 0; }

附上无聊从Andy博客上看到的**DIJ+堆优化**code

var a,v,g:array[1..500,0..500] of longint;p:boolean; i,n,m,x,y,z,tot,j:longint; dis:array[1..500] of longint; bz,w:array[1..500] of boolean; h:array[0..10000,1..2] of longint; procedure swap(x,y:longint); begin h[0]:=h[x];h[x]:=h[y];h[y]:=h[0];end; procedure delete; var i,j:longint; begin h[1]:=h[tot];dec(tot); i:=1;j:=2; while j<=tot do begin if (j<tot)and(h[j,2]>h[j+1,2]) then inc(j); if h[j,2]<h[i,2] then begin swap(i,j); i:=j;j:=j*2; end else break; end; end; procedure insert(x,y:longint); var i,j:longint; begin inc(tot);h[tot,1]:=x;h[tot,2]:=y; i:=tot;j:=tot div 2; while j>0 do begin if h[i,2]<h[j,2] then begin swap(i,j); i:=j;j:=j div 2; end else break; end; end; procedure dijkstra(x:longint); var i,now:longint; begin fillchar(bz,sizeof(bz),false); fillchar(dis,sizeof(dis),$7f); tot:=0;insert(x,0);dis[x]:=0; while true do begin while (tot>0)and(bz[h[1,1]]) do delete; if tot=0 then break; now:=h[1,1]; bz[now]:=true; for i:=1 to a[now,0] do if dis[a[now,i]]>dis[now]+v[now,a[now,i]] then begin dis[a[now,i]]:=dis[now]+v[now,a[now,i]]; insert(a[now,i],dis[a[now,i]]);g[x,a[now,i]]:=now;end else if dis[a[now,i]]=dis[now]+v[now,a[now,i]] then g[x,a[now,i]]:=0; end; end; begin assign(input,'city.in');reset(input); assign(output,'city.out');rewrite(output); readln(n,m); for i:=1 to m do begin read(x,y,z); if x=y then continue; if (v[x,y]=0) then begin inc(a[x,0]);a[x,a[x,0]]:=y; inc(a[y,0]);a[y,a[y,0]]:=x; v[x,y]:=z;v[y,x]:=z; end else if (v[x,y]>z) then begin v[x,y]:=z;v[y,x]:=z; end; end; for i:=1 to n do begin dijkstra(i); for j:=1 to n do if g[i,j]<>0 then if (g[i,j]<>i)and(g[i,j]<>j) then w[g[i,j]]:=true; end; for i:=1 to n do if w[i] then begin write(i,' ');p:=true;end; if not p then writeln('No important cities.'); close(input);close(output); end.

SPFA+lll+slf;

fillchar(dis,sizeof(dis),$7f); l:=0;t[1]:=n+1;t[2]:=n+1+n+2;r:=2;dis[n+1]:=0;dis[n+1+n+2]:=0;cont:=2;su:=0; while l<>r do begin l:=l mod mo+1; while dis[t[l]]>su div cont do begin r:=r mod mo+1;t[r]:=t[l];l:=l mod mo+1; end; no:=t[l]; p:=last[no]; dec(cont);dec(su,dis[t[l]]); while p<>0 do begin if (dis[no]+v[p]<dis[bi[p]])or(dis[bi[p]]=dis[0]) then begin dis[bi[p]]:=dis[no]+v[p]; if not bz[bi[p]] then begin bz[bi[p]]:=true;inc(cont);su:=su+dis[bi[p]]; if dis[bi[p]]<dis[t[l mod mo+1]] then begin t[l]:=bi[p];l:=(l+mo-2)mod mo+1; end else begin r:=r mod mo+1;t[r]:=bi[p]; end; end; end; p:=next[p]; end; bz[no]:=false; end;