Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

SRM477 DIV1 MEDIUM - PythTriplets (この記事を編集する[管理者用])

Source

TopCoder SRM477 DIV1 MEDIUM (500pt)
Problem Statement
SRM477 DIV1 自分の参加記録

問題概要

200個以下の整数が与えられる.
その中から,2つの整数を選んで,互いに素で,2乗の和が平方数になっているなら取り除ける.
最大で何回取り除けるかを求める問題.

解法

最大マッチングだけど,グラフは整数の偶奇で分けると2部グラフになる.
偶数同士は互いに素じゃない,奇数同士はピタゴラス数にならない.
なので,最大流.

C++によるスパゲッティなソースコード
// #includeとusing namespace std;は略

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define ll long long

#define INT_INF 1000000000

#define INT_LIST_MAX_FLOW_NODE 602
int intLmfEdge[INT_LIST_MAX_FLOW_NODE][INT_LIST_MAX_FLOW_NODE];
int intLmfFlow[INT_LIST_MAX_FLOW_NODE][INT_LIST_MAX_FLOW_NODE];
int intLmfInv[INT_LIST_MAX_FLOW_NODE][INT_LIST_MAX_FLOW_NODE];
int intLmfEdgeSize[INT_LIST_MAX_FLOW_NODE],intLmfEdgeMemory[INT_LIST_MAX_FLOW_NODE];
int intLmfLevel[INT_LIST_MAX_FLOW_NODE];
int intLmfQueue[INT_LIST_MAX_FLOW_NODE];

void intListMaxFlowLevelize(int n,int st,int ed){
  int i,j,k,t;
  int q_st,q_end;
  rep(i,n) intLmfLevel[i]=-1; intLmfLevel[st]=0; q_st=0; q_end=1; intLmfQueue[0]=st;
  while(q_st!=q_end){
    i=intLmfQueue[q_st++]; t=intLmfLevel[i]+1;
    rep(j,intLmfEdgeSize[i]) if(intLmfFlow[i][j]){
      k=intLmfEdge[i][j]; if(intLmfLevel[k]!=-1) continue;
      intLmfLevel[k]=t; intLmfQueue[q_end++]=k; if(k==ed) return;
    }
  }
}

int intListMaxFlowFlow(int i,int ed,int lim){
  int j,k,ret=0,t,s,ji;
  if(i==ed) return lim;
  rep(j,intLmfEdgeSize[i]) if(intLmfFlow[i][j]){
    k=intLmfEdge[i][j]; if(intLmfLevel[k]<=intLmfLevel[i]) continue;
    s=lim; if(s>intLmfFlow[i][j]) s=intLmfFlow[i][j];
    t=intListMaxFlowFlow(k,ed,s); if(!t) continue;
    ret+=t; lim-=t; ji=intLmfInv[i][j];
    intLmfFlow[i][j]-=t; intLmfFlow[k][ji]+=t;
    if(!lim) break;
  }
  if(lim) intLmfLevel[i]=-1;
  return ret;
}

int intListMaxFlow(int n,int st,int ed){
  int ret=0;
  for(;;){
    intListMaxFlowLevelize(n,st,ed); if(intLmfLevel[ed]==-1) break;
    ret += intListMaxFlowFlow(st,ed,INT_INF);
  }
  return ret;
}

void intListMaxFlowEdgeInit(){
  int i;
  rep(i,INT_LIST_MAX_FLOW_NODE) intLmfEdgeSize[i]=0;
}

void intListMaxFlowEdgeInitAdv(int n){
  int i;
  rep(i,n) intLmfEdgeSize[i]=0;
}

/* 制約: n1!=n2 */
void intListMaxFlowEdgeAdd(int n1,int n2,int f1,int f2){
  int s1=intLmfEdgeSize[n1]++, s2=intLmfEdgeSize[n2]++;
  intLmfEdge[n1][s1]=n2; intLmfEdge[n2][s2]=n1;
  intLmfFlow[n1][s1]=f1; intLmfFlow[n2][s2]=f2;
  intLmfInv[n1][s1]=s2;  intLmfInv[n2][s2]=s1;
}

int read_int_from_char(const char in[],int l,int ret[]){
  int i,n,fg,mfg;
  if(l<0) {for(i=0;;i++) if(in[i]<' ') break; l=i;}
  n=0; fg=0; mfg=0; ret[0]=0;
  rep(i,l+1){
    if(in[i]=='-'){mfg=1; continue;}
    if(isdigit(in[i])){ret[n]=ret[n]*10+in[i]-'0'; fg=1; continue;}
    if(!fg) continue;
    fg=0; if(mfg){ret[n]=-ret[n]; mfg=0;}
    ret[++n]=0;
  }
  return n;
}


int edge[210][210], deg[210];

int GCD(int a,int b){int r; while(a){r=b; b=a; a=r%a;} return b;}
int is_sq(ll a,ll b){
  ll x = a*a + b*b, y, i;
  y = (ll)sqrt(x)-5;
  if(y<0) y=1;
  REP(i,y,y+12) if(i*i==x) return 1;
  return 0;
}

class PythTriplets {
public:
int findMax(vector <string> stick_s) {
  int i,j,k;
  int res=0;
  int n, in[300];
  int in1[300], in2[300], n1, n2;
  int node, st, ed;
  string stick;

  rep(i,stick_s.size()) stick += stick_s[i];
  n = read_int_from_char(stick.c_str(),-1,in);

  n1 = n2 = 0;
  rep(i,n){
    if(in[i]%2) in1[n1++]=in[i];
    else        in2[n2++]=in[i];
  }

  node = n1 + n2; st = node++; ed = node++;
  intListMaxFlowEdgeInitAdv(node);

  rep(i,n1) rep(j,n2) if(GCD(in1[i],in2[j])==1) if(is_sq(in1[i],in2[j]))
    intListMaxFlowEdgeAdd(i,n1+j,1,0);
  rep(i,n1) intListMaxFlowEdgeAdd(st,i,1,0);
  rep(i,n2) intListMaxFlowEdgeAdd(n1+i,ed,1,0);

  res = intListMaxFlow(node,st,ed);

  return res;
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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