专栏文章

题解：AT_jsc2019_qual_e Card Collector

EEnoch006
AT_jsc2019_qual_e题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@minjp2wt
此快照首次捕获于
2025/12/02 03:31
3 个月前
此快照最后确认于
2025/12/02 03:31
3 个月前
查看原文
给个不转化，两只 log 的题解。
先操作每一行，最优操作是选每一行最大的数。
再看每一列，每一列肯定想选这一列最大的数，问题是这个点可能被选过了。
考虑反悔贪心，相当于在这一行和这一列中选次大值，相当于合并这行和这列。
由于在操作的过程中，可能会有次大值也被选择的情况，所以相当于再加入一行/一列。
那么可以用并查集维护这些合并的行列的最大值（删除了行和前面列要选的值后），这个可以用 set 启发式合并。
那么复杂度就是两只 log 的，可以看代码：
CPP
#include<bits/stdc++.h>
using namespace std;
namespace Sasuke{
	namespace fast_IO {
#define IOSIZE 100000
	static unsigned int precision = 6, POW[10] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000};	// 向下取整到小数点后第 precision 位
	static char obuf[IOSIZE], *p3 = obuf;
#ifdef ONLINE_JUDGE
	static char ibuf[IOSIZE], *p1 = ibuf, *p2 = ibuf;
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#endif 
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
	template<typename T> static inline T read() { T s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s * w; }
	template<typename T> static inline bool read(T &s) { s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s *= w, true; }
	template<typename T> static inline void print(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) print(x / 10); putchar(x % 10 + 48); }
	static inline bool read(char &s) { while (s = getchar(), isspace(s) and s != EOF); return s != EOF; }
	static inline void print(char x) { putchar(x); }
	static inline bool read(char *s) { char ch; while (ch = getchar(), isspace(ch) && ch != EOF); if (ch == EOF) return false; while (!isspace(ch) and (ch != EOF)) *s++ = ch, ch = getchar(); *s = '\0'; return true; }
	static inline void print(char *x) { while (*x) putchar(*x++); }
	static inline void print(const char *x) { for (int i = 0; x[i]; i++) putchar(x[i]); }
	static inline bool read(std::string& s) { s = ""; char ch; while (ch = getchar(), isspace(ch) and ch != EOF); if (ch == EOF) return false; while (!isspace(ch)) s += ch, ch = getchar(); return true; }
	static inline void print(std::string x) { for (int i = 0, n = x.size(); i < n; i++) putchar(x[i]); }
	static inline bool read(bool &b) { char ch; while(ch=getchar(), isspace(ch) and ch != EOF); return ch == EOF ?false :(b=ch^48, true); }
	static inline void print(bool b) { putchar(b+48); }
	static inline bool read(double &x) { char ch = getchar(); int f = 1; for(; (ch<48 or 57<ch) and (ch != EOF); ch=getchar()) if(ch == '-')	f = -1; if(ch == EOF)	return false; for(x=0; 47<ch and ch<58; ch=getchar())	x = x*10 + (ch^48); if(ch != '.')	return x *= f, true; double y = 0.1; for(ch=getchar(); 47<ch and ch<58; ch=getchar())	x += y*(ch^48), y /= 10; return x *= f, true; }
	static inline void print(double x) { if(x < 0) putchar('-'), x = -x; if(!precision) print((unsigned long long)(x-(unsigned long long)(x)>=0.5 ?x+1 :x)); else { unsigned long long xx = x; double y = ((x-xx)*POW[precision]); unsigned long long yy = (y-(unsigned long long)(y)>=0.5 ?y+1 :y); if(yy == POW[precision])	xx++, yy = 0; print(xx), putchar('.'); for(int j=precision-1; ~j; j--)	putchar(48+yy/POW[j]%10); } }
	template<typename T, typename... T1> static inline int read(T& a, T1&... other) { return read(a) + read(other...); }
	template<typename T, typename... T1> static inline void print(T a, T1... other) { print(a), print(other...); }
	static struct Fast_IO { 
		bool flag = 1;
		inline ~Fast_IO() { fwrite(obuf, p3 - obuf, 1, stdout); } 
		inline void SetPrecision(int x) { if(x > 9)	throw runtime_error("Precision too high!"); else if(x < 0) throw runtime_error("Precision too low!"); else precision = x; } // 浮点数精度设为 x，即精确到小数点后 x 位。
		inline operator bool() { return flag; }
	} io;
	template<typename T> static Fast_IO& operator >> (Fast_IO &io, T &b) { return io.flag &= read(b), io; }
	template<typename T> static Fast_IO& operator << (Fast_IO &io, T b) { return print(b), io; }
