File: Timus 1035. Cross-stitch
Author: xiaotian @ hnu
Created on 2010年9月30日, 上午9:06
题解：把网格交叉点抽象成顶点，正面线抽象为正边，反面的抽象为反边。
求联通块，分别求出每个联通块的针数，最后相加即为答案。
1 #include<iostream>
2 #include<stdio.h>
3 #include<string.h>
4 #include<queue>
5 using namespace std;
6 int p[40500], a[40500][2], sum[40500], n, m;
7
8 int find(int x) {
9 if (p[x] != x)p[x] = find(p[x]);
10 return p[x];
11 }
12
13 int judge(int x, int y) {
14 return find(x) == find(y);
15 }
16
17 void make(int side) {
18 int ul, ur, dl, dr;
19 char c;
20 for (int i = 0; i < n; i++)
21 {
22 for (int j = 0; j <= m; j++) {
23 scanf("%c", &c);
24 if (j == m) break;
25 ul = i * (m + 1) + j;
26 ur = ul + 1;
27 dl = (i + 1)*(m + 1) + j;
28 dr = dl + 1;
29 if ((c == 'X') || (c == '\\')) {
30 a[ul][side]++;
31 a[dr][side]++;
32 if (!judge(ul, dr))p[p[ul]] = p[dr];
33 }
34 if ((c == 'X') || (c == '/')) {
35 a[ur][side]++;
36 a[dl][side]++;
37 if (!judge(ur, dl))p[p[ur]] = p[dl];
38 }
39 }
40 }
41 }
42
43 int main() {
44 while (scanf("%d%d\n", &n, &m) != EOF) {
45 int i, ans = 0;
46 for (i = 0; i < (m + 1)*(n + 1); i++) p[i] = i;
47 make(0);
48 make(1);
49 for (i = 0; i < (m + 1)*(n + 1); i++)
50 if (a[i][0] || a[i][1]) sum[find(i)] += abs(a[i][0] - a[i][1]);
51 for (i = 0; i < (m + 1)*(n + 1); i++)
52 if ((a[i][0] || a[i][1]) && (p[i] == i)) ans += sum[i] ? sum[i] / 2 : 1;
53 printf("%d\n", ans);
54 return 0;
55 }
56 }
无聊的写了一个水题，发现 Timus 的题目很好玩啊
判断一个图是不是二分图。bfs 染色即可。
1 #include<stdio.h>
2 #include<iostream>
3 #include<string.h>
4 #include<queue>
5 #include<vector>
6 #define N 108
7 #define inf 0x3ffffff
8 using namespace std;
9 vector<int>g[N];
10 int clor[N];
11 int n;
12 int bfs(int s)
13 {
14 queue<int>q;
15 q.push(s);
16 clor[s]=0;
17 while(!q.empty())
18 {
19 int p=q.front(); q.pop();
20 for(int i=0;i<g[p].size();i++)
21 {
22 if(clor[g[p][i]]==-1)
23 {
24 clor[g[p][i]]=1-clor[p];
25 q.push(g[p][i]);
26 }
27 else if(clor[g[p][i]]!=1-clor[p]) return 0;
28 }
29 }
30 return 1;
31 }
32
33 int main()
34 {
35 while(scanf("%d",&n)!=EOF)
36 {
37 for(int i=0;i<=n;i++) g[i].clear();
38 for(int i=0;i<n;i++)
39 {
40 int k;
41 while(scanf("%d",&k),k)
42 {
43 g[i].push_back(k-1);
44 g[k-1].push_back(i);
45 }
46 }
47 memset(clor,-1,sizeof(clor));
48 int i;
49 for(i=0;i<n;i++)
50 if(clor[i]==-1) if(bfs(i)==0) break;
51 if(i<n) puts("-1");
52 else for(int i=0;i<n;i++)printf(i==n-1?"%d\n":"%d",clor[i]);
53 }
54 return 0;
55 }
摘要: 第35届ACM/ICPC亚洲区预选赛哈尔滨赛区的 1004 题，Power Stations。Dancing Links，相对于其他的 DLX 来说，这道题目应该还算简单的。
Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/--> 1...
阅读全文
1 /*
2 * File: Timus 1033. Labyrinth
3 * Author: xiaotian @ hnu
4 * Created on 2010年9月29日, 上午10:30
5 * 题解：bfs数墙面个数，最后乘以 9 。
6 */
7
8 #include<stdio.h>
9 #include<iostream>
10 #include<string.h>
11 #include<queue>
12 #include<set>
13 #include<math.h>
14 using namespace std;
15 #define N 40
16 #define inf 0x7ffffff
17 const int dx[4] = {0, 1, 0, -1};
18 const int dy[4] = {1, 0, -1, 0};
19 char map[N][N];
20 int vis[N][N][4];
21 int num[N][N];
22 int n;
23
24 struct point {
25 int x, y;
26 point(int xx = 0, int yy = 0) : x(xx), y(yy) {
27 }
28 };
29
30 inline int ok(int x, int y) {
31 return x > 0 && x <= n && y > 0 && y <= n;
32 }
33
34 int bfs(point s) {
35 int ans = 0;
36 queue<point>q;
37 q.push(s);
38 num[s.x][s.y] = 1;
39 while (!q.empty()) {
40 point p = q.front();
41 q.pop();
42 for (int i = 0; i < 4; i++) {
43 int x = p.x + dx[i], y = p.y + dy[i];
44 if ((x == 0 || x == n + 1 || y == 0 || y == n + 1 || map[x][y] == '#') && vis[p.x][p.y][i] == 0 && vis[x][y][(i + 2) % 4] == 0) {
45 ans++;
46 vis[p.x][p.y][i] = 1;
47 vis[x][y][(i + 2) % 4] = 1;
48 }
49 if (ok(x, y) && map[x][y] == '.' && num[x][y] == 0) {
50 num[x][y] = 1;
51 q.push(point(x, y));
52 }
53 }
54 }
55 return ans;
56 }
57
58 int main() {
59 while (scanf("%d\n", &n) != EOF) {
60 for (int i = 1; i <= n; i++)
61 gets(map[i] + 1);
62 for (int i = 0; i <= n + 2; i++)
63 for (int j = 0; j <= n + 2; j++) {
64 num[i][j] = 0;
65 for (int k = 0; k < 4; k++)
66 vis[i][j][k] = 0;
67 }
68 int ans=bfs(point(1,1))+bfs(point(n,n));
69 printf("%d\n", ans*9-36);
70 }
71 return 0;
72 }
很裸的拓扑排序
1 /*
2 * File: 1022. Genealogical tree
3 * Author: xiaotian @ hnu
4 * Created on 2010年9月28日, 下午 9:26
5 * 解题：很裸的拓扑排序
6 */
7
8 #include<stdio.h>
9 #include<iostream>
10 #include<string.h>
11 #define N 108
12 using namespace std;
13 bool t[N][N];
14 int d[N];
15 int n;
16 void init()
17 {
18 memset(d,0,sizeof(d));
19 memset(t,0,sizeof(t));
20 for(int i=1;i<=n;i++)
21 for(int a;scanf("%d",&a) && (a>0);d[a]++)
22 t[i][a]=1;
23 }
24 void calc()
25 {
26 for(int dex=1;dex<=n;dex++)
27 {
28 int k=1;
29 for(;(k<=n)&&(d[k]>0);k++);
30 d[k]=1<<30-1;
31 for(int i=1;i<=n;i++) if(t[k][i]) d[i]--;
32 printf(dex==n?"%d\n":"%d ",k);
33 }
34 }
35 int main()
36 {
37 while(scanf("%d",&n)!=EOF)
38 {
39 init();
40 calc();
41 }
42 return 0;
43 }
摘要: bfs，很基础的。可以看作在一个图上跑最短路，关健是建图，本人愚拙，手打整个图。
Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/--> 1 /* 2 * File:&n...
阅读全文