贊助廠商

娛樂城推薦

首頁

電腦與網際網路/其他:電腦列表

計算數學 Problem Solving- UVa11865 Directed Graph的MST

這題我卡好久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;}--
  • 發問日期:2021-06-01 22:30:03

友站連結