1.1万

xyzfrozen

LIERLIER
no_one

Seveness
yuefanxiao
pccc

yrf_zwh

qing_lin
77777777777

123_34
Dumby_cat
ACWING__1227

4个月前

#include<iostream>
#include<string>
#include<vector>
#include<cmath>
#include<algorithm>
#include<set>
#include<stack>
#include<map>
#include<cstring>
#include<queue>
using namespace std;
const int N = 505;
int pos[N][2], p[N];
bool vis[N];
typedef long long ll;
int find(int x) {
return x == p[x] ? x : (p[x] = find(p[x]));
}
ll getDist(int r1, int c1, int r2, int c2) {
return (r1 - r2) * (r1 - r2) + (c1 - c2) * (c1 - c2);
}
bool cmp(vector<ll>& a, vector<ll>& b) {
return a[2] < b[2];
}
int main()
{
int n, k;
cin >> n >> k;
for (int i = 0; i < n; i++) cin >> pos[i][0] >> pos[i][1], p[i] = i;
if(k >= n) {
cout << "0.00";
return 0;
}
vector<vector<ll>> e;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
e.push_back({ i, j, getDist(pos[i][0], pos[i][1], pos[j][0], pos[j][1]) });
}
}
sort(e.begin(), e.end(), cmp);
int cnt = 1;
double ans = 0;
for (int i = 0; i < e.size(); i++) {
auto v = e[i];
if (find(v[0]) != find(v[1])) {
p[find(v[0])] = find(v[1]);
ans = v[2];
++cnt;
if(n - cnt == k - 1) {
break;
}
}
}
ans = sqrt(ans);
printf("%.2f", ans);
return 0;
}


5个月前
#include<iostream>
#include<string>
#include<vector>
#include<cmath>
#include<algorithm>
#include<set>
#include<stack>
#include<map>
#include<cstring>
#include<queue>
using namespace std;
typedef long long ll;
const int N = 1e4 + 5, M = 5e4 + 5;
int h[N], e[M], edge[M], w[M], idx;
int scc[N], low[N], dfn[N], instk[N], siz[N], tot, cnt;
stack<int> stk;
void add(int u, int v) {
e[idx] = v;
edge[idx] = h[u];
h[u] = idx++;
}
void tarjan(int x) {
low[x] = dfn[x] = ++tot;
stk.push(x), instk[x] = 1;
for (int i = h[x]; i != -1; i = edge[i]) {
int ne = e[i];
if (!dfn[ne]) {
tarjan(ne);
low[x] = min(low[ne], low[x]);
}
else if (instk[ne]) {
low[x] = min(low[x], dfn[ne]);
}
}
if (dfn[x] == low[x]) {
int y;
++cnt;
do {
y = stk.top();
stk.pop();
instk[y] = 0;
scc[y] = cnt;
siz[cnt]++;
} while (y != x);
}
}
int main()
{
memset(h, -1, sizeof(h));
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
int v;
while (cin >> v && v) {
}
}
for (int i = 1; i <= n; i++) {
if (!dfn[i]) tarjan(i);
}
vector<int> idg(cnt + 1), odg(cnt + 1);
for (int i = 1; i <= n; i++) {
for (int j = h[i]; j != -1; j = edge[j]) {
int ne = e[j];
if (scc[i] != scc[ne]) {
idg[scc[ne]]++, odg[scc[i]]++;
}
}
}
int ans1 = 0, ans2 = 0;
for (int i = 1; i <= cnt; i++) {
if (idg[i] == 0) ++ans1;
if (odg[i] == 0) ++ans2;
}
// 入度为0的个数
cout << ans1 << "\n";
// 入度为0和出度为0的最大值，如1->3,2->3，要使他们变成强连通分量，则需要加3->1,3->2；又如1->2,1->3，要使他们变成强连通分量，则需要加2->1,3->1
if (cnt > 1) cout << max(ans1, ans2);
else cout << 0;
return 0;
}


