kmjp's blog

競技プログラミング参加記です

yukicoder : No.748 yuki国のお財布事情

★3だけど必要知識があれば後は簡単。
https://yukicoder.me/problems/no/748

問題

N点M辺の連結無向グラフが与えられる。
各辺にはコストが設定されている。

このうちグラフの連結性を保つ範囲で、いくつか辺を減らしグラフを構成する辺の総コストを削減したい。
ただし、いくつか減らすことができない辺が指定されている。
減らせるコストの最大値を求めよ。

解法

クラスカル法の要領で、コストの低い辺から使うようにしていけばよい。
ただしコストによらず減らせない辺が存在するので、それらは先に使って辺をつないでおく。

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<101010> uf;

int N,M,K;
int A[101010],B[101010],C[101010];
int need[101010];
pair<int,int> P[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>K;
	FOR(i,M) {
		cin>>A[i]>>B[i]>>C[i];
		P[i]={C[i],i};
	}
	FOR(i,K) {
		cin>>x;
		x--;
		need[x]=1;
		uf(A[x],B[x]);
	}
	
	ll ret=0;
	sort(P,P+M);
	FOR(i,M) {
		x=P[i].second;
		if(uf[A[x]]!=uf[B[x]]) {
			uf(A[x],B[x]);
		}
		else {
			ret+=C[x];
		}
	}
	cout<<ret<<endl;
}

まとめ

でもUnion Find使うし★2.5だと低すぎなのかな。