日历
| 日 | 一 | 二 | 三 | 四 | 五 | 六 |
---|
26 | 27 | 28 | 29 | 30 | 31 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|
统计
- 随笔 - 23
- 文章 - 122
- 评论 - 31
- 引用 - 0
导航
常用链接
留言簿(2)
随笔档案(23)
文章分类(270)
文章档案(122)
我的豆瓣
搜索
最新评论

阅读排行榜
评论排行榜
|
去年武汉现场赛的题目,当时想法都对了死活没写出来,惭愧,其实很简单,判环还想复杂了,其实构造好图后就一个拓扑排序就行了。 解法:处理好一维的,三维就一样,什么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;
}

|