5个月前
#include<iostream>
#include<string>
#include<vector>
#include<cmath>
#include<algorithm>
#include<set>
#include<stack>
#include<map>
#include<cstring>
#include<queue>
using namespace std;
typedef long long ll;
const int N = 1e4 + 5, M = 5e4 + 5;
int h[N], e[M], edge[M], w[M], idx;
int scc[N], low[N], dfn[N], instk[N], siz[N], tot, cnt;
stack<int> stk;
void add(int u, int v) {
e[idx] = v;
edge[idx] = h[u];
h[u] = idx++;
}
void tarjan(int x) {
low[x] = dfn[x] = ++tot;
stk.push(x), instk[x] = 1;
for (int i = h[x]; i != -1; i = edge[i]) {
int ne = e[i];
if (!dfn[ne]) {
tarjan(ne);
low[x] = min(low[ne], low[x]);
}
else if (instk[ne]) {
low[x] = min(low[x], dfn[ne]);
}
}
if (dfn[x] == low[x]) {
int y;
++cnt;
do {
y = stk.top();
stk.pop();
instk[y] =
scc[y] = cnt;
siz[cnt]++;
} while (y != x);
}
}
int main()
{
memset(h, -1, sizeof(h));
int n, m;
cin >> n >> m;
while (m--) {
int u, v;
cin >> u >> v;
}
for (int i = 1; i <= n; i++) {
if (!dfn[i]) tarjan(i);
}
vector<vector<int>> g(cnt + 1);
vector<int> odg(cnt + 1);
for (int i = 1; i <= n; i++) {
for (int j = h[i]; j != -1; j = edge[j]) {
int ne = e[j];
if (scc[i] != scc[ne]) {
g[scc[i]].push_back(scc[ne]), odg[scc[i]]++;
}
}
}
int ans = 0, zero = 0;
for (int i = 1; i <= cnt; i++) {
if (odg[i] == 0) ans = siz[i], ++zero;
}
// 如果存在多个出度为0的点，则输出0
if (zero > 1) cout << 0;
else cout << ans;
return 0;
}


7个月前

#include<bits/stdc++.h>
using namespace std;
const int N = 1005, M = 2e4 + 5;
int n, m, k;
int h[N], ne[M], e[M], w[M], idx, st[N], dist[N];
void add(int a, int b, int c) {
ne[idx] = h[a];
e[idx] = b;
w[idx] = c;
h[a] = idx++;
}
struct HeapNode {
int id, val;
bool operator < (const HeapNode& t) const {
return val > t.val;
}
};
bool dijkstra(int x) {
memset(dist, 0x3f, sizeof(dist));
memset(st, 0, sizeof(st));
dist[1] = 0;
priority_queue<HeapNode> q;
q.push({1, 0});
while(!q.empty()) {
auto node = q.top();
q.pop();
int t = node.id;
if(st[t]) continue;
st[t] = true;
for(int i = h[t];i != -1;i = ne[i]) {
int j = e[i];
if(dist[j] > dist[t] + (w[i] > x)) {
dist[j] = dist[t] + (w[i] > x);
q.push({j, dist[j]});
}
}
}
return dist[n] <= k;
}
int main()
{
memset(h, -1, sizeof(h));
cin >> n >> m >> k;
for(int i = 0;i < m;i++) {
int a, b, c;
cin >> a >> b >> c;
}
dijkstra(0);
if(dist[n] == 0x3f3f3f3f) {
cout << -1;
return 0;
}
int l = 0, r = 1e8;
while(l < r) {
int mid = (l + r) >> 1;
if(dijkstra(mid)) r = mid;
else l = mid + 1;
}
cout << r;
return 0;
}


7个月前

