zoj1346 (토폴로지 정렬을 만족시키는 서열 개수 구하기)

3658 단어 dp토폴로지 정렬

Comparing Your Heroes


시간 제한: Sec 메모리 제한: 128MB 전송: 9 해결: 6 [전송] [상태] [토론판] [명제: admin]
제목 설명
Nowadays many students wouldn't attend classes in university, instead, they stay in dormitory playing Electronic games on computers. One of the most popular games among the boys is KOF (the King Of Fighters), a kind of action game presented by SNK corporation. This series of games becomes so successful that SNK has even created comics and story for it. Although in the story IORI and KYO are the definitely two strongest heroes, it would not affect players' true affection of other characters. Actually, every player has his own favorite heroes. As a fanatical fan of the KOF game, you're going to help the other players to find out the ranking of their favorite heroes. Players would only provide information of comparisons between the heroes. This sometimes can lead to confusion: maybe not only one ranking satisfies the comparisons. So at first you'd like to find out the number of the rankings that satisfy a specific player's comparisons.
 
 
입력
The input consists of several test cases. Each test case begins with a positive integer N on a line, indicating the number of the comparisons. The following N lines are the comparisons between the heroes. Each one is a line containing 2 names of the heroes separated by a space, means the player prefer the first hero to the second. The name of the hero is a sequence of at most 10 upper case letters. No two comparisons would be same, and you can always assure one's favorite heroes would not exceed 16.
 
출력
For each test case, print out the number of the rankings that satisfy the comparisons on a single line. If no such ranking exists, just print out 0.
 
 

샘플 입력


샘플 데이터 복사
4
IORI KYO
MARY SHERMIE
KYO ANDY
SHERMIE ANDY
3
IORI KYO
KYO CLARK
CLARK IORI

샘플 출력
6
0

 
소스/분류
ZJU 2002 
 
제목 대의: 제목은 토폴로지 정렬의 서열을 만족시키는 개수를 구한다.
문제풀이 사고방식: 쓸 줄 모른다.보충 문제를 풀 때 비로소 배열 총수는 현재 입도가 0인 수를 제외한 나머지 수의 배열 총수와 같다는 것을 알게 되었다.
한 개만 있을 때 요구를 충족시키는 배열수는 1이다.그래서 우리는 거슬러 올라갈 때 답을 통계할 수 있다.
구체적인 과정: 연결, 각 점의 입도를 통계하고 상태가 압축된 후 dp수조를 초기화한다(한 점만 있을 때 답은 1).
그 다음에 현재 입도가 0인 점을 순서대로 열거한 다음에 현재 점을 제거하면 된다.
  
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define LL long long
#define sca(x) scanf("%d",&x)
#define lowb(x) (x&(-x))
#define pb(x) push_back(x)
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define per(i,j,k) for(int i=j;i>=k;i--)
#define pri(x) printf("%d
",x);
#define N 405
#define inf 0x3f3f3f3f
const LL mod=1e9+7;

mapmmp;
int g[20][20];
LL dp[1<<17];
int in[20];
int id;
LL dfs(LL now)
{
    if(dp[now]) return dp[now];
    dp[now]=0;
    for(int i=0;i>n)
    {
        id=0;
        string a,b;
        mmp.clear();
        memset(g,0,sizeof(g));
        memset(dp,0,sizeof(dp));
        memset(in,0,sizeof(in));
        rep(i,1,n)
        {
           cin>>a>>b;
           if(mmp.find(a)==mmp.end())
           {
               mmp[a]=id++;
           }
           if(mmp.find(b)==mmp.end())
           {
               mmp[b]=id++;
           }
           g[mmp[a]][mmp[b]]=1;
           in[mmp[b]]++;
        }
        for(int i=0;(1<

하마터면 기억할 뻔했다.php.어디
Vim에서paiza의 준비를 잘 하고 차근차근 열심히 하겠습니다.

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage