注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

vfleaking的博客

My name is VFlea King

 
 
 

日志

 
 

2307: [Ctsc2011]无穷图的桥  

2013-03-24 00:33:51|  分类: 衡阳八中 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
A掉了好开心……
几天之前hza说有这么一道题,于是我跑去看了看……
由于这题名字太喜感了所以在嘴里念叨了几天,终于忍不住放下POI 2010的做题进度来搞此题。
这两天都在搞这题,托hza的洪福终于A掉了。


怎么样……这个题解……是不是觉得被坑了……
这题之所以成为神题是因为曹钦翔神犇的官方题解未免也太不详细了吧!!屡次YY出来错误算法……代码写了删删了写。
一口血喷出来……

这里有贾教的代码。

其实有一份不清晰的题解 + 一个风格良好的代码是足以A掉此题的~
非常感谢贾教的神代码~orz
不保证下面介绍的就是曹钦翔的官方解法,我介绍的是贾教的程序里的算法。

为了说话方便……我们把图中的边分为两种:横边和竖边。
还有一般省掉“极大”两个字……对于连通分量和边双连通分量。

G是我们关注的那个图。
首先由于G是无穷图,那么把删掉第一行的结点后形成的图仍然是G。立即推出删掉前s行的结点后形成的图仍然是G。
由于G是连通图,所以删掉前s行的结点后形成的图仍然是连通图。

假设你现在只需要决定第一行哪些横边是桥。
那么我们只看第一行的结点,只看第一行的横边,这样形成了一个图G1,如果某条边在这个图里面不是桥,那它在G中就一定不是桥。(显然)
在G1中是桥,在G中是不是一定是桥呢?
显然不是!!
因为可以绕到下面的行去,再杀回来,形成一个环。
于是我们陷入了很囧的境地,连决定第一行都束手无策。

我们先管不了那么许多……把边双联通分量缩起来再说……因为边双联通分量里面的边之后永远都不可能是桥。
发现出现了迷人的树~

发现删掉第一行后的图仍然是连通图,所以任意两点间一定存在一条路径。
所以如果有两条竖边,且两个竖边的上端在G1中是处于同一个联通块的,那么两个上端对应的G1中的双联通分量间的所有桥,是不是一定不会是G中的桥鸟?(两个下端在G中是连通的)
既然不是桥,要之做甚……
于是我们搬来两个并查集,ufs1和ufs2。(实在起不出好名字了……毁了我的代码风格……)ufs1负责把G1中的连通分量缩一起,ufs2负责把非桥的边缩一起。
一开始的时候先dfs一遍搞出初始的ufs1、ufs2。接着扫一遍所有竖边,把上端在G1中属于同一连通块的边处理一下,将两上端之间双连通分量缩在一起。发现这两个过程是可以裹在一起做的。
m2是竖边的个数,e2存的是所有竖边,visited是dfs时有没有访问过,preE[v]是指向dfs时产生的生成树上的结点v连向父亲的边的指针。
dfs就是dfs。
topE2Idx[v]表示对于dfs产生的生成树的根v,编号最小的上端是v所处连通分量的结点的竖边。
unionPath是把两个结点之间的双连通分量全部缩起来。
isBri2[i]表示编号为i的竖边是否是桥。

for (int i = 1; i <= m2; i++)
{
if (!visited[e2[i].v])
{
preE[e2[i].v] = NULL;
dfs(e2[i].v);
topE2Idx[e2[i].v] = i;
}
else
{
int t = ufs1.Find(e2[i].v);
unionPath(e2[i].v, e2[topE2Idx[t]].v);
isBri2[topE2Idx[t]] = isBri2[i] = false;
}
}


这样就确定了第一行的横边的生存状态。
由于G是连通图,所以发现第s行的某条边是不是桥,其实与第s + 1行无关。
现在我们来用扫描线来搞~

定义概念:
第i行的奇葩连通分量:只考虑前i行的边,若第i行的两个结点v、u之间有路,则v、u属于一个奇葩连通分量。
第i行的奇葩边双连通分量:只考虑前i行的边,若第i行的两个结点v、u之间有不经过G中的桥的路,则v、u属于一个奇葩边双连通分量。
第i行的奇葩分量:上面那两个东西的总称。