#include<bits/stdc++.h>
using namespace std;
const int N = 5e4 + 5, M = 2e5 + 5;
int h[N], ne[M], e[M], w[M], idx;
int tar[6], dist[6][N], vis[N];
void add(int a, int b, int c) {
e[idx] = b;
ne[idx] = h[a];
w[idx] = c;
h[a] = idx++;
}
struct HeapNode {
int id, val;
bool operator < (const HeapNode& t) const {
return val > t.val;
}
};
void dijkstra(int s, int id) {
memset(dist[id], 0x3f, sizeof(dist[id]));
memset(vis, 0, sizeof(vis));
dist[id][s] = 0;
priority_queue<HeapNode> q;
q.push({s, 0});
while(!q.empty()) {
auto node = q.top();
q.pop();
int t = node.id;
if(vis[t]) continue;
vis[t] = true;
for(int i = h[t];i != -1;i = ne[i]) {
int j = e[i];
if(dist[id][j] > dist[id][t] + w[i]) {
dist[id][j] = dist[id][t] + w[i];
q.push({j, dist[id][j]});
}
}
}
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n, m;
memset(h, -1, sizeof(h));
cin >> n >> m;
unordered_map<int, int> mp;
tar[0] = 1;
for(int i = 1;i <= 5;i++) cin >> tar[i], mp[tar[i]] = i;
mp[1] = 0;
for(int i = 0;i < m;i++) {
int a, b, c;
cin >> a >> b >> c;
}
for(int i = 0;i <= 5;i++) dijkstra(tar[i], mp[tar[i]]);
sort(tar + 1, tar + 6);
int ans = 0x3f3f3f3f;
do {
int sum = 0;
for(int i = 0;i < 5;i++) {
sum += dist[mp[tar[i]]][tar[i + 1]];
}
ans = min(sum ,ans);
} while(next_permutation(tar + 1, tar + 6));
cout << ans << "\n";
return 0;
}


7个月前

$f[i][0]$：第i个结点被父节点观察
$f[i][1]$：第i个结点被至少一个子节点观察
$f[i][2]$：第i个结点本身有哨兵
$f[i][0] = ∑min(f[j][1], f[j][2])$
$f[i][1] = 枚举k有哨兵∑(f[k][2] + f[i][0] - min(f[k][1], f[k][2]))$
$f[i][2] = ∑min(f[j][0], f[j][1], f[j][2])$