#define cout io
#define cin io
#define endl '\n'
} using namespace fast_IO;
	#define ll long long
	#define maxm 1000005
	#define maxn 1005
	#define mod 1000000007
	#define msk cerr
	#define inf 0x3f3f3f3f3f3f
	int cas,T,k,n,m;
	ll ans;
	int siz[maxm<<1];
	struct srh{int x,y,w;}a[maxm];
	struct node{
		int i,w;
		friend bool operator <(node x,node y){return x.w<y.w;}
	};
	inline bool cmp(node x,node y){return x.w>y.w;}
	int vis[maxm],ban[maxm],fa[maxm<<1];
	int pi[maxm<<1];
	vector<node>ha[maxm],li[maxm];
	priority_queue<node>tmp[maxm<<1];//换成懒惰删除的堆 
	inline node Get(priority_queue<node>&q){
		while(q.size()){
			int id=q.top().i;
			if(ban[id]){q.pop();continue;}
			return q.top();
		}
		return {0,0};
	}
	inline node Getha(int x){
		while(pi[x]<siz[x]&&ban[ha[x][pi[x]].i])pi[x]++;
		return pi[x]>=siz[x]?(node){0,0}:ha[x][pi[x]];
	}
	inline node Getli(int y){
		while(pi[y+n]<siz[y+n]&&ban[li[y][pi[y+n]].i])pi[y+n]++;
		return pi[y+n]>=siz[y+n]?(node){0,0}:li[y][pi[y+n]];
	}
	int Getfa(int x){return x==fa[x]?x:fa[x]=Getfa(fa[x]);}
	void Mer(int x,int y){
		x=Getfa(x);y=Getfa(y);
		if(x==y)return;
		if(tmp[x].size()<tmp[y].size())swap(x,y);
		fa[y]=x;
		while(1){
			node p=Get(tmp[y]);
			if(!p.i)break;
			tmp[y].pop();tmp[x].push(p);
		}
	}
	signed main(){
//		ios::sync_with_stdio(0);
//		cin.tie(0);cout.tie(0);
		cin>>k>>n>>m;
		for(int i=1;i<=k;i++){
			cin>>a[i].x>>a[i].y>>a[i].w;
			siz[a[i].x]++;siz[a[i].y+n]++;
		}
		for(int i=1;i<=n;i++)ha[i].reserve(siz[i]);
		for(int i=1;i<=m;i++)li[i].reserve(siz[i+n]);
		for(int i=1;i<=k;i++){
			ha[a[i].x].push_back({i,a[i].w});
			li[a[i].y].push_back({i,a[i].w});
		}
		for(int i=1;i<=m;i++)sort(li[i].begin(),li[i].end(),cmp);
		for(int i=1;i<=n;i++){
			if(ha[i].size()){
				sort(ha[i].begin(),ha[i].end(),cmp);
				node p=ha[i][0];
				int id=p.i;vis[id]=1;
			}
		}
		for(int i=1;i<=n+m;i++)fa[i]=i; 
		for(int i=1;i<=m;i++){
			int f=Getfa(i+n);
			node p=Getli(i);int id=p.i;
			if(id)tmp[f].push({id,a[id].w});
			while(1){//一直寻找 
				node p=Get(tmp[f]);
				int i=p.i,x=a[i].x,y=a[i].y;
				if(!i)break;
				if(!vis[i]){//没有选过该点，好 
					vis[i]=1;
					break;
				}
				Mer(x,y+n);f=Getfa(f);
				ban[i]=1;
				p=Getha(x);
				if(p.i)tmp[f].push(p);
				p=Getli(y);
				if(p.i)tmp[f].push(p);
			}
//			for(int i=1;i<=n+m;i++)msk<<i<<":"<<Getfa(i)<<"\n";
		}
		for(int i=1;i<=k;i++)if(vis[i])ans+=a[i].w;//,msk<<i<<" ";
		cout<<ans;
		return 0;
	}
}
signed main(){
//	freopen("oblivious5_3.in","r",stdin);
	freopen("oblivious.in","r",stdin);
	freopen("oblivious.out","w",stdout);
	Sasuke::main();//while(1);
	return 0; 
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...