那么刚才的工作,我们已经求出来了第1行的奇葩分量了。
令ufs1[i]记录第i行的奇葩连通分量,ufs2[i]记录第i行的奇葩边双连通分量。
而我们刚才实际上已经求出来了ufs1[1]、ufs2[1]。
如果已知第i - 1行的奇葩分量,如何求第i行的奇葩分量呢?

扫描线的任务:每次通过第i - 1行的奇葩分量,计算出第i行的奇葩分量,和第i行的是G的桥的横边、第i行与第i +1行间的是G的桥的竖边。

如果两个结点v、u在第i - 1行是属于同一个奇葩连通分量,那么在第i行也必然属于同一个奇葩连通分量。奇葩边双连通分量也是一样。
而且两层之间的竖边我们是知道的。
2307: [Ctsc2011]无穷图的桥 - vfleaking - vfleaking的博客
那么我们初始时先让ufs1[i] = ufs[i - 1], ufs2[i] = ufs2[i - 1],那么是什么导致ufs1[i]和ufs2[i]有异于ufs1[i - 1]和ufs2[i - 1]呢?
发现是竖边惹的祸。

【情况零】假设第i-1行的某奇葩连通分量和第i行的某个奇葩边双连通分量有多条边。
显然可以删成一条吧囧!!

【情况一】假设第i-1行的某奇葩连通分量和第i行的某个奇葩边双连通分量有边
2307: [Ctsc2011]无穷图的桥 - vfleaking - vfleaking的博客
那么这个奇葩连通分量实际上是非常没有存在感的……因为它不可能对第i层有任何贡献……
于是这样的无存在感的第i - 1行的奇葩连通分量在一秒钟内全部消失。

【情况二】如果第i - 1行的某奇葩连通分量和第i行的某两个处于同一奇葩连通分量的边双连通分量有边:
2307: [Ctsc2011]无穷图的桥 - vfleaking - vfleaking的博客
那么因为形成了个环,所以相连的那两倒霉奇葩边双连通分量之间的那条路径上的边就全都不是G中的桥了。
于是unionPath一下。

【情况三】如果第i - 1行的某奇葩连通分量和第i行的两个奇葩连通分量有边:
2307: [Ctsc2011]无穷图的桥 - vfleaking - vfleaking的博客
那么第i层的那两个倒霉的奇葩连通分量应该合并在一起,因为可以通过那条向上走再向下走的路连通。这是对ufs1[i]的修改。
发现ufs2[i]似乎也要改改诶……肿么改呢……好像很复杂。
好像上面那幅图蒙蔽了我们的双眼……
2307: [Ctsc2011]无穷图的桥 - vfleaking - vfleaking的博客
而值得注意的是,如果两条竖边上端所处的奇葩连通分量相同,那么这两条边肯定都不是G的桥……
所以每个奇葩连通分量最多只有一条很有特色的桥,这个桥的上端位于这个奇葩连通分量中。
于是我们用topE2Idx数组来维护这个很有特色的桥~(之前出现过)
一个奇葩连通分量内部一定会是由奇葩双连通分量形成的树组成的。我们让那个很有特色的桥的在这个奇葩连通分量的那一端的结点作为这棵树的根。
那么第i层的那两个倒霉奇葩连通分量对应的奇葩双连通分量的树的根奇葩双连通分量进行在ufs2[i]中进行合并,合并出来的那家伙作为新根,而ufs1[i]中的新的奇葩连通分量的topE2Idx可以随便设一个自己喜欢的东西了……原来的那两个topE2Idx已经不是桥了,所以可以随便玩了……。正确性显然吧。(这一段是不是很抽象啊 T_T)
这样剩下的事情就和情况二相同。

于是对于一个第i - 1行的奇葩连通分量,我们可以不断讨论上面的情况然后把大家都消成没有存在感的奇葩连通分量。

对于刚才说的“所以XXX肯定不是桥”,就等比数列求和公式给这条边结算,然后之后都不把它当桥。
对于一直都是桥的就用那个啥……10 * 边的权值来更新答案。

于是我们骄傲的宣布,此题已解决
………………………………………………………………吗?
发现晴空万里的无穷图的桥的天空上漂浮着两朵小乌云……
发现为了更新,我们每次都要把所有的边扫一遍……
而且也不知道啥时候结束……
时间复杂度O(inf)