#include<bits/stdc++.h>
using namespace std;
const int N = 1505;
int h[N], ne[N], w[N], e[N], idx, not_root[N];
int f[N][3];
void add(int a, int b) {
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
void dfs(int node) {
f[node][2] = w[node];
for (int i = h[node]; i != -1; i = ne[i]) {
int j = e[i];
dfs(j);
f[node][0] += min(f[j][1], f[j][2]);
f[node][2] += min(f[j][0], min(f[j][1], f[j][2]));
}
f[node][1] = 1e9;
for (int i = h[node]; i != -1; i = ne[i]) {
int j = e[i];
f[node][1] = min(f[node][1], f[j][2] + f[node][0] - min(f[j][1], f[j][2]));
}
}
int main()
{
memset(h, -1, sizeof(h));
int n;
scanf("%d", &n);
for(int i = 0;i < n;i++) {
int id, m, wg;
scanf("%d%d%d", &id, &wg, &m);
w[id] = wg;
for(int j = 0;j < m;j++) {
int b;
scanf("%d", &b);
not_root[b] = 1;
}
}
int root;
for(int i = 1;i <= n;i++) {
if(!not_root[i]) root = i;
}
dfs(root);
printf("%d", min(f[root][1], f[root][2]));
return 0;
}


7个月前

### 观察的是边而不是点，所以必有$dp[i][0] = dp[e[i]][1]$

#include<bits/stdc++.h>
using namespace std;
// 状态表示：dp[i][j]表示当前节点i状态为j，使以i为根节点的子树合法的最少士兵数，j=0表示不选，j=1表示选
const int N = 1505;
int f[N][2];
int h[N], ne[N], e[N], idx;
bool not_root[N];
void add(int a, int b) {
ne[idx] = h[a];
e[idx] = b;
h[a] = idx++;
}
void dfs(int node) {
if(h[node] == -1) {
f[node][0] = 0;
f[node][1] = 1;
return;
}
int res1 = 0, res2 = 0;
for(int i = h[node];i != -1;i = ne[i]) {
dfs(e[i]);
res2 += f[e[i]][1], res1 += min(f[e[i]][0], f[e[i]][1]);
}
f[node][0] = res2;
f[node][1] = res1 + 1;
}
int main()
{
int n;
while(scanf("%d", &n) != EOF) {
memset(h, -1, sizeof(h));
idx = 0;
memset(not_root, 0, sizeof(not_root));
memset(f, 0x3f, sizeof(f));
for(int i = 0;i < n;i++) {
int m, a;
scanf("%d:(%d)", &a, &m);
for(int j = 0;j < m;j++) {
int b;
scanf("%d", &b);
not_root[b] = 1;
}
}
int root;
for(int i = 0;i < n;i++) {
if(!not_root[i]) root = i;
}
dfs(root);
cout << min(f[root][0], f[root][1]) << "\n";
}
return 0;
}


7个月前

#include<bits/stdc++.h>
using namespace std;
const int N = 1005;
// 状态表示：dp[i][j]表示第i个结点保留j个树枝的最大苹果数量，这j个树枝是与其连通的子树边
int dp[N][N], n, m, inf;
int h[N], ne[N], w[N], e[N], idx;
void add(int a, int b, int c) {
ne[idx] = h[a];
e[idx] = b;
w[idx] = c;
h[a] = idx++;
}
void dfs(int node, int fa) {
dp[node][0] = 0;
for(int i = h[node];i != -1;i = ne[i]) {
if(e[i] == fa) continue;
dfs(e[i], node);
for(int k = n;k >= 0;k--) {
for(int j = 0;j <= n;j++) {
if(k - j - 1 >= 0) dp[node][k] = max(dp[node][k], dp[node][k - j - 1] + dp[e[i]][j] + w[i]);
}
}
}
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
memset(dp, -0x3f, sizeof(dp));
memset(h, -1, sizeof(h));
cin >> n >> m;
for(int i = 0;i < n - 1;i++) {
int a, b, c;
cin >> a >> b >> c;
}
dfs(1, -1);
cout << dp[1][m] << "\n";
return 0;
}


7个月前
#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 + 5, M = 2 * N;
int h[N], e[M], ne[M], w[M], idx;
int d1[N], d2[N], up[N], son[N];
void add(int a, int b, int c) {
e[idx] = b;
ne[idx] = h[a];
w[idx] = c;
h[a] = idx++;
}
void dfs_up(int node, int fa) {
for(int i = h[node];i != -1;i = ne[i]) {
int j = e[i];
if(j == fa) continue;
dfs_up(j, node);
int res = d1[j] + w[i];
if(res >= d1[node]) {
d2[node] = d1[node];
d1[node] = res;
son[node] = j;
}
else if(res > d2[node]) {
d2[node] = res;
}
}
}
void dfs_down(int node, int fa) {
for(int i = h[node];i != -1;i = ne[i]) {
int j = e[i];
if(j == fa) continue;
if(son[node] == j) up[j] = max(up[node], d2[node]) + w[i];
else up[j] = max(up[node], d1[node]) + w[i];
dfs_down(j, node);
}
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n;
cin >> n;
memset(h, -1, sizeof(h));
for(int i = 0;i < n - 1;i++) {
int a, b, c;
cin >> a >> b >> c;
}
dfs_up(1, -1);
dfs_down(1, -1);
int ans = 0x3f3f3f3f;
for(int i = 1;i <= n;i++) ans = min(ans, max(d1[i], up[i]));
cout << ans;
return 0;
}


7个月前
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5, M = 2 * N;
int h[N], w[N], ne[M], e[N], idx, ans;
void add(int a, int b, int c) {
w[idx] = c;
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
int dfs(int node, int fa) {
int dist = 0, d1 = 0, d2 = 0;
for(int i = h[node];i != -1;i = ne[i]) {
int j = e[i];
if(j == fa) continue;
int res = dfs(j, node) + w[i];
dist = max(res, dist);
if(res >= d1) d2 = d1, d1 = res;
else if(res > d2) d2 = res;
}
ans = max(d1 + d2, ans);
return dist;
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n;
memset(h, -1, sizeof(h));
cin >> n;
for(int i = 0;i < n - 1;i++) {
int a, b, c;
cin >> a >> b >> c;