C - Important Roads
Time Limit: 20 Sec
Memory Limit: 256 MB
题目连接
http://acm.hust.edu.cn/vjudge/contest/view.action?cid=88926#problem/C
Description
The city where Georgie lives has n junctions some of which are connected by bidirectional roads. Every day Georgie drives from his home to work and back. But the roads in the city where Georgie lives are very bad, so they are very often closed for repair. Georgie noticed that when some roads are closed he still can get from home to work in the same time as if all roads were available. But there are such roads that if they are closed for repair the time Georgie needs to get from home to work increases, and sometimes Georgie even cannot get to work by a car any more. Georgie calls such roads important. Help Georgie to find all important roads in the city.
Input
Output
Output l — the number of important roads — at the first line of the output file. The second line must contain l numbers, the numbers of important roads. Roads are numbered from 1 to m as they are given in the input file.
Sample Input
6 7
1 2 1
2 3 1
2 5 3
1 3 2
3 5 1
2 4 1
5 6 2
Sample Output
2
5 7
HINT
题意
给你一个无向图，问你里面有多少个important道路
重要的道路就是指这条路去掉之后，整个图的最短路长度会发生变化
题解：
跑tarjan之后，如果这个边是桥的话，就输出就好了
和codeforces #314的E题几乎一模一样
代码：
#include <cstdio> #include <algorithm> #include <vector> #include <cstring> #include <queue> using namespace std; const int maxn = 200010; #define INF (1LL<<61) typedef long long ll; struct Dijkstra { struct node { ll d; int u; bool operator < (const node& b) const { return d > b.d; } node() {} node(ll _d, int _u): d(_d), u(_u) {} }; struct Edge { int from, to, id; ll dist; Edge() {} Edge(int u, int v, ll w) : from(u), to(v), dist(w){} }; int n, m; vector<Edge> edges; vector<int> G[maxn]; bool done[maxn]; ll d[maxn]; int p[maxn]; void init(int n) { this->n = n; for (int i = 0; i <= n; i++) G[i].clear(); edges.clear(); } void addEdge(int from, int to, ll dist) { edges.push_back(Edge(from, to, dist)); m = edges.size(); G[from].push_back(m-1); } void dijkstra(int s) { priority_queue<node> Q; for (int i = 0; i <= n; i++) d[i] = INF; d[s] = 0; memset(done, 0, sizeof(done)); Q.push(node(0, s)); while (!Q.empty()) { node x = Q.top(); Q.pop(); int u = x.u; if (done[u]) continue; done[u] = true; for (int i = 0; i < G[u].size(); i++) { Edge& e = edges[G[u][i]]; if (d[e.to] > d[u] + e.dist) { d[e.to] = d[u] + e.dist; p[e.to] = G[u][i]; Q.push(node(d[e.to], e.to)); } } } } } S, T; int dfn[maxn]; // 时间戳 int dfs_clock; // dfs时间变量 int low[maxn]; // u及u的后代在DFS树上能够到达的最早的祖先 struct Edge { int u, v, w, id; Edge(int a=0, int b=0, int w=0, int c=0) : u(a), v(b), w(w), id(c) {} } e[2*maxn]; vector<Edge> G[maxn]; bool isbridge[2*maxn]; int dfs(int u, int la) { int lowu = dfn[u] = ++dfs_clock; // dfs_clock在调用dfs前要初始化为0 int child = 0; // 子节点个数 for (int i = 0; i < G[u].size(); i++) { int v = G[u][i].v; if (!dfn[v]) { // 未访问过，树边 int lowv = dfs(v, G[u][i].id); lowu = min(lowu, lowv); if (lowv > dfn[u]) { // 判断桥 isbridge[G[u][i].id] = 1; } } else if (dfn[v] < dfn[u] && G[u][i].id != la) { // 反向边 lowu = min(lowu, dfn[v]); } } low[u] = lowu; return lowu; } int ison[2*maxn]; int can[2*maxn]; vector<int> ans; int main() { freopen("important.in","r",stdin); freopen("important.out","w",stdout); int n, m, s, t; scanf("%d%d", &n, &m); s = 1,t = n; S.init(n+1); T.init(n+1); int u, v, w; for (int i = 1; i <= m; i++){ scanf("%d%d%d", &u, &v, &w); e[i*2-1] = Edge(u, v, w, i*2-1); S.addEdge(u, v, w); T.addEdge(v, u, w); e[i*2] = Edge(v,u,w,i*2); S.addEdge(v,u,w); T.addEdge(u,v,w); } m*=2; S.dijkstra(s); T.dijkstra(t); ll ddd = S.d[t]; ll delta; for (int i = 1; i <= m; i++) { u = e[i].u; v = e[i].v; w = e[i].w; if (S.d[u] + w == S.d[v] && T.d[v] + w == T.d[u]) { G[u].push_back(Edge(u, v, w, i)); G[v].push_back(Edge(v, u, w, i)); ison[i] = 1; } } dfs(s, -1); for (int i = 1; i <= m; i++) { if (isbridge[i]) { ans.push_back((i+1)/2); } } sort(ans.begin(),ans.end()); ans.erase(unique(ans.begin(),ans.end()),ans.end()); printf("%d ",ans.size()); for(int i=0;i<ans.size();i++) printf("%d ",ans[i]); printf(" "); return 0; }