优化就是每次动态维护下边的集合,这个边不是一般的边,而是第i - 1行的奇葩连通分量连向第i层的结点的边。如果两条边的上端处于同一个第i- 1行的奇葩连通分量,下端处于同一个第i行的奇葩边双连通分量,就当相同的边去重。
等等……现在还不知道第i行的奇葩边双连通分量啊……
没关系嘛……一开始的时候我们是ufs1[i] = ufs1[i - 1], ufs2[i] = ufs2[i - 1]。就以这个为标准。(因为之后我们是逐步求出ufs1[i]、ufs2[i]……所以……啊……是吧……我实在是解释不清楚了,求自行脑补。)

那么扫描线多了一个任务:计算出第i行与第i +1行间的边的集合。
现在看看目前状态:
2307: [Ctsc2011]无穷图的桥 - vfleaking - vfleaking的博客
 
 
实在是不会画这么复杂的图……实在看不懂就无视掉……
第i - 1行连向第i行的边,其下端一定处于同一个奇葩边双连通分量中。
如果第i - 1行对第i行有XXXX的边,则第i行也对第i + 1行有XXXX的边。
而曾经的第i - 1行的奇葩连通分量现在已经变成了第i层某个奇葩连通分量中的一员了。
于是可以扫所有第i - 1行奇葩连通分量,把他们的边附加在第i行对应的奇葩连通分量中。

但是立刻就发现噩耗了,这样每次扫描线移动一次,我们都要O(奇葩连通分量个数)地处理。
而且仍然不知道啥时候结束。

我们发现没有存在感的奇葩连通分量是很奇葩的,如果大家都是没有存在感的奇葩连通分量,那么就可以结束算法了。
那么是不是发现一个没有存在感的奇葩连通分量就可以直接删掉它呢?发现不是……因为未来有一天它可能会被派上用场。

进而发现我们可以维护一个动态数组valid,记录当前有存在感的奇葩连通分量有哪些。
发现如果第i行的一个奇葩连通分量没有被某条第i - 1行与第i行之间的竖边连接,那么这个奇葩连通分量一定是没有存在感的。因为要么它之前不在valid列表中,那么显然它仍然没有存在感。要么之前在valid列表中,由于没有竖边来惹它,也就没有发生任何合并操作,它连出去的边的下端一定都缩到同一个边双连通分量中了,那么它就成为了没有存在感的了。

于是我们扫一遍第i - 1行的valid,对于有存在感的每个奇葩通分量v:
由于我们已经通过情况二、情况三对边进行了处理,所以现在valid中所有奇葩连通分量都变成没存在感的了。
我们称onlyU[v]是结点v唯一一个与之相邻的第i层的奇葩边双连通分量。
设u = onlyU[v]
再来看第i - 1行的v往下连的边的集合,发现这些边的下端一定是在u中的。也就是说对于某一条边(v, k),k实际是属于u的。再定义k'为与k同一列的第i - 1行的那个结点,则onlyU[k'所处的奇葩连通分量]这家伙好像有点神奇……
再定义onlyU‘[k'所处的奇葩连通分量]表示与onlyU[k'所处的连通分量]同一列的第i + 1行的那个奇葩边双连通分量。
u要连一条边到onlyU'[k'所处的奇葩连通分量]对不对!!!因为一旦有边下一行同位置地方依然有边嘛!!!
这样就可以知道第i行的奇葩连通分量向下连的边~排序去重后去掉没有存在感的,就得到了第i行的valid。

还有就是那啥……我不知道这题的时间复杂度呃囧……
忽略并查集的那个反阿克曼函数……当作是O(1)

我不清楚这个算法是O(n + m)还是O(nm)……
一开始就会把所有边压缩到了O(n)级别了……
某条边被缩起来了就再也不会被访问了……
而缩边只会发生O(n)次吧……
所以这部分是O(n)。
而之前还要求边双联通分量啊干啥的,是O(n + m)。
所以总时间复杂度是O(n + m)?

求神犇鉴定上面的分析对不对……
反正能在1s以内跑出最大点……

要是木有看懂……详细的看代码吧,各种滚动数组……汗……

神题难,难于上青天,使人听此凋朱颜!

代码:(这题各种毁代码风格……代码丑死了……千万别照着我的代码写……会让你一边写一边吐槽……)

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

