Codeforces Global Round 12 : E. Capitalism

レート増減0だった回。
https://codeforces.com/contest/1450/problem/E

問題

連結グラフが与えられている。
辺は、無向辺と有向辺がある。
各点vに整数値A[v]を設定したい。
この時、辺(u,v)があるならA[v]=A[u]+1となるようにしたい。

各無向辺の向きを任意に決められるとき、条件を満たすAが存在するか。
存在するなら、そのうちAの最大値と最小値の差が最小のものを1つ示せ。

解法

各点vがA[v]=0とした場合、他の点の値をどこまで小さくできるか考える。
辺(u,v)があったとき、

• 有効辺ならA[v]≦A[u]+1、A[u]≦A[v]-1
• 無向辺ならA[v]≦A[u]+1、A[u]≦A[v]+1

よってAが上記を満たすよう、N回ループしてAの最大値を抑え込んでいく。

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

int N,M;
vector<pair<int,int>> E[202];
int D[303];
int ma=-1;
int R[303];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>x>>y>>r;
		x--;y--;
		E[x].push_back({y,r});
		E[y].push_back({x,-r});
		uf(x*2,y*2+1);
		uf(y*2,x*2+1);
		if(uf[x*2]==uf[x*2+1]) return _P("NO\n");
	}
	FOR(i,N) {
		FOR(j,N) D[j]=1010;
		D[i]=0;
		FOR(j,N+1) {
			FOR(x,N) FORR(e,E[x]) {
				if(e.second==0 || e.second==1) D[e.first]=min(D[e.first],D[x]+1);
				if(e.second==-1) D[e.first]=min(D[e.first],D[x]-1);
			}
		}
		x=0;
		FOR(j,N) {
			if(D[j]<0) break;
			x=max(x,D[j]);
		}
		if(j<N) continue;
		if(x>ma) {
			ma=x;
			FOR(j,N) R[j]=D[j];
		}
	}
	if(ma==-1) {
		cout<<"NO"<<endl;
	}
	else {
		cout<<"YES"<<endl;
		cout<<ma<<endl;
		FOR(j,N) cout<<R[j]<<" ";
		cout<<endl;
		
	}
	
}

まとめ

こういう問題は結構好き。