syhd142  
日历
<2024年5月>
日一二三四五六
2829301234
567891011
12131415161718
19202122232425
2627282930311
2345678
统计
  • 随笔 - 23
  • 文章 - 122
  • 评论 - 31
  • 引用 - 0

导航

常用链接

留言簿(2)

随笔档案(23)

文章分类(270)

文章档案(122)

我的豆瓣

搜索

  •  

最新评论

阅读排行榜

评论排行榜

 
HDU 3231 Box Relations
去年武汉现场赛的题目，当时想法都对了死活没写出来，惭愧，其实很简单，判环还想复杂了，其实构造好图后就一个拓扑排序就行了。
解法：处理好一维的，三维就一样，什么bellmanford完全不用，直接拓扑排序。
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define M 500000
#define N 2005

struct edge
{
    int ed;
    edge *next;
}e[M], *head[4][N];

int pos, in[4][N], queue[4][N], ans[4][N];

inline void Add(int type, int a, int b);

void Pre(int n)
{
    pos = 0;
    memset(head, 0, sizeof(head));
    memset(in, 0, sizeof(in));
    
    for(int i = 1; i <= n; i++)
    for(int j = 1; j <= 3; j++)
    {
        Add(j, i, i + n);
    }
}

inline void Add(int type, int a, int b)
{
    e[pos].ed = b, e[pos].next = head[type][a];
    head[type][a] = &e[pos++];
    in[type][b]++;
}

bool TopSort(int type, int n)
{
    int front, top;
    front = top = 0;
    for(int i = 1; i <= 2 * n; i++)
        if(!in[type][i])
        {
            queue[type][top++] = i;
        }
    while(front < top)
    {
        int u = queue[type][front++];
        for(edge *p = head[type][u]; p; p = p->next)
        {
            in[type][p->ed]--;
            if(!in[type][p->ed])
            {
                queue[type][top++] = p->ed;
            }
        }
    }
    return top == 2 * n;
}

void solve(int n)
{
    for(int i = 1; i <= 3; i++)
    {
        bool flag = TopSort(i, n);
        if(!flag)
        {
            puts("IMPOSSIBLE");
            return;
        }
    }
    puts("POSSIBLE");
    for(int i = 0; i < 2 * n; i++)
    for(int j = 1; j <= 3; j++)
        ans[j][queue[j][i]] = i;
        
    for(int i = 1; i <= n; i++)
        printf("%d %d %d %d %d %d\n", ans[1][i], ans[2][i], ans[3][i],
                                ans[1][i + n], ans[2][i + n], ans[3][i + n]);

}

int main()
{
    int n, r, a, b, cas = 0;
    char op[5];
    while(scanf("%d %d", &n, &r), n + r)
    {
        Pre(n);
        while(r--)
        {
            scanf("%s %d %d", &op, &a, &b);
            if(op[0] == 'I')
            {
                for(int i = 1; i <= 3; i++)
                {
                    Add(i, a, b + n);
                    Add(i, b, a + n);
                }
            }
            else if(op[0] == 'X') Add(1, a + n, b);
            else if(op[0] == 'Y') Add(2, a + n, b);
            else if(op[0] == 'Z') Add(3, a + n, b);
        }
        printf("Case %d: ", ++cas);
        solve(n);
        puts("");
    }
    return 0;
}
posted on 2010-05-22 23:57 Fucker 阅读(474) 评论(0)  编辑 收藏 引用 所属分类: ACM/ICPC 、图论

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


 
Copyright © Fucker Powered by: 博客园 模板提供：沪江博客