#define ALL(a) (a).begin(), (a).end()
#define SIZE(a) (int)(a).size()

const int MaxN = 300000;
const int MaxM1 = 500000;
const int MaxM2 = 500000;

inline int getint()
{
char c;
while (c = getchar(), '0' > c || c > '9');

int res = c - '0';
while (c = getchar(), '0' <= c && c <= '9')
res = res * 10 + c - '0';
return res;
}

template <class T>
inline void tension(T &a, const T &b)
{
if (b < a)
a = b;
}

struct edge
{
int v, u, w;
};
struct halfEdge
{
int u, w;
halfEdge *next;
};
halfEdge adj_pool[MaxM1 * 2], *adj_tail = adj_pool;

int n, m1, m2;
halfEdge *adj[MaxN + 1];
edge e2[MaxM2 + 1];

inline halfEdge *opposite(const halfEdge *i)
{
return adj_pool + ((i - adj_pool) ^ 1);
}

inline void addEdge(const int &v, const int &u, const int &w)
{
adj_tail->u = u, adj_tail->w = w;
adj_tail->next = adj[v], adj[v] = adj_tail++;
}
inline int getE1Idx(const halfEdge *i)
{
return ((i - adj_pool) >> 1) + 1;
}
inline edge getE1(const int &idx)
{
edge res;
res.v = adj_pool[(idx - 1) << 1 | 1].u;
res.u = adj_pool[(idx - 1) << 1].u;
res.w = adj_pool[(idx - 1) << 1].w;
return res;
}

class UnionFindSet
{
private:
int f[MaxN + 1];
public:
inline void Init()
{
for (int i = 1; i <= n; i++)
f[i] = i;
}
inline int Find(const int &v)
{
int res;
for (res = v; f[res] != res; res = f[res]);
for (int i = v, j = f[v]; i != res; f[i] = res, i = j, j = f[i]);
return res;
}
inline void Union(int v, int u)
{
f[Find(u)] = Find(v);
}
};

UnionFindSet ufs1, ufs2;

bool visited[MaxN + 1];
halfEdge *preE[MaxN + 1];

int topE2Idx[MaxN + 1];

bool isBri1[MaxM1 + 1], isBri2[MaxM2 + 1];

void dfs(const int &v)
{
visited[v] = true;
for (halfEdge *i = adj[v]; i; i = i->next)
if (i != preE[v])
{
if (!visited[i->u])
{
preE[i->u] = opposite(i);
dfs(i->u);
ufs1.Union(v, i->u);
}
else
{
int cur = ufs2.Find(v);
while (ufs2.Find(cur) != ufs2.Find(i->u))
{
isBri1[getE1Idx(preE[cur])] = false;
ufs2.Union(preE[cur]->u, cur);
cur = ufs2.Find(cur);
}
isBri1[getE1Idx(i)] = false;
}
}
}

inline double unionPath(int v, int u)
{
static bool book[MaxN + 1];

v = ufs2.Find(v), u = ufs2.Find(u);

int tv = v, tu = u;
while (tv != tu && !book[tv] && !book[tu])
{
if (preE[tv])
book[tv] = true, tv = ufs2.Find(preE[tv]->u);
if (preE[tu])
book[tu] = true, tu = ufs2.Find(preE[tu]->u);
}
int lca = book[tv] ? tv : tu;

for (int i = v; i != tv; i = ufs2.Find(preE[i]->u))
book[i] = false;
book[tv] = false;
for (int i = u; i != tu; i = ufs2.Find(preE[i]->u))
book[i] = false;
book[tu] = false;

double res = 0.0;
for (int i = v; i != lca; i = ufs2.Find(i))
{
isBri1[getE1Idx(preE[i])] = false;
res += preE[i]->w;
ufs2.Union(preE[i]->u, i);
}
for (int i = u; i != lca; i = ufs2.Find(i))
{
isBri1[getE1Idx(preE[i])] = false;
res += preE[i]->w;
ufs2.Union(preE[i]->u, i);
}

return res;
}

