题目链接这里!!!
题目翻译
我依然不会告诉你题目的难度有一半是读题
其实就是给定一个图中一部分点,给定一部分边,先让你求这之中的最小生成树,然后再这个树的基础上求关于所有点和所有边的最大生成树。
好用的最小生成树模板
看到这里我觉得大部分dalao就可以喊着“这出题人语文真差而且这道题真水”去写代码秒题了
如果您还往下看,只有两种可能:
1.yizimi的语文太菜了,题目翻译还是看不懂 2.不会写代码诶
好,基本上就没别的弯路,上代码:
#include <algorithm> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #include <iostream> #include <map> #include <queue> #include <set> #include <stack> #include <string> #include <vector> using namespace std; #define go(i, j, n, k) for (int i = j; i <= n; i += k) #define fo(i, j, n, k) for (int i = j; i >= n; i -= k) #define rep(i, x) for (int i = h[x]; i; i = e[i].nxt) #define mn 20020 #define mm 200010 #define inf 1 << 30 #define ll long long #define ld long double #define fi first #define se second #define root 1, n, 1 #define lson l, m, rt << 1 #define rson m + 1, r, rt << 1 | 1 #define bson l, r, rt inline int read() { int f = 1, x = 0; char ch = getchar(); while (ch > '9' || ch < '0') { if (ch == '-') f = -f; ch = getchar(); } while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return x * f; } inline void write(int x) { if (x < 0) putchar('-'), x = -x; if (x > 9) write(x / 10); putchar(x % 10 + '0'); } //This is AC head above... int n, m; int ans, tot, cnt; bool b[mn]; struct edge { int u, v, w, p; bool used; } e[mm]; inline bool cmp1(edge a, edge b) { return a.w < b.w; } inline bool cmp2(edge a, edge b) { return a.w > b.w; } int father[mn]; inline int findx(int x) { return father[x] == x ? x : father[x] = findx(father[x]); } inline void mergex(int x, int y)//随机合并大法好 { int xx = findx(x); int yy = findx(y); if (xx == yy) return; srand((unsigned)time(NULL));//随机合并 if (rand() % 2) { father[xx] = yy; } else { father[yy] = xx; } } inline void Krus()//最小生成树 { go(i, 1, n, 1) father[i] = i; sort(e + 1, e + m + 1, cmp1); go(i, 1, m, 1) { if (b[e[i].u] && b[e[i].v] && findx(e[i].u) != findx(e[i].v) && e[i].p == 1 && !e[i].used) { ans += e[i].w; mergex(e[i].u, e[i].v); e[i].used = true; cnt++; } if (cnt == tot - 1) return; } } inline void Krub()//最大生成树 { sort(e + 1, e + m + 1, cmp2); go(i, 1, m, 1) { if (findx(e[i].u) != findx(e[i].v) && !e[i].used) { ans += e[i].w; mergex(e[i].u, e[i].v); e[i].used = true; cnt++; } if (cnt == n - 1) return; } } int main() { //freopen("002.in", "r", stdin); //freopen("002.out", "w", stdout); n = read(), m = read(); go(i, 1, n, 1) { b[i] = read(); //cin >> b[i]; //scanf("%d", &b[i]); if (b[i]) tot++; } go(i, 1, m, 1) { e[i].u = read(), e[i].v = read(), e[i].w = read(), e[i].p = read(), e[i].w *= e[i].p, e[i].used = false; //cin >> e[i].u >> e[i].v >> e[i].w >> e[i].p; //scanf("%d%d%d%d", &e[i].u, &e[i].v, &e[i].w, &e[i].p); //e[i].w *= e[i].p, e[i].used = false; }//这里你可以试试cin,保证慢死 Krus(); if (cnt != tot - 1) { cout << -1; return 0; } int ans1 = ans; Krub(); if (cnt != n - 1) { cout << -1; return 0; } cout << ans1 << " " << ans - ans1; return 0; }
有些大佬看到这里可能会说:
明明我写对了,为什么会T?
我只是想说:
dalao您先看看时限!
这个题是300ms,如果你用cin大约是600ms(部分点),不开O2都有可能T掉。
这就是这个题的最大的坑