PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

[問題] UVa11865 Directed Graph的MST已刪文

看板Prob_Solve (計算數學 Problem Solving)作者darrenlee1 (darrenleeleelee)時間4年前 (2020/06/22 00:39)推噓3(3推 0噓 5→)

留言8則, 3人參與討論串1/1

這題我卡好久TLE，這題是directed graph要找minimum spanning tree，加上他 time limit只給1秒，用了二分搜的方法我還是一直TLE，請問我還有哪邊可以優化嗎? 題目: https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=0&problem=2965&mosmsg=Submission+received+with+ID+25162727 #include <bits/stdc++.h> using namespace std; const int maxn = 60+5; const int INF = 0x3f3f3f3f; struct Edge { int from, to, cap, cost; }; Edge E[maxn * maxn], e[maxn * maxn]; int n, m, c; int in[maxn], pre[maxn], id[maxn], vis[maxn]; int CLE(int root, int n, int m, int lowest_b) { int res = 0; while(1) { for(int i = 0; i < n; i++){ in[i] = INF; } for(int i = 0; i < m; i++){ int from = e[i].from, to = e[i].to; if(from != to && e[i].cap >= lowest_b && e[i].cost < in[to]){ in[to] = e[i].cost; } pre[to] = from; } for(int i = 0; i < n; i++){ if(i == root) continue; if(in[i] == INF) return -1; } int num = 0; memset(id, -1, sizeof(id)); memset(vis, -1, sizeof(vis)); in[root] = 0; for(int i = 0; i < n; i++){ res += in[i]; int v = i; while(vis[v] != i && id[v] == -1 && v != root) { vis[v] = i; v = pre[v]; } if(v != root && id[v] == -1) { for(int j = pre[v]; j != v; j = pre[j]){ id[j] = num; } id[v] = num++; } } if(num == 0) break; for(int i = 0; i < n; i++){ if(id[i] == -1) id[i] = num++; } for(int i = 0; i < m; i++){ int from = e[i].from, to = e[i].to; e[i].from = id[from]; e[i].to = id[to]; if(id[from] != id[to]) e[i].cost -= in[to]; } n = num; root = id[root]; } return res; } int main(int argc, char const *argv[]) { int T; scanf("%d", &T); while(T--){ scanf("%d%d%d", &n, &m, &c); int L = 0x3f3f3f3f, R = -1; for(int i = 0; i < m; i++){ scanf("%d%d%d%d", &E[i].from, &E[i].to, &E[i].cap, &E[i].cost); R = max(R, E[i].cap); L = min(L, E[i].cap); } int res = -1; while(L <= R){ int M = (L + R) / 2; for(int i = 0; i < m; i++) e[i] = E[i]; int tmp = CLE(0, n, m, M); if(tmp == -1 || tmp > c){ R = M - 1; } else{ L = M + 1; res = M; } } if(res == -1){ printf("streaming not possible.\n"); } else{ printf("%d kbps\n", res); } } return 0; } -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.228.211.220 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1592757544.A.7B1.html