标签:图论
鱼鱼蒸题。
原图由若干个偶环组成,那么对于每个环分别计算贡献,枚举环上的一段区间,然后算出要能包含这一段的 \(l,r,L,R\) 的对应的最小区间,然后又不能包含这段区间左右的点,所以要去掉一部分,然后乘起来再乘上区间长度的一半即可。
优美的代码实现。
#include <bits/stdc++.h>
#define int long long
#define F(i, a, b) for (int i = (a); i <= (b); i++)
#define dF(i, a, b) for (int i = (a); i >= (b); i--)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 6005, M = (N << 1), inf = 1e16, mod = 1e9 + 7;
int ans, n, m, cnt, vis[N], cir[N];
vector<int> G[N];
void dfs(int u) {
vis[u] = 1; cir[++cnt] = u;
for (auto i : G[u]) if (!vis[i]) dfs(i);
}
int mx1 = 0, mn1 = inf, mx2 = 0, mn2 = inf;
void work(int x) {
if (x <= n) mx1 = max(mx1, x), mn1 = min(mn1, x);
else mx2 = max(mx2, x), mn2 = min(mn2, x);
}
void ckmax(int &x, int y) { if (y > x) x = y; }
void ckmin(int &x, int y) { if (y < x) x = y; }
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n;
m = n * 2;
F(i, 1, m) {
int u, v;
cin >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
}
F(i, 1, n) {
if (!vis[i]) {
mx1 = 0, mn1 = inf, mx2 = 0, mn2 = inf, cnt = 0;
dfs(i);
F(j, 1, cnt) cir[j + cnt] = cir[j];
F(j, 1, cnt) work(cir[j]);
ans += mn1 * (n - mx1 + 1) * (mn2 - n) * (n * 2 - mx2 + 1) * cnt / 2;
F(j, 1, cnt) {
mx1 = 0, mn1 = inf, mx2 = 0, mn2 = inf, work(cir[j]);
F(k, j + 1, j + cnt - 2) {
work(cir[k]);
int val = (k - j + 1) / 2, x[2] = {j == 1 ? cnt * 2 : j - 1, k + 1};
int d1 = 1, u1 = n, d2 = n + 1, u2 = n * 2;
F(p, 0, 1) {
if (cir[x[p]] >= mn1 && cir[x[p]] <= mx1 || cir[x[p]] >= mn2 && cir[x[p]] <= mx2) {val = 0; break;}
if (cir[x[p]] <= n) {
if (cir[x[p]] < mn1) ckmax(d1, cir[x[p]] + 1);
if (cir[x[p]] > mx1) ckmin(u1, cir[x[p]] - 1);
} else {
if (cir[x[p]] < mn2) ckmax(d2, cir[x[p]] + 1);
if (cir[x[p]] > mx2) ckmin(u2, cir[x[p]] - 1);
}
}
ans += (mn1 - d1 + 1) * (u1 - mx1 + 1) * (mn2 - d2 + 1) * (u2 - mx2 + 1) * val;
}
}
}
}
cout << ans;
return 0;
}
标签:cnt,Matchings,int,Sum,mx2,mx1,cir,CF1651E,mn2
From: https://www.cnblogs.com/z-t-rui/p/18235962/CF1651E