1640
题意：
一张无向图
在最小化最大边后求最大边权和
Slove：
sort
最小生成树
倒叙最大生成树
#include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <cstring> #include <string> using namespace std; #define LL long long #define gc getchar() inline int read() {int x = 0, f = 1; char c = gc; while(c < ‘0‘ || c > ‘9‘) {if(c == ‘-‘) f = -1; c = gc;} while(c >= ‘0‘ && c <= ‘9‘) x = x * 10 + c - ‘0‘, c = gc; return x * f;} inline LL read_LL() {LL x = 0; char c = gc; while(c < ‘0‘ || c > ‘9‘) c = gc; while(c >= ‘0‘ && c <= ‘9‘) x = x * 10 + c - ‘0‘, c = gc; return x;} #undef gc const int N = 1e5 + 10; int fa[N]; int A[N << 1], U[N << 1], V[N << 1], W[N << 1]; int n, m; bool Cmp(int a, int b) {return W[a] < W[b];} int Get(int x) {return fa[x] == x ? x : fa[x] = Get(fa[x]);} void Minst(int &R) { for(int i = 1; i <= n; i ++) fa[i] = i; int js = 0; for(int i = 1; i <= m; i ++) { int fu = Get(U[A[i]]), fv = Get(V[A[i]]); if(fu != fv) { fa[fu] = fv; js ++; } if(js == n - 1) { R = i; while(W[A[R + 1]] == W[A[i]]) R ++; return ; } } } inline long long Maxst(int R) { for(int i = 1; i <= n; i ++) fa[i] = i; int js = 0; long long ret = 0; for(int i = R; i >= 1; i --) { int fu = Get(U[A[i]]), fv = Get(V[A[i]]); if(fu != fv) { fa[fu] = fv; ret += W[A[i]]; js ++; } if(js == n - 1) return ret; } } int main() { n = read(), m = read(); for(int i = 1; i <= m; i ++) A[i] = i, U[i] = read(), V[i] = read(), W[i] = read(); sort(A + 1, A + m + 1, Cmp); int R; Minst(R); cout << Maxst(R); return 0; }
1649
由于 1 - n 之间一定存在一种直接相连的道路
判断哪种直接相连
跑另外一种的最短路
#include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <cstring> #include <string> using namespace std; #define LL long long #define gc getchar() inline int read() {int x = 0; char c = gc; while(c < ‘0‘ || c > ‘9‘) c = gc; while(c >= ‘0‘ && c <= ‘9‘) x = x * 10 + c - ‘0‘, c = gc; return x;} inline LL read_LL() {LL x = 0; char c = gc; while(c < ‘0‘ || c > ‘9‘) c = gc; while(c >= ‘0‘ && c <= ‘9‘) x = x * 10 + c - ‘0‘, c = gc; return x;} #undef gc const int N = 410, oo = 999999999; int Map[N][N], Bmap[N][N]; int n, m; int main() { n = read(), m = read(); for(int i = 1; i <= n; i ++) for(int j = 1; j <= n; j ++) Map[i][j] = oo; for(int i = 1; i <= n; i ++) Map[i][i] = 0; for(int i = 1; i <= n; i ++) for(int j = 1; j <= n; j ++) Bmap[i][j] = oo; for(int i = 1; i <= n; i ++) Bmap[i][i] = 0; for(int i = 1; i <= m; i ++) { int u = read(), v = read(); Map[u][v] = Map[v][u] = 1; } if(Map[1][n] == 1) { for(int i = 1; i <= n; i ++) for(int j = 1; j <= n; j ++) { if(i == j) continue; if(Map[i][j] == oo) Bmap[i][j] = 1; } for(int k = 1; k <= n; k ++) for(int i = 1; i <= n; i ++) for(int j = 1; j <= n; j ++) Bmap[i][j] = min(Bmap[i][j], Bmap[i][k] + Bmap[k][j]); if(Bmap[1][n] == oo) cout << -1; else cout << Bmap[1][n]; } else { for(int k = 1; k <= n; k ++) for(int i = 1; i <= n; i ++) for(int j = 1; j <= n; j ++) Map[i][j] = min(Map[i][j], Map[i][k] + Map[k][j]); if(Map[1][n] == oo) cout << -1; else cout << Map[1][n]; } return 0; }
1535
图是树的充要条件
$m = n - 1$ && 图联通
由于题目无自环
所以不存在二元环
并且若 $m >= n - 1$
则图联通
此时若 $m = n$
那么就会存在且只存在一个三元环（或更大）
因此只需判断 $n = m$ 即可
if(n == m) cout << "FHTAGN!"; else cout << "NO";
原文：https://www.cnblogs.com/shandongs1/p/9591918.html