題目描述:
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=21
算法分析:
對(duì)于一個(gè)pipe, 模擬水位不斷上升, 判斷有多少聯(lián)通link, 就需要多少水量... 還要注意漫溢的情況
如果遇見一個(gè)空pipe, 遞歸處理之...
處理之后, 將那個(gè)pipe聯(lián)通的link合并到當(dāng)前pipe. 并看這個(gè)pipe是否遇到了可行解 / 漫溢的情況
要小心處理判斷的順尋, 因?yàn)轭}中說要"稍微高一些" ...
代碼:
zoj 1021
1 #include<iostream>
2 #include<cstring>
3 #include<cstdio>
4 using namespace std;
5 const int N = 110;
6 struct node {
7 int x, u, d;
8 } num[30];
9 int G[30][N];
10 int vis[N], n, e ,lvl, flag, st, full[N];
11 int dfs(int u, int tp){
12 full[u] = 0;
13 // cout<<u<<" "<<tp<<endl;
14 vis[u] = ++st;
15 int ans = 0;
16 int up = max(tp, num[u].u);
17 for(int l = num[u].d ; l >= up; l--) {
18 int v = G[u][l];
19 if(l != num[u].d)
20 for(int i = 0; i < n; i++){
21 ans += vis[i] >= vis[u];
22 if(vis[i] >= vis[u] && l == num[i].u)
23 full[u] = 1;
24 }
25 if(v != -1 && !vis[v]) {
26 ans += dfs(v,l);
27 for(int i = l+1; i >=0; i--)
28 if(G[v][i] != -1) G[u][i] = G[v][i];
29 if(flag) return ans;
30 full[u] |= full[v];
31 }
32 // cout<<"l: "<<l<<" "<<v<<" "<<ans<<endl;
33 if(l == up) break;
34 if(vis[e] && l <= lvl-full[u]){
35 flag = 1; return ans;
36 }
37 if(full[u]) return ans;
38
39 }
40 return ans;
41 }
42 // main
43 int find(int x){
44 for(int i = 0; i < n; i++)
45 if(num[i].x == x) return i;
46 }
47 int main(){
48 int cas,len,m, x, y;
49 cin >> cas ;
50 while(cas --){
51 cin >> n;
52 for(int i = 0; i < n; i++){
53 cin >> num[i].x >> num[i].u >> len;
54 num[i].d = num[i].u + len;
55 }
56 cin >> m;
57 memset(G,-1,sizeof(G));
58 for(int i = 0; i < m; i++){
59 cin >> x >> y >> len;
60 int a = x - 1, b = x + len;
61 a = find(a); b = find(b);
62 G[a][y] = b;
63 G[b][y] = a;
64 }
65 cin >> e >> lvl;
66 e --;
67 if(lvl <= num[e].u ||lvl > num[e].d) {
68 puts("No Solution");
69 continue;
70 }
71 st = flag = 0;
72 memset(vis, 0 ,sizeof(vis));
73 int ans = dfs(0,0);
74 if(flag) cout << ans << endl;
75 else puts("No Solution");
76 }
77 }
78 posted on 2012-09-03 19:58
西月弦 閱讀(304)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
解題報(bào)告