uoj problem 14 DZY Loves Graph

题目:

DZY开始有 \(n\) 个点，现在他对这 \(n\) 个点进行了 \(m\) 次操作，对于第 \(i\) 个操作（从 \(1\) 开始编号）有可能的三种情况：

Add a b：表示在 \(a\) 与 \(b\) 之间连了一条长度为 \(i\) 的边（注意，\(i\)是操作编号）。保证 \(1 \leq a, b \leq n\)。

Delete k：表示删除了当前图中边权最大的k条边。保证 \(k\) 一定不会比当前图中边的条数多。

Return：表示撤销第 \(i-1\) 次操作。保证第 \(1\) 次操作不是 Return 且第 \(i-1\) 次不是 Return 操作。

请你在每次操作后告诉DZY当前图的最小生成树边权和。如果最小生成树不存在则输出 \(0\)。

题解:

首先我们来挖掘一下题目的性质.

加入的边权值递增
如果一条边被删除,那么所有大于这条边权值的边要么没被加入，要么已经被删除.

所以我们可以直接大力可持久化并查集.

\(O(mlog^2n)\) 做一些有理有据的底层优化应该能过掉.

但其实这道题没有那么复杂.

首先我们先忽略掉Return操作.

我们考虑维护动态加入和删除的并查集.

我们可以直接在\(O(mlogn)\)内完成.

但其实加上Return操作后对我们的做法也没有什么影响.

进行每一次操作的时候，我们首先检查一下下一操作是不是Return操作

如果不是Return我们就直接在现有的状态上进行修改.

如果是Return那么我们就计算出当前操作的影响,并不把这份影响加入到我们当前的状态中.

这样我们就可以直接用一维数组解决掉啦..

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long ll;

inline void read(int &x){

    x=0;char ch;bool flag = false;

    while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;

    while(x=10*x+ch-'0',ch=getchar(),ch > '!');if(flag) x=-x;

}

const int maxn = 510010;

int fa[maxn],siz[maxn];

inline int find(int x){

    while(fa[x] != x) x = fa[x];

    return x;

}

int ope[maxn];

char s[12];

struct ope{

    int op,u,v;

}op[maxn];

ll ans[maxn],sum[maxn];

int main(){

    int n,m;read(n);read(m);

    for(int i=1;i<=n;++i) fa[i] = i,siz[i] = 1;

    for(int i=1;i<=m;++i){

	scanf("%s",s);

	if(*s == 'A'){

	    op[i].op = 1;

	    read(op[i].u);

	    read(op[i].v);

	}else if(*s == 'D'){

	    op[i].op = 2;

	    read(op[i].u);

	}else if(*s == 'R') op[i].op = 3;

    }

    int ecnt = 0,nodecnt = n;

    for(int i=1;i<=m;++i){

	if(op[i].op == 1){

	    if(op[i+1].op == 3){

		if(nodecnt == 1) printf("%lld\n",ans[ecnt]);

		else if(nodecnt == 2){

		    int x = find(op[i].u);

		    int y = find(op[i].v);

		    if(x == y) puts("0");

		    else printf("%lld\n",sum[ecnt] + i);

		}else puts("0");

		printf("%lld\n",ans[ecnt]);

		++ i;

	    }else{

		ans[ecnt+1] = ans[ecnt];

		sum[ecnt+1] = sum[ecnt];

		++ecnt;

		int x = find(op[i].u);

		int y = find(op[i].v);

		if(x == y){

		    printf("%lld\n",ans[ecnt]);

		    ope[ecnt] = 0;

		    continue;

		}

		if(siz[x] > siz[y]) swap(x,y);

		fa[x] = y;siz[y] += siz[x];ope[ecnt] = x;

		sum[ecnt] += i;

		if(--nodecnt == 1) ans[ecnt] = sum[ecnt];

		printf("%lld\n",ans[ecnt]);

	    }

	}else if(op[i].op == 2){

	    if(op[i+1].op == 3){

		printf("%lld\n",ans[ecnt-op[i].u]);

		++ i;

		printf("%lld\n",ans[ecnt]);

	    }else{

	        for(int j=0;j<op[i].u;++j){

		    if(ope[ecnt] != 0){

			int x = ope[ecnt];

			++ nodecnt;

			siz[fa[x]] -= siz[x];

			fa[x] = x;

		    }-- ecnt;

		}

		printf("%lld\n",ans[ecnt]);

	    }

	}

    }

    return 0;

}

巴特西

uoj problem 14 DZY Loves Graph

题目:

题解:

最新文章

热门文章