int main()
{
freopen("2307.in", "r", stdin);
freopen("2307.out", "w", stdout);

cin >> n >> m1 >> m2;
for (int i = 1; i <= m1; i++)
{
int v = getint(), u = getint(), w = getint();
// ((1, v), (1, u), w)
addEdge(v, u, w);
addEdge(u, v, w);
}

for (int i = 1; i <= m2; i++)
{
e2[i].v = getint(), e2[i].u = getint(), e2[i].w = getint();
// ((1, v), (2, u), w)
}

ufs1.Init();
ufs2.Init();

fill(isBri1 + 1, isBri1 + m1 + 1, true);
fill(isBri2 + 1, isBri2 + m2 + 1, true);

double res = 0.0;
for (int i = 1; i <= m2; i++)
{
if (!visited[e2[i].v])
{
preE[e2[i].v] = NULL;
dfs(e2[i].v);
topE2Idx[e2[i].v] = i;
}
else
{
int t = ufs1.Find(e2[i].v);
unionPath(e2[i].v, e2[topE2Idx[t]].v);
isBri2[topE2Idx[t]] = isBri2[i] = false;
}
}

// adjacency table of two adjacent layers
static vector<int> adjB[MaxN + 1];
static int onlyU[MaxN + 1];
for (int i = 1; i <= m2; i++)
adjB[ufs1.Find(e2[i].v)].push_back(ufs2.Find(e2[i].u));

int valid_n = 0;
static int valid[MaxN];
for (int v = 1; v <= n; v++)
if (v == ufs1.Find(v))
{
sort(ALL(adjB[v]));
adjB[v].erase(unique(ALL(adjB[v])), adjB[v].end());

if (SIZE(adjB[v]) > 1)
valid[valid_n++] = v;
if (SIZE(adjB[v]) == 1)
onlyU[v] = adjB[v][0];
else
onlyU[v] = 0;
}

for (double coe = 1.0; valid_n > 0; coe *= 0.9)
{
static vector<int> backup[MaxN + 1];
for (int i = 0; i < valid_n; i++)
{
int v = valid[i];
for (vector<int>::iterator pu = adjB[v].begin(); pu != adjB[v].end(); pu++)
backup[v].push_back(ufs1.Find(*pu));
}

for (int i = 0; i < valid_n; i++)
{
int v = valid[i];

int u1 = adjB[v][0];
int idx1 = topE2Idx[ufs1.Find(u1)];
if (isBri2[idx1])
{
isBri2[idx1] = false;
res += (10 - 9 * coe) * e2[idx1].w;
}

for (int j = 1; j < SIZE(adjB[v]); j++)
{
int u2 = adjB[v][j];
int idx2 = topE2Idx[ufs1.Find(u2)];

if (ufs1.Find(u1) != ufs1.Find(u2))
{
ufs1.Union(u1, u2);
ufs2.Union(e2[idx1].v, e2[idx2].v);

if (isBri2[idx2])
{
isBri2[idx2] = false;
res += (10 - 9 * coe) * e2[idx2].w;
}
}
res += (10 - 9 * coe) * unionPath(u1, u2);
}
}

static int cnt[MaxN + 1];
for (int i = 0; i < valid_n; i++)
{
int v = valid[i];
onlyU[v] = ufs2.Find(adjB[v][0]);
cnt[ufs1.Find(onlyU[v])]++;
adjB[v].clear();
}

int tvalid_n = 0;
for (int i = 0; i < valid_n; i++)
{
int v = valid[i];

for (vector<int>::iterator pu = backup[v].begin(); pu != backup[v].end(); pu++)
if (onlyU[*pu])
adjB[ufs1.Find(onlyU[v])].push_back(ufs2.Find(onlyU[*pu]));
backup[v].clear();

int cur = ufs1.Find(onlyU[v]);
if (--cnt[cur] == 0)
{
sort(ALL(adjB[cur]));
adjB[cur].erase(unique(ALL(adjB[cur])), adjB[cur].end());

if (SIZE(adjB[cur]) > 1)
valid[tvalid_n++] = cur;
else if (SIZE(adjB[cur]) == 1)
onlyU[cur] = adjB[cur][0];
}
}

valid_n = tvalid_n;
}

for (int i = 1; i <= m1; i++)
if (isBri1[i])
res += 10 * getE1(i).w;
for (int i = 1; i <= m2; i++)
if (isBri2[i])
res += 10 * e2[i].w;

cout << fixed << setprecision(2) << res << endl;

return 0;
}


  评论这张
 
阅读(1444)| 评论(3)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017