HDU 5624 KK's Reconstruction

这题目测是数据水了。我这种暴力写法显然是可以卡超时的。

假设有2000个点，15000条边，前面10000条不能构成树，后面5000条可以，这种数据显然可以卡超时。

#include <stdio.h> #include <algorithm> #include <string.h> #include <queue> #include <stack> #include <map> #include <vector> using namespace std;const int maxn = 2000 + 10; const int maxm = 15000 + 10; const int inf = 0x7fffffff; int T; int n, m; struct Edge {int u;int v;int id;int val; }e[maxm]; int fa[maxn];bool cmp(const Edge&a, const Edge&b) {return a.val<b.val; }void read() {scanf("%d%d", &n, &m);for (int i = 1; i <= m; i++)scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].val);sort(e + 1, e + 1 + m, cmp); }int Find(int x) {if (x != fa[x]) fa[x] = Find(fa[x]);return fa[x]; }void work() {int ans = inf;int i, j;int cnt;for ( i = 1; i <= m; i++){for ( j = 1; j <= n; j++) fa[j] = j;cnt = n;for ( j = i; j <= m; j++){int fu = Find(e[j].u);int fv = Find(e[j].v);if (fu == fv) continue;fa[fu] = fv; cnt--;if (cnt == 1){ans = min(ans, e[j].val - e[i].val);break;}}if (cnt != 1) break;}if (ans == inf) ans = -1;printf("%d\n", ans); }int main() {scanf("%d", &T);while (T--){read();work();}return 0; }

 

转载于:https://www.cnblogs.com/zufezzt/p/5189056.html

总结

以上是生活随笔为你收集整理的HDU 5624 KK's Reconstruction的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。