标签：最小生成树 int path 暴力枚举 c++ 范围 价值 cin 平面
https://vjudge.net/contest/325913#overview
A.Threehouses
题意：一直二维平面上的$n$个点中，前$e$个点落在小岛周围，并且有$p$条边已经连接，问最少花费使得所有点都可以通过一些边到达小岛，两点之间建边的花费为两点间的欧式距离。
思路：根据$kruskal$求最小生成树的方法将前$e$个点合并起来，再将已有$p$条边的两点合并，之后做一次$kruskal$把所有点合并即可。
#include
using namespace std;
const int maxn = 1000 + 10;
int fa[maxn];
double x[maxn], y[maxn], dist[maxn][maxn];
int tot;
struct node {
int u, v;
double val;
bool operator
C.Cops ans Robbers
题意：给定图中只有字母点可以设立障碍，问让小偷所在的位置$B$无法达到边界所需设立障碍的最小花费。
思路：先说做法。考虑最小割，对每个点拆点，让$u$到$u^{‘}$的流量为该点对应的值，如果该点不能设立障碍则为$inf$，然后对一个点$u$的相邻点连一条$u^{‘}$到$v$流量为$inf$的边，如果越界那么就连向汇点$T$，流量依旧为$inf$。这样做使得每个格点所在的路径流向$T$的最小割只会被其上的价值最小的点所限制，由于建图时所有相邻格点都有连边，所以从源点出发时不会漏边。
#include
using namespace std;
typedef long long LL;
const int N = 1000 + 5;
const int inf = 0x3f3f3f3f;
const LL linf = 0x3f3f3f3f3f3f3f3f;
int n, m, c, T;
LL val[26];
char mp[N][N];
struct Dinic {
static const int maxn = 1e6 + 5;
static const int maxm = 4e6 + 5;
struct Edge {
int u, v, next;
LL flow, cap;
} edge[maxm];
int head[maxn], level[maxn], cur[maxn], eg;
void addedge(int u, int v, LL cap) {
edge[eg] = {u, v, head[u], 0, cap}, head[u] = eg++;
edge[eg] = {v, u, head[v], 0, 0}, head[v] = eg++;
}
void init() {
eg = 0;
memset(head, -1, sizeof head);
}
bool makeLevel(int s, int t, int n) {
for(int i = 0; i q; q.push(s);
level[s] = 1;
while(!q.empty()) {
int u = q.front();
q.pop();
for(int i = head[u]; ~i; i = edge[i].next) {
Edge &e = edge[i];
if(e.flow 0) {
e.flow += flow;
rev.flow -= flow;
return flow;
}
}
}
return 0;
}
LL max_flow(int s, int t, int n) {
LL res = 0;
while(makeLevel(s, t, n)) {
LL flow;
while((flow = findpath(s, t)) > 0) {
if(res >= linf) return res;
res += flow;
}
}
return res;
}
} di;
int id(int r, int c) {
if(r n || c m) return T;
return (r - 1) * m + c;
}
LL getVal(int r, int c) {
if(r n || c m) return linf;
if(mp[r][c] == ‘.‘ || mp[r][c] == ‘B‘) return linf;
else return val[mp[r][c] - ‘a‘];
}
int main() {
scanf("%d%d%d", &m, &n, &c);
for(int i = 1; i = linf ? -1 : ans);
return 0;
}
/*
10 10 1
..........
..........
..........
...a.a....
..a.a.a...
.a..B.a...
..aaaaa...
..........
..........
..........
1
*/
E.Coprime Integers
题意：给定$a,b,c,d$，求$\sum_{i=a}^{b}\sum_{j=c}^{d}[gcd(i,j)=1]$，$[t=1]$表示$t$等于$1$时的值为$1$，否则为$0$。
思路：容斥原理+莫比乌斯反演，考虑$solve(n,m)=\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)=1]$，可以发现$ans=solve(b,d)-solve(a-1,d)-solve(c-1,b)+solve(a-1,c-1)$。接着考虑如何计算$solve(n,m)$
$\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)=1]$
$=\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{t|i,t|j}u(t)$
$=\sum_{t=1}^{min(n,m)}u(t)\sum_{i=1}^{\left \lfloor \frac{n}{t} \right \rfloor}\sum_{j=1}^{\left \lfloor \frac{m}{t} \right \rfloor}1$
$=\sum_{t=1}^{min(n,m)}u(t)\left \lfloor \frac{n}{t} \right \rfloor\left \lfloor \frac{m}{t} \right \rfloor$
预处理莫比乌斯函数前缀和之后整除分块即可在$O(\sqrt n)$复杂度内求出一次$solve$。
#include
using namespace std;
typedef long long LL;
const int N = 1e7 + 5;
int p[N / 10], cnt, mu[N];
bool tag[N];
void getPrime() {
mu[1] = 1;
for(int i = 2; i
H.Heir‘s Dilemma
题意：求$L$到$H$之间满足位数是$6$位，且没有某一位是$0$，且能被每一位的数字整除的数的个数。
思路：数据范围很小，暴力枚举每个数$check$是否可行即可。
#include
using namespace std;
bool ck(int x) {
bool vis[10];
for(int i = 0; i > a >> b;
for(int i = a; i
ComWin’ round 11部分题解
标签：最小生成树 int path 暴力枚举 c++ 范围 价值 cin 平面
原文地址：https://www.cnblogs.com/DuskOB/p/11517554.html