[UVA][SCC&負環&DP] 11721 - Instant View of Big Bang
|
I I U P C 2 0 0 9 |
|
|
|
|
|
Problem I: Instant View of Big Bang |
|
|
|
|
|
Have you forgot about wormholes? Oh my god! Ok, let me explain again.
A wormhole is a subspace tunnel through space and time connecting two star systems. Wormholes have a few peculiar properties:
1. Wormholes are one-way only. 2. The time it takes to travel through a wormhole is negligible. 3. A wormhole has two end points, each situated in a star system. 4. A star system may have more than one wormhole end point within its boundaries. 5. Between any pair of star systems, there is at most one wormhole in each direction. 6. There are no wormholes with both end points in the same star system.
All wormholes have a constant time difference between their end points. For example, a specific wormhole may cause the person traveling through it to end up 15 years in the future. Another wormhole may cause the person to end up 42 years in the past.
A brilliant physicist, wants to use wormholes to study the Big Bang. Since warp drive has not been invented yet, it is not possible for her to travel from one star system to another one directly. This can be done using wormholes, of course.
The scientist can start her journey from any star system. Then she wants to reach a cycle of wormholes somewhere in the universe that causes her to end up in the past. By traveling along this cycle a lot of times, the scientist is able to go back as far in time as necessary to reach the beginning of the universe and see the Big Bang with her own eyes. Write a program to help her to find such star systems where she can start her journey.
|
|
|
Input |
|
|
The first line of the input will contain T, denoting the number of cases.
Each case starts with a blank line. The next line contains two numbers n and m . These indicate the number of star systems ( 1 ≤ n ≤ 1000 ) and the number of wormholes ( 0 ≤ m ≤ 2000 ). The star systems are numbered from 0 through n-1 . For each wormhole a line containing three integer numbers x, y and t is given. These numbers indicate that this wormhole allows someone to travel from the star system numbered x to the star system numbered y, thereby ending up t ( -1000 ≤ t ≤ 1000 ) years in the future or past, a negative integer denotes past, positive integer denotes future.
|
|
|
Output |
|
|
For each case, print the case number first, then print the star systems (in ascending order) where she can start her journey. If no such star system is found, print 'impossible'.
|
|
|
Sample Input |
Output for Sample Input |
|
2
3 3 0 1 1000 1 2 15 2 1 -42
4 4 0 1 10 1 2 20 2 3 30 3 0 -60 |
Case 1: 0 1 2 Case 2: impossible |
|
|
|
|
Problem Setter: Jane Alam Jan Special Thanks: Md. Abirul Islam |
|
題目描述：
研究員想要藉由蟲洞回到宇宙大爆炸，詢問有哪些點可以當作起點。
題目解法：
先考慮要回到宇宙大爆炸時，也就是必須存在負環，才可以繞回過去。
題目是希望找到負環回去，必須繞非常多圈，而非找到負的目的地。
負環檢查大概要 O(VE)，用 SPFA 也許會快一點。
但我們不能對於每一點都進行負環檢查，也就是從一點出發的負環檢查。
O(V^2 * E) 太慢，會 TLE。
如果按照找負環後，查看哪些點可以到負環，找負環本身就不怎麼方便。
仔細思考一下，負環上的點剛好是一個 SCC 元件。
因此打算找到 SCC 後，查看這個 SCC 完全圖中是否存在負環。
而縮點變成一個 DAG，對於 DAG 作一次 DP 計算即可。
#include <stdio.h>
#include <string.h>
#include <vector>
#include <queue>
#include <deque>
#include <algorithm>
using namespace std;
vector<int> g[1005], vg[1005], ng[1005];
int vfind[1005], findIdx;
int stk[1005], stkIdx;
int in_stk[1005], visited[1005];
int contract[1005];
int dist[1005], inq[1005], inqc[1005];
int hasNeg[1005];
int scc(int nd) {
in_stk[nd] = visited[nd] = 1;
stk[++stkIdx] = nd;
vfind[nd] = ++findIdx;
int mn = vfind[nd], i;
for(i = 0; i < g[nd].size(); i++) {
if(!visited[g[nd][i]])
mn = min(mn, scc(g[nd][i]));
if(in_stk[g[nd][i]])
mn = min(mn, vfind[g[nd][i]]);
}
if(mn == vfind[nd]) {
vector<int> C;
int mC[1005] = {};
do {
in_stk[stk[stkIdx]] = 0;
contract[stk[stkIdx]] = nd;
C.push_back(stk[stkIdx]);
mC[stk[stkIdx]] = 1;
} while(stk[stkIdx--] != nd);
//spfa
int neg = 0;
memset(dist, 63, sizeof(dist));
memset(inq, 0, sizeof(inq));
memset(inqc, 0, sizeof(inqc));
deque<int> Q;
Q.push_front(C[0]), dist[C[0]] = 0;
while(!Q.empty()) {
int tn = Q.front();
Q.pop_front(), inq[tn] = 0;
for(i = 0; i < g[tn].size(); i++) {
if(mC[g[tn][i]]) {
if(dist[g[tn][i]] > dist[tn]+vg[tn][i]) {
dist[g[tn][i]] = dist[tn]+vg[tn][i];
if(inq[g[tn][i]] == 0) {
inq[g[tn][i]] = 1;
if(dist[g[tn][i]] < dist[tn])//Small Label First
Q.push_front(g[tn][i]);
else
Q.push_back(g[tn][i]);
if(++inqc[g[tn][i]] > C.size())
neg = 1;
}
}
}
}
if(neg) break;
}
hasNeg[nd] = neg;
}
return mn;
}
int dp[1005], used[1005];
int dfs(int nd) {
if(used[nd]) return dp[nd];
int i;
dp[nd] = hasNeg[nd];
for(i = 0; i < ng[nd].size(); i++)
dp[nd] |= dfs(ng[nd][i]);
return dp[nd];
}
int main() {
int testcase, cases = 0;
int n, m;
int i, j, k;
int x, y, v;
scanf("%d", &testcase);
while(testcase--) {
scanf("%d %d", &n, &m);
for(i = 0; i < m; i++) {
scanf("%d %d %d", &x, &y, &v);
g[x].push_back(y);
vg[x].push_back(v);
}
memset(visited, 0, sizeof(visited));
memset(in_stk, 0, sizeof(in_stk));
for(i = 0; i < n; i++) {
if(visited[i] == 0) {
findIdx = stkIdx = 0;
scc(i);
}
}
// build DAG
for(i = 0; i < n; i++) {
int x = contract[i], y;
for(j = 0; j < g[i].size(); j++) {
y = contract[g[i][j]];
if(x != y)
ng[x].push_back(y);
}
}
// DP
memset(used, 0, sizeof(used));
for(i = 0; i < n; i++) {
if(contract[i] == i) {
dfs(i);
}
}
printf("Case %d:", ++cases);
int exist = 0;
for(i = 0; i < n; i++)
if(dp[contract[i]])
printf(" %d", i), exist = 1;
if(exist)
puts("");
else
puts(" impossible");
for(i = 0; i < n; i++)
g[i].clear(), vg[i].clear(), ng[i].clear();
}
return 0;
}