|
日歷
| | 日 | 一 | 二 | 三 | 四 | 五 | 六 |
|---|
| 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 | 29 | 30 | | 31 | 1 | 2 | 3 | 4 | 5 | 6 |
|
統計
- 隨筆 - 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;
}
|