Codeforces Global Round 12 E問題 - Capitalism

Source

Codeforces Global Round 12 E問題 (2500pt)
Problem description

問題概要

省略

解法

省略

cLayversion 20201206-1)のコード

C++に変換後のコードはこちら

//no-unlocked
int N, M, X[4000], Y[4000], B[4000];
int mn[200], mx[200];
int res[200], opt, tmp;
graph g;
{
  rd(N,M,(X--,Y--,B)(M));
  g.setEdge(N,M,X,Y);
  if(g.bipartite()==0) wt("NO"), return 0;

  rep(i,M) (X[M+i], Y[M+i], B[M+i]) = (Y[i], X[i], -B[i]);
  M *= 2;

  opt = -int_inf;
  rep(r,N){
    rep(i,N) mn[i] = -int_inf, mx[i] = int_inf;
    mn[r] = mx[r] = 0;
    for(;;){
      int fg = 0;
      rep(i,M){
        if(mn[X[i]] == -int_inf) continue;
        if(B[i] == 0 && mn[Y[i]] < mn[X[i]] - 1) mn[Y[i]] = mn[X[i]] - 1, fg++;
        if(B[i] == 0 && mx[Y[i]] > mx[X[i]] + 1) mx[Y[i]] = mx[X[i]] + 1, fg++;
        if(B[i] != 0 && mn[Y[i]] < mn[X[i]] + B[i]) mn[Y[i]] = mn[X[i]] + B[i], fg++;
        if(B[i] != 0 && mx[Y[i]] > mx[X[i]] + B[i]) mx[Y[i]] = mx[X[i]] + B[i], fg++;
      }
      rep(i,N) if(mx[i] < mn[i] || mx[i] < 0) break_break_continue;
      if(!fg) break;
    }
    if(opt < max(mx(N))){
      opt = max(mx(N));
      rep(i,N) res[i] = mx[i];
    }
  }
  if(opt==-int_inf) wt("NO"), return 0;
  wt("YES");
  wt(opt);
  wt(res(N));
}

Current time: 2021年12月05日22時56分00秒
Last modified: 2020年12月11日22時53分00秒 (by laycrs)
Tags: Competitive_Programming_Incomplete Codeforces Codeforces_Global_Round_12
トップページに戻る

Logged in as: unknown user (not login)

ログイン: