【陶冶情操】续 CF 240E, 一些意外状况.
这次的内容是左偏树优化的朱刘算法。
今天颓极无聊感觉如果没有写过O(ElogV)的std就在题解里写“鉴于CF上几乎没人能过E=10^5的链加反向边就不加这个数据了”的话没有什么说服力，所以写了一下。
先写的是一个不用输出方案的裸题，然后改了改就变成输出方案的了。
朱刘算法有多种implementation。我在试题准备阶段作为std的那个O(VE)的思想是一次性加进所有边，然后经过多轮找环缩环直到没环为止的，这个是仿照了dc.的写法。我当时就是看着他的代码敲下来的。这样子一来，每时每刻的图都是一个图，维护起来比较没有维护树那么方便，不容易优化。我不是data structure master，但是我见得太多了，树比图不知道好维护到哪里去了，我在为维护图的捉急啊，真的。
Tarjan的论文里有另一种写法，这个写法是这样的，一开始没有边，然后按照一定的次序加进边，遇到环就缩。所以每时每刻都是树，有优化的余地。
话虽这么说，但是其实根本没有用到任何树的数据结构，连树结构都没有维护过……
这个写法维护的是一些强连通分量（下简记做strC）和一些弱连通（基图连通）分量（下简记做wkC），每个wkC中缩掉每个strC后成为一个有根树。每次，找到一个除"1"所在的strC以外的，某个wkC的根strC。找到一个权值最小的连向这个strC中点的边<u, v>。
根据这个边的起点讨论:
如果u和v在同一个strC（也就是那个strC）中，不管这条边。因为之前用了权值更小的边已经让这些点成strC了。
否则，如果u和v在同一个wkC中，由于v所在的那个strC是这个wkC的根strC，所以u的strC是v的strC的一个后代。只要保存每个strC的父亲，就可以快速做出要成环的strC序列。这些strC就缩成了一个strC。然后就是改权值，这没有什么不同的。
否则，u和v在不同的wkC中，这时候就直接加上这条边就可以了。
遗留问题：
1. 如何实现每次快速地找到一个权值最小的边？同时strC还会合并。
你需要一个支持整体加减，支持取最小值，支持合并的优先队列。用打标记的左偏树。
2. 如何描述strC和wkC的合并？
问这种问题的人应该回去pj组重膜冰茶姬。
3. 如何维护每个strC的父亲？
在写strC的合并时候，把那些非根strC并到根strC中。这时只有“u和v在不同的wkC中”的那种情况会需要对父亲数组进行操作。话说这是问题吗……
4. 如何每次找到有可用边的根strC？
用一个set保存所有可能有可用边的strC。每次在set里随便找一个元素找边。如果一个strC不再是根strC（即情况3），erase掉。如果其他的strC被并入了某个strC（即情况2），insert它（吸纳新鲜血液以后就又有可能有可用边了）。如果一个strC的Leftist*已经是NULL了，也erase掉。
5. 如何输出方案？
还是像原来一样搞Info结构体，推标记。你需要支持Info*的加法（标记叠加）和减法（标记作用）。
6. 正确性？
不会证。@tarjan。虽然我不会证但是A掉还是没有什么问题的。
贴个代码。最后祝您，浑身难受。
// Author: Ruchiose
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<set>
#include<vector>
#define i64 long long
#define d64 long double
#define fortodo(i, f, t) for (i = f; i <= t; i++)
using namespace std;
struct Info
{
int sig;
int cost, used;
Info *compn[2];
Info() {}
Info(int cost)
{
sig = 0; compn[0] = compn[1] = NULL;
this->cost = cost; used = 0;
}
Info(bool isBothPosi, Info* compn0, Info* compn1)
{
sig = (isBothPosi) ? 1 : -1;
compn[0] = compn0;
compn[1] = compn1;
cost = compn[0]->cost + sig * compn[1]->cost;
used = 0;
}
void pick()
{
used++;
}
void inhr()
{
if (sig)
{
compn[0]->used += used;
compn[1]->used += sig * used;
used = 0;
}
}
};
Info emptyInfo(0);
vector<Info*> derived;
Info* Add(Info* a, Info* b)
{
if (a == &emptyInfo) return b;
if (b == &emptyInfo) return a;
Info* nxt = new Info(true, a, b);
derived.push_back(nxt);
return nxt;
}
Info* Sub(Info* a, Info* b)
{
if (b == &emptyInfo) return a;
Info* nxt = new Info(false, a, b);
derived.push_back(nxt);
return nxt;
}
struct Leftist
{
Leftist* s[2];
pair<Info*,int> val;
Info *Mask;
int Dist;
Leftist(pair<Info*,int> nval = std::pair<Info*,int>(&emptyInfo, 0))
{
s[0] = s[1] = NULL;
Dist = 1;
val = nval; Mask = &emptyInfo;
}
int Key()
{
return val.first->cost;
}
};
int dist(Leftist* cur)
{
return (cur) ? cur->Dist : 0;
}
void Push(Leftist* cur)
{
if (cur->s[0]) cur->s[0]->Mask = Add(cur->s[0]->Mask, cur->Mask);
if (cur->s[1]) cur->s[1]->Mask = Add(cur->s[1]->Mask, cur->Mask);
cur->val.first = Sub(cur->val.first, cur->Mask);
cur->Mask = &emptyInfo;
}
Leftist* Merge(Leftist* l, Leftist* r)
{
if (l == NULL) return r;
if (r == NULL) return l;
Push(l); Push(r);
if (l->Key() > r->Key())
swap(l, r);
l->s[1] = Merge(l->s[1], r);
if (dist(l->s[0]) < dist(l->s[1]))
swap(l->s[0], l->s[1]);
l->Dist = dist(l->s[1]) + 1;
return l;
}
pair<Info*,int> Extract(Leftist* &cur)
{
Push(cur);
pair<Info*,int> ret = cur->val;
cur = Merge(cur->s[0], cur->s[1]);
return ret;
}
const int MAXN = 100010;
const int MAXM = 100010;
int N, M;
Leftist* heap[MAXN];
struct UFS
{
int F[MAXN];
void Init()
{
int i;
fortodo(i, 1, N) F[i] = i;
}
int Find(int x)
{
return (F[x] == x) ? x : Find(F[x]);
}
void Union(int x, int y)
{
F[Find(y)] = Find(x);
}
bool Cnx(int x, int y)
{
return Find(x) == Find(y);
}
};
UFS weak, strong;
set<int> activeStrong;
void Join(int u, int v) // u & v are Strong C. , u is Root Strong C. of its Weak C.
{
strong.Union(u, v);
heap[u] = Merge(heap[u], heap[v]);
heap[v] = NULL;
activeStrong.insert(u);
}
Info baseInfo[MAXM], *prevCost[MAXN];
int prev[MAXN], Ans;
bool Connected()
{
int i;
fortodo(i, 1, N)
if (!weak.Cnx(1, i))
return false;
return true;
}
int main()
{
int i;
scanf("%d%d", &N, &M);
fortodo(i, 1, N) heap[i] = NULL;
fortodo(i, 1, M)
{
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
baseInfo[i] = Info(w);
if (v == 1) continue;
heap[v] = Merge(heap[v], new Leftist(make_pair(&baseInfo[i], u)));
}
activeStrong.clear();
fortodo(i, 2, N)
activeStrong.insert(i);
weak.Init();
strong.Init();
Ans = 0;
while (activeStrong.size())
{
int s0 = *activeStrong.begin();
if (heap[s0] == NULL)
{
activeStrong.erase(s0);
continue;
}
pair<Info*,int> pdi = Extract(heap[s0]);
int S = strong.Find(pdi.second);
if (S == s0) continue;
if (!weak.Cnx(pdi.second, s0))
{
prev[s0] = pdi.second;
prevCost[s0] = pdi.first;
Ans += pdi.first->cost;
pdi.first->pick();
weak.Union(pdi.second, s0);
activeStrong.erase(s0);
continue;
}
vector<int> LIZ;
LIZ.clear();
LIZ.push_back(strong.Find(pdi.second));
while (LIZ.back() != s0)
LIZ.push_back(strong.Find(prev[LIZ.back()]));
Ans += pdi.first->cost;
pdi.first->pick();
if (heap[s0]) heap[s0]->Mask = Add(heap[s0]->Mask, pdi.first);
int SZ = LIZ.size();
fortodo(i, 0, SZ - 2)
if (heap[LIZ[i]])
heap[LIZ[i]]->Mask = Add(heap[LIZ[i]]->Mask, prevCost[LIZ[i]]);
fortodo(i, 0, SZ - 2)
Join(s0, LIZ[i]);
}
if (!Connected())
{
printf("-1\n");
return 0;
}
printf("%d\n", Ans);
vector<int> VI;
VI.clear();
for (vector<Info*>::reverse_iterator rit = derived.rbegin(); rit != derived.rend(); rit++)
(*rit)->inhr();
fortodo(i, 1, M)
if ((baseInfo[i].used) && (baseInfo[i].cost))
VI.push_back(i);
fortodo(i, 0, Ans - 1)
printf("%d%s", VI[i], (i == Ans - 1) ? "\n" : " ");
if (Ans == 0) printf("\n");
}
Dec 16, 2014 06:52:46 PM
orz 约大爷