URAL 1957 Wrong Answer 暴力

Wrong Answer

思路：

1.先枚举4的全排列，即球赛的所有可能结果，一共4!=24种情况

2.对于每种情况，DFS 未确定的比赛 的结果，判断这种情况是否可达。

剪枝：

1.对于每种全排列，只需要找到一种满足这个全排列的情况即可，如果有一种情况满足，则不必再枚举其他可能。

2.因为在每种情况下，球队之间的排名已经确定了，所以在DFS的过程中，凡是不满足此排名的情况统统可以剪掉。

这样就可以少很多情况，即使在n=0的情况下也跑出了不错的效率，但是它Wrong Answer on test 17了。。。

求指点T^T

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>

using namespace std;

const int MAXN = 10010;
const int permuta[30] = { 1234, 1243, 1324, 1342, 1423, 1432,
                          2134, 2143, 2314, 2341, 2413, 2431,
                          3124, 3142, 3214, 3241, 3412, 3421,
                          4123, 4132, 4213, 4231, 4312, 4321
                        };


struct Team
{
    int id;
    int qiu;
    int point;
};

bool vis[30];
int game[5][5], gori[5][5];   // 0=i输j 1=i平j 3=i赢j
Team tm[5], ori[5];
int N, cnt;

void show()
{
    for ( int i = 1; i <= 4; ++i )
        printf( "id=%d point=%d qiu=%d
", i, tm[i].point, tm[i].qiu );
    puts("");
    return;
}

void chuli( int i, int j, int c )   //c为队伍i的净赢球量
{
    tm[i].point += game[i][j];
    tm[j].point += game[j][i];
    tm[i].qiu += c;
    tm[j].qiu -= c;
    return;
}

void init()
{
    memset( vis, false, sizeof(vis) );
    memset( game, -1, sizeof( game ) );
    memset( tm, 0, sizeof(tm) );
    for ( int i = 0; i < N; ++i )
    {
        int a, b, c, d;
        scanf( "%d%d%d%d", &a, &b, &c, &d );
        if ( c == d )
        {
            game[a][b] = game[b][a] = 1;
        }
        else if ( c > d )
        {
            game[a][b] = 3;
            game[b][a] = 0;
        }
        else
        {
            game[a][b] = 0;
            game[b][a] = 3;
        }
        chuli( a, b, c - d );
    }
    return;
}

bool DFS( int *tmp, int cur )
{
    if ( cur <= 0 )
    {
        /*
        for ( int i = 1; i <= 4; ++i )
            printf( "id=%d point=%d qiu=%d
", tmp[i], tm[ tmp[i] ].point, tm[ tmp[i] ].qiu );
        puts("");
*/
        for ( int i = 1; i < 4; ++i )
        {
            int u = tmp[i];
            int v = tmp[i + 1];
            if ( tm[u].point < tm[v].point || ( tm[u].point == tm[v].point && tm[u].qiu < tm[v].qiu ) )
                return false;
        }
        return true;
    }

    int j = tmp[cur];
    bool ok = true;
    for ( int i = 1; i <= 4; ++i )
    {
        if ( i == j ) continue;
        if ( game[j][i] == -1 )
        {
            ok = false;
            for ( int k = -10; k <= 10; ++k )   //枚举净赢球数
            {
                if ( k < 0 )
                {
                    game[j][i] = 0;
                    game[i][j] = 3;
                }
                else if ( k == 0 )
                {
                    game[j][i] = 1;
                    game[i][j] = 1;
                }
                else
                {
                    game[j][i] = 3;
                    game[i][j] = 0;
                }
                chuli( j, i, k );

                //puts("*************");
                //show();

                if ( DFS( tmp, cur ) ) return true;

                tm[j].point -= game[j][i];
                tm[i].point -= game[i][j];
                game[j][i] = -1;
                game[i][j] = -1;
                tm[i].qiu += k;
                tm[j].qiu -= k;

                //show();
                //puts("==============");

            }
        }
    }

    if ( ok )
    {
        if ( cur != 4 )
        {
            int u = tmp[cur];
            int v = tmp[cur + 1];
            //printf("%d %d %d %d
",tm[u].point, tm[v].point, tm[u].qiu, tm[v].qiu );
            if ( tm[u].point < tm[v].point || ( tm[u].point == tm[v].point && tm[u].qiu < tm[v].qiu ) )
                return false;
            else
            {
                if ( DFS( tmp, cur - 1 ) ) return true;
            }
        }
        else
        {
            if ( DFS( tmp, cur - 1 ) ) return true;
        }
    }
    return false;
}

void solved()
{
    for ( int i = 1; i <= 4; ++i )
    {
        ori[i] = tm[i];
        for ( int j = 1; j <= 4; ++j )
            gori[i][j] = game[i][j];
    }

    int temp[5];
    for ( int i = 0; i < 24; ++i )
    {
        int nn = permuta[i];
        for ( int j = 4; j > 0; --j )
        {
            temp[j] = nn % 10;
            nn /= 10;
        }
/*
        for ( int j = 1; j <= 4; ++j )
            printf( "%d ", temp[j] );
        puts("");
*/
        for ( int j = 1; j <= 4; ++j )
        {
            tm[j] = ori[j];
            for ( int k = 1; k <= 4; ++k )
                game[j][k] = gori[j][k];
        }

        if ( DFS( temp, 4 ) )
        {
            ++cnt;
            vis[i] = true;
        }

  //      puts("-------");
    }
}

int main()
{
    //freopen("s.out", "w", stdout );
    while ( ~scanf( "%d", &N ) )
    {
        init();

        cnt = 0;
        solved();

        int ans[4];
        printf( "%d
", cnt );
        for ( int i = 0; i < 24; ++i )
            if ( vis[i] )
            {
                int nn = permuta[i];
                for ( int j = 3; j >= 0; --j )
                {
                    ans[j] = nn % 10;
                    nn /= 10;
                }
                for ( int j = 0; j < 4; ++j )
                {
                    if ( j ) putchar(' ');
                    printf( "%d", ans[j] );
                }
                puts("");
            }
    }
    return 0;
}