imported>jereneal20 at 04:07, 8 August 2013

2013-08-08T04:07:16Z

New page

= 사신도 =
* * [http://www.algospot.com/judge/problem/read/FOURGODS 사신도]
* A-B-C-D(-A) 와 같은 순서가 되도록 하는 것의 경우의 수 구하기
** 염주 수열은 같은 것으로 본다.
* 모든 A와 C에 대해서 한다.(n^2)
** B와 D의 후보를 찾아서 조건에 맞는지 확인한다.(A,C와 연결되어있는지) (n)
** 토탈 n^3
* 중복제거. A-B-C-D는 숫자로 주어지므로 우선순위를 정한다.(e.g. 작은 숫자 우선)
** A가 항상 가장 작은 숫자가 되도록 한다. B와 C의 크기는 바뀔 수 있는데, A-B-C-D와 A-C-B-D 둘 모두 다른 정답으로 보기 때문이다.
//
// fourgods.cpp
// codersHigh2013
//
// Created by Jereneal Kim on 13. 8. 6..
// Copyright (c) 2013년 Jereneal Kim. All rights reserved.
//

#include <iostream>
using namespace std;
int T,N,M;
int arr[501][501];
typedef struct Edge{
int u;
int v;
}Edge;
bool comp(Edge a,Edge b){
if(a.u!=b.u){
return a.u<b.u;
}else{
return a.v<b.v;
}
}

int main(int argc, const char * argv[])
{
freopen("/Users/jkim/Development/C&C++/codersHigh2013/codersHigh2013/input.txt","r",stdin);
int i,j,k,num;
scanf("%d",&T);
for(int iter=0;iter<T;iter++){
num=0;
for(i=0;i<500;i++){
for(j=0;j<500;j++){
arr[i][j] = 0;
}
}//initalize

scanf("%d %d",&N,&M);
for(i=0;i<M;i++){
int tmp1,tmp2;
scanf("%d %d",&tmp1,&tmp2);
arr[tmp2][tmp1] = 1;
arr[tmp1][tmp2] = 1;
}
// get A & C
for(i=1;i<=N;i++){
for(k=i+1;k<=N;k++){
int tmpNum=0;
for(j=i+1;j<=N;j++){
if(arr[i][j]&&arr[j][k]){
tmpNum++;
}
}
num+=tmpNum*(tmpNum-1)/2;
num%=20130728;
}
}

printf("%d\n",num);
}
return 0;
}

FOURGODS/김태진 - Revision history

imported>jereneal20 at 04:07, 8 August 2013