結果

問題 No.519 アイドルユニット
コンテスト
ユーザー tnakao0123
提出日時 2017-06-01 20:17:24
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 2,958 bytes
コンパイル時間 838 ms
コンパイル使用メモリ 90,316 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-09-21 21:41:51
合計ジャッジ時間 1,890 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 27 WA * 7
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:97:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   97 |   scanf("%d", &n);
      |   ~~~~~^~~~~~~~~~
main.cpp:102:12: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  102 |       scanf("%d", &fs[i][j]);
      |       ~~~~~^~~~~~~~~~~~~~~~~

ソースコード

diff # 

/* -*- coding: utf-8 -*-
 *
 * 519.cc: No.519 アイドルユニット - yukicoder
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

const int MAX_N = 100;
const int INF = 1 << 30;

/* typedef */

typedef vector<int> vi;
typedef pair<int,int> pii;

/* global variables */

int fs[MAX_N][MAX_N];
vi nbrs[MAX_N];
int caps[MAX_N][MAX_N], costs[MAX_N][MAX_N], flows[MAX_N][MAX_N];

/* subroutines */

pii min_cost_flow(const int n, const vi nbrs[], int st, int gl) {
  // assume that caps and costs are pre-assigned
  memset(flows, 0, sizeof(flows));
  pii total; // (cost, flow)
  vi hs(n, 0);

  for (;;) {
    //printf("total=%d,%d\n", total.first, total.second);
    vi dists(n, INF); dists[st] = 0;
    vi prvs(n, -1);
    vi minfs(n, INF);

    for (int i = 0; i < n - 1; i++) {
      for (int ui = 0; ui < n; ui++) {
	int &ud = dists[ui];
	const vi &nbru = nbrs[ui];
	for (vi::const_iterator vit = nbru.begin(); vit != nbru.end(); vit++) {
	  const int &vi = *vit;
	  int vc = caps[ui][vi] - flows[ui][vi];
	  if (vc > 0) {
	    int vd = ud + costs[ui][vi] + hs[ui] - hs[vi];
	    if (dists[vi] > vd) {
	      dists[vi] = vd;
	      prvs[vi] = ui;
	      minfs[vi] = min(vc, minfs[ui]);
	    }
	  }
	}
      }
    }
    if (prvs[gl] < 0) break;

    int min_flow = minfs[gl];
    for (int v = gl; v != st;) {
      int u = prvs[v];
      total.first += min_flow * costs[u][v];
      flows[u][v] += min_flow;
      flows[v][u] -= min_flow;
      v = u;
    }

    total.second += min_flow;
    for (int i = 0; i < n; i++) hs[i] += dists[i];
  }

  return total;
}

/* main */

int main() {
  int n;
  scanf("%d", &n);

  int maxf = 0;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) {
      scanf("%d", &fs[i][j]);
      if (maxf < fs[i][j]) maxf = fs[i][j];
    }
  //printf("maxf=%d\n", maxf);

  int st = n * 2, gl = st + 1, gn = gl + 1;

  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      if (i != j && fs[i][j] >= 0) {
	int f = maxf - fs[i][j];
	nbrs[i].push_back(n + j);
	caps[i][n + j] = 1;
	costs[i][n + j] = f;
	nbrs[n + j].push_back(i);
	caps[n + j][i] = 0;
	costs[n + j][i] = -f;
      }

  for (int i = 0; i < n; i++) {
    nbrs[st].push_back(i);
    caps[st][i] = 1;
    costs[st][i] = 0;
    nbrs[i].push_back(st);
    caps[i][st] = 0;
    costs[i][st] = 0;
  }

  for (int i = 0; i < n; i++) {
    nbrs[n + i].push_back(gl);
    caps[n + i][gl] = 1;
    costs[n + i][gl] = 0;
    nbrs[gl].push_back(n + i);
    caps[gl][n + i] = 0;
    costs[gl][n + i] = 0;
  }

  pii t = min_cost_flow(gn, nbrs, st, gl);
  //printf("%d %d\n", t.first, t.second);

  printf("%d\n", (maxf * n - t.first) / 2);
  return 0;
}
0