Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2449-b23fc3f6
この記事にトラックバックする(FC2ブログユーザー)

ARC 009 D - 覚醒ノ高橋君 (この記事を編集する[管理者用])

Source

AtCoder Regular Contest #009
問題文

問題概要

ノード数T,枝数Mの無向グラフが与えられる.
同じノード間に枝はたかだか1本で,枝には,その枝を壊すコスト(1以上77以下)が付けられている.
ノードはA個 (77以下) の集合にわかれていて,枝は同じ集合に属すノード間にしかない.
各集合に属すノードの数は7以下.
k個の集合に属すノードの数をS[k]とすると,S[k] * (k-1)の和がA-1になっている.(解法1行目参照)
全域木にする方法が幾つか考えられるが,それをコスト順にソートして,コストが小さい方からk番目 (7777777以下) のもののコストを求める問題.
k通りも存在しないならそれを指摘する.

解法

結局は,それぞれの集合に対して,全域木にすれば,全体で全域木になるようになっている.
それぞれの集合に対して全域木を列挙してあげて,使う枝の合計コストcでできる全域木の数をカウントしておく.
(使わない枝のコストは大きくなるので,使う枝のコストを求めて,最後に全体の枝のコストから引く)
後は,DPで,全体のコストcでできる全体の全域木の数を求める.

Cによるスパゲッティなソースコード
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define ll long long

int node;
int edge[100][100], cost[100][100], es[100];
int cnt[10000];

void solve(int now[], int a, int b, int co){
  int i, j, k;
  int c1, c2;
  int send[10];

  REP(i,1,node) if(now[i] != now[i-1]) break;
  if(i==node){
    cnt[co]++;
    return;
  }

  if(a==node) return;
  if(b==es[a]){ solve(now, a+1, 0, co); return; }

  solve(now, a, b+1, co);

  c1 = a; c2 = edge[a][b];
  if(now[c1]==now[c2]) return;
  c1 = now[c1];
  c2 = now[c2];
  
  rep(i,node) send[i] = now[i];
  rep(i,node) if(send[i]==c2) send[i] = c1;

  solve(send, a, b+1, co + cost[a][b]);
}

int edge_a[500000], edge_b[500000], edge_c[500000];
int num[100][1000];
ll dp[100000], next[100000], sum;

int main(){
  int A, T, K, M;
  int N[100], C[100][1000];

  int i, j, k;
  int a, b;
  int now[1000], cnv[1000];

  scanf("%d%d%d",&A,&T,&K);
  rep(i,A){
    scanf("%d",N+i);
    rep(j,N[i]) scanf("%d",C[i]+j);
  }

  scanf("%d",&M);
  rep(i,M) scanf("%d%d%d",edge_a+i,edge_b+i,edge_c+i);
  rep(i,A) rep(j,1000) num[i][j] = 0;

  rep(i,A){
    rep(j,1000) cnt[j] = 0;
    node = N[i];

    rep(j,T+1) cnv[j] = -1;
    rep(j,node) cnv[C[i][j]] = j;

    rep(j,node) now[j] = j, es[j] = 0;
    rep(j,M) if(cnv[edge_a[j]] >= 0 && cnv[edge_b[j]] >= 0){
      a = cnv[edge_a[j]];
      b = cnv[edge_b[j]];
      if(a > b) k = a, a = b, b = k;
      edge[a][es[a]] = b; cost[a][es[a]] = edge_c[j];
      es[a]++;
    }
    solve(now, 0, 0, 0);

    rep(j,1000) num[i][j] = cnt[j];

/*    printf("Town %d\n",A);
    rep(j,1000) if(num[i][j]) printf("cost %d num %d\n",j,cnt[j]);*/
  }

  rep(i,100000) dp[i] = 0;
  dp[0] = 1;

  rep(k,A){
    rep(i,100000) next[i] = 0;
    rep(i,1000) if(num[k][i]){
      rep(j,90000) if(dp[j]){
        next[i+j] += dp[j] * num[k][i];
        if(next[i+j] > K+1) next[i+j] = K+1;
      }
    }
    rep(i,100000) dp[i] = next[i];
  }

  sum = 0;
  rep(i,M) sum += edge_c[i];

  K--;
  for(i=99999;i>=0;i--){
    K -= dp[i];
    if(K < 0){ printf("%lld\n",sum - i); break; }
  }
  if(i<0) puts("-1");

  return 0;
}

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2449-b23fc3f6
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。