第一回日本最強プログラマー学生選手権-予選- : E - Card Collector

本番なんとか解けたけどだいぶ遠回りしてしまった。
https://atcoder.jp/contests/jsc2019-qual/tasks/jsc2019_qual_e

問題

H*Wのグリッドに、いくつかのカードが置いてある。
カードにはスコアが書かれており、1つのマスに複数枚のカードがある場合もある。

各列から1枚以下のカードを取り除いたうえで、各行から1枚以下のカードを取り除くとき、取り除くカードのスコアの総和の最大値を求めよ。

解法

カードのスコアの高い順に、貪欲に選べるかどうか判定していく。
その際、下記のデータ構造を持とう。

• 各列・行が有効かどうか
• 各列・行合わせて(H+W)要素からなるUnion-Find構造

列・行の状態に対し、判定対象に対し以下のように処理する。

• 列も行も有効な場合
  • カードのある列と行に対応する要素が連結の場合、カードはとりのぞけるが、列・行およびその連結成分が以後使えなくなる。
  • カードのある列と行に対応する要素が非連結の場合、カードはとりのぞけるが、列・行に対応する要素を連結する。
• 列か行いずれかが有効な場合
  • その列か行を使い、カードを取り除く。当然その列・行とその連結成分は以後使えなくなる。
• 列も行も無効な場合
  • そのカードは選べない。

上記処理は、行か列のいずれかでも利用可能なら貪欲に選んでいくが、その際「行か列いずれかしか選べない」という状態になったものを連結していくことになる。
もし途中で閉路ができてしまった場合、一連の列・行がすべて以後利用不能になる。

int N,H,W;

int R[101010],C[101010],A[101010];
int ok[201010];

template<int um> class UF {
	public:
	vector<int> par,rank,cnt;
	UF() {par=rank=vector<int>(um,0); cnt=vector<int>(um,1); for(int i=0;i<um;i++) par[i]=i;}
	void reinit() {int i; FOR(i,um) rank[i]=0,cnt[i]=1,par[i]=i;}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int count(int x) { return cnt[operator[](x)];}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		cnt[y]=cnt[x]=cnt[x]+cnt[y];
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};
UF<202020> uf;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>H>>W;
	vector<vector<int>> V;
	FOR(i,N) {
		cin>>R[i]>>C[i]>>A[i];
		R[i]--;
		C[i]--;
		V.push_back({A[i],R[i],C[i]});
	}
	FOR(i,H) ok[i]=1;
	FOR(i,W) ok[H+i]=1;
	
	sort(ALL(V));
	reverse(ALL(V));
	ll ret=0;
	FORR(v,V) {
		int y=v[1];
		int x=v[2];
		
		if(ok[uf[y]]&&ok[uf[H+x]]) {
			if(uf[y]==uf[H+x]) {
				ok[uf[y]]=0;
			}
			else {
				uf(y,H+x);
			}
			ret+=v[0];
		}
		else if(ok[uf[y]]) {
			ok[uf[y]]=0;
			ret+=v[0];
		}
		else if(ok[uf[H+x]]) {
			ok[uf[H+x]]=0;
			ret+=v[0];
		}
	}
	cout<<ret<<endl;
	
}

まとめ

本番ではUnion-FindとDFS両方やってしまい面倒な実装をしてしまった。