正文
HDU 6041 - I Curse Myself | 2017 Multi-University Training Contest 1
小程序：扫一扫查出行【扫一扫了解最新限行尾号】
复制小程序
和题解大致相同的思路
/*
HDU 6041 - I Curse Myself [ 图论,找环,最大k和 ] | 2017 Multi-University Training Contest 1
题意：
给出一个仙人掌图，求最小的k棵生成树
N <= 1000, M <= 2000, K <= 1e5
分析：
将问题转化为从每个环中选出一条边，求最大的k个和
首先找环，随便怎么找，比如 在保证每条边只走一次的情况下遍历到祖先节点就说明有环，记录一下前驱就能找出来
然后是每个环两两合并，此时相当于两个vector，res.size() = k，cir[i].size() = Mi, ∑mi = M
由于 M<=2000,k <= 1e5，故选择在堆中的元素是cir[i]中的元素
这样就能保证复杂度为 O( ∑K*log(mi) ) = O( K*log(∏mi) ) <= O(K*M) 编码时长: INF(-8)
*/
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const LL MOD = 1LL<<32;
const int N = 1005;
struct Edge {
int to, next, w;
bool vis;
}edge[N<<2];
int head[N], tot;
void init() {
memset(head, -1, sizeof(head));
tot = 0;
}
void addedge(int u, int v, int w) {
edge[tot].to = v; edge[tot].next = head[u];
edge[tot].vis = 0; edge[tot].w = w;
head[u] = tot++;
}
int n, m, block;
vector<int> cir[N];
bool vis[N];
int f[N], g[N];//父节点和连着的边
void dfs(int u)
{
for (int i = head[u]; i != -1; i = edge[i].next)
{
int v = edge[i].to;
if (edge[i].vis) continue;
edge[i].vis = 1;
edge[i^1].vis = 1;
if (vis[v])
{
++block;
int t = u;
do{
cir[block].push_back(edge[g[t]].w);
t = f[t];
}while (t != v);
cir[block].push_back(edge[i].w);
}
else
{
vis[v] = 1, f[v] = u, g[v] = i;
dfs(v);
}
}
}
void find_cir()
{
for (int i = 0; i < N; i++) cir[i].clear();
memset(vis, 0, sizeof(vis));
block = 0;
vis[1] = 1;
dfs(1);
}
struct Node {
int x, id;
bool operator < (const Node& b) const {//大的先出去
return x < b.x;
}
};
priority_queue<Node> Q;
vector<int> res, tmp;
void solve(int k)
{
res.clear();
res.push_back(0);
for (int i = 1; i <= block; ++i)
{
while (!Q.empty()) Q.pop();
tmp.clear();
for (auto& x : cir[i])
Q.push(Node{x+res[0], 0});
while (tmp.size() < k && !Q.empty())
{
auto p = Q.top(); Q.pop();
tmp.push_back(p.x);
if (p.id+1 < res.size())
{
++p.id;
p.x += res[p.id] - res[p.id-1];
Q.push(p);
}
}
res.clear();
for (auto& x : tmp) res.push_back(x);
}
}
int main()
{
int tt = 0, u, v, w, k;
while (~scanf("%d%d", &n, &m))
{
init();
LL sum = 0, ans = 0;
for (int i = 1; i <= m; i++)
{
scanf("%d%d%d", &u, &v, &w);
sum += w;
addedge(u, v, w); addedge(v, u, w);
}
find_cir();
scanf("%d", &k);
solve(k);
for (int i = 0; i < res.size(); i++)
ans += (i+1) * ( (sum-res[i])) % MOD;
printf("Case #%d: %lld\n", ++tt, ans%MOD);
}
}
限制第k小的大小后，满足这个限制的答案的数量具有单调性，故还可以二分第k小 暴力DFS+剪枝 验证，就是代码不算好写
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int N = 1005;
const LL MOD = 1LL<<32;
struct Edge {
int to, next, w;
bool vis;
}edge[N<<2];
int head[N], tot;
void init() {
memset(head, -1, sizeof(head));
tot = 0;
}
void addedge(int u, int v, int w) {
edge[tot].w = w; edge[tot].to = v; edge[tot].next = head[u];
edge[tot].vis = 0;
head[u] = tot++;
}
int block;
vector<int> cir[N];
int f[N], g[N], vis[N];
void dfs(int u)
{
for (int i = head[u]; ~i; i = edge[i].next)
{
if (edge[i].vis) continue;
edge[i].vis = 1;
edge[i^1].vis = 1;
int v = edge[i].to;
if (vis[v])
{
++block;
int t = u;
do {
cir[block].push_back(edge[g[t]].w);
t = f[t];
}while (t != v);
cir[block].push_back(edge[i].w);
}
else
{
vis[v] = 1;
f[v] = u, g[v] = i;
dfs(v);
}
}
}
void find_cir()
{
for (int i = 0; i < N; i++) cir[i].clear();
memset(vis, 0, sizeof(vis));
block = 0;
vis[1] = 1;
dfs(1);
}
bool cmp (const int &x, const int &y) {
return x > y;
}
int n, m, k, num;
LL mid, res[100005];
void dfs(int i, LL sum)
{
if (num > k) return;
if (sum > mid) return;
if (i == block+1)
{
res[++num] = sum; return;
}
for (auto& x : cir[i])
{
if (sum + x > mid) break;
dfs(i+1, sum+x);
}
}
LL BinaryFind(LL l, LL r)
{
while (l <= r)
{
mid = (l+r)>>1;
num = 0;
dfs(1, 0);
if (num >= k) r = mid-1;
else l = mid+1;
}
return l;
}
int main()
{
int t = 0, x, y, z;
while (~scanf("%d%d", &n, &m))
{
init();
LL base = 0, ans = 0;
for (int i = 1; i <= m; i++)
{
scanf("%d%d%d", &x, &y, &z);
addedge(x, y, z), addedge(y, x, z);
base += z;
}
find_cir();
scanf("%d", &k);
printf("Case #%d: ", ++t);
if (block == 0)
{
printf("%lld\n", base%MOD); continue;
}
for (int i = 1; i <= block; i++)
{
sort(cir[i].begin(), cir[i].end(), cmp);
base -= cir[i][0];
for (int j = 1; j < cir[i].size(); j++)
cir[i][j] = cir[i][0] - cir[i][j];
cir[i][0] = 0;
}
int Max = 1;
for (int i = 1; i <= block && Max < k; i++)
Max *= cir[i].size();
if (k > Max)
{
k = Max;
mid = 2e9;
num = 0;
dfs(1, 0);
}
else
{
mid = BinaryFind(1, 2e9);
mid--;
num = 0;
dfs(1, 0);
for (int i = num+1; i <= k; i++) res[i] = mid+1;
}
sort(res+1, res+k+1);
for (int i = 1; i <= k; i++)
ans += i * (base+res[i]) % MOD;
printf("%lld\n", ans% MOD);
}
}
