【1】PKU1094
思考难度不大，就是不断在有向图中加边，求加了几条边以后，图中出现一条连接N个点的简单路径（就是一条长度为(N-1)的链），或者图中出现环。判定连接N个点的简单路径的算法：拓扑排序，若每次队列中有且只有一个入度为0的点，则这样的路径存在，所排出的顺序就是结果。注意两点：
（1）如果在前面的若干条边加入后，已经找到了解，那么就输出解，结束（不管后面的边了，即使后面的边加入后形成环也无视），数据：
In:
4 4
A<B
B<C
C<D
D<A
0 0
Out:
Sorted sequence determined after 3 relations: ABCD.(在前3条边加入后已经找到了解，此时无视第4条边，直接结束)
（2）在拓扑排序中发现队列中入度为0的点超过1个（即路径不存在）时，不要直接退出，应该将排序过程进行完毕，因为可能图中已经形成环，此时直接输出有环的结果，数据：
In:
6 6
A<B
B<C
C<D
D<E
A<F
E<C
0 0
Out:
Inconsistency found after 6 relations.(在第6条边加入后，虽然拓扑排序中在A出队后队列中出现了BF两个点，但不能退出，因为此时图中已经出现了环C->D->E->C，需要输出有环的结果)
代码：
#include <iostream>
#include <stdio.h>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
const int MAXN = 26, MAXM = 1000;
struct edge {
int a, b, pre, next;
} ed[MAXM];
int n, m, e[MAXN], q[MAXN], a0[MAXM], b0[MAXM], res = 0;
void init_d()
{
re(i, n) ed[i].a = ed[i].pre = ed[i].next = i;
m = n;
}
void add_edge(int a, int b)
{
ed[m].a = a; ed[m].b = b; ed[m].pre = ed[a].pre; ed[m].next = a; ed[a].pre = m; ed[ed[m].pre].next = m++;
}
int solve()
{
re(i, n) e[i] = 0;
re(i, n) for (int p=ed[i].next; p != i; p=ed[p].next) e[ed[p].b]++;
int front = 0, rear = -1;
re(i, n) if (!e[i]) q[++rear] = i;
int i, j;
bool ff = 1;
while (front < n) {
if (front < rear) ff = 0;
if (front > rear) return -1;
i = q[front++];
for (int p=ed[i].next; p != i; p=ed[p].next) {
j = ed[p].b; e[j]--;
if (!e[j]) q[++rear] = j;
}
}
return ff;
}
int main()
{
int m0, x;
char ch1, ch2, ch;
while (1) {
scanf("%d%d", &n, &m0);
if (!n) break; ch = getchar();
init_d();
re(i, m0) {
scanf("%c%*c%c", &ch1, &ch2); ch = getchar();
a0[i] = ch1 - 65; b0[i] = ch2 - 65;
}
res = 0;
re(i, m0) {
add_edge(a0[i], b0[i]);
x = solve();
if (x) {res = x * (i + 1); break;}
}
if (res > 0) {
printf("Sorted sequence determined after %d relations: ", res);
re(i, n) putchar(q[i] + 65); puts(".");
} else if (res < 0)
printf("Inconsistency found after %d relations.\n", -res);
else puts("Sorted sequence cannot be determined.");
}
return 0;
}
【2】PKU1112：
本题极其猥琐，先求二分图强连通分支再DP，DP时还因为会涉及负数下标而被迫改用中点型数组，最可怕的是范围问题（可能会超范围），无语了……真痛苦啊……（本沙茶一开始老是查不出来哪里疵了，搞了个手打的SJ……）
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re1(i, n) for (int i=1; i<=n; i++)
#define re2(i, l, r) for (int i=l; i<r; i++)
#define re3(i, l, r) for (int i=l; i<=r; i++)
#define rre1(i, n) for (int i=n; i>0; i--)
const int MAXN = 101, MAXM = 15500;
struct edge {
int a, b, pre, next;
} ed[MAXM + MAXM];
int n, m, p = 0, st[MAXN], s1[MAXN], s2[MAXN], ls1[MAXN][MAXN], ls2[MAXN][MAXN], q[MAXN], reslen1 = 0, reslen2 = 0, res1[MAXN], res2[MAXN];
bool f[MAXN][MAXN + MAXN + 1];
void init_d()
{
re(i, n) ed[i].a = ed[i].pre = ed[i].next = i;
if (n % 2) m = n + 1; else m = n;
}
void add_edge(int a, int b)
{
ed[m].a = a; ed[m].b = b; ed[m].pre = ed[a].pre; ed[m].next = a; ed[a].pre = m; ed[ed[m].pre].next = m++;
ed[m].a = b; ed[m].b = a; ed[m].pre = ed[b].pre; ed[m].next = b; ed[b].pre = m; ed[ed[m].pre].next = m++;
}
void init()
{
scanf("%d", &n); init_d();
int x;
re(i, n)
while (1) {
scanf("%d", &x);
if (!x) break;
f[i][--x] = 1;
}
re(i, n-1) re2(j, i + 1, n) if (!f[i][j] || !f[j][i]) add_edge(i, j);
}
bool bfs(int x)
{
s1[++p] = 1; s2[p] = 0; q[0] = ls1[p][0] = x; st[x] = 1;
int i, j, v;
for (int front=0, rear=0; front<=rear; front++) {
i = q[front]; v = st[i];
for (int p0=ed[i].next; p0 != i; p0=ed[p0].next) {
j = ed[p0].b;
if (st[j] == v) return 0;
if (!st[j]) {
st[j] = 3 - v; q[++rear] = j;
if (st[j] == 1) ls1[p][s1[p]++] = j; else ls2[p][s2[p]++] = j;
}
}
}
return 1;
}
int cmp(const void *s1, const void *s2)
{
return *(int *)s1 - *(int *)s2;
}
void solve()
{
re(i, n) if (!st[i] && !bfs(i)) {reslen1 = -1; return;}
f[0][MAXN] = 1; re1(i, n) f[0][MAXN + i] = f[0][MAXN - i] = 0;
int x;
re1(i, p) {
x = s1[i] - s2[i];
re3(j, MAXN - n, MAXN + n) f[i][j] = (j + x <= MAXN + n && f[i - 1][j + x]) || (j - x >= MAXN - n && f[i - 1][j - x]);
}
int j;
re3(i, 0, n) {
if (f[p][MAXN + i]) {j = MAXN + i; break;}
if (f[p][MAXN - i]) {j = MAXN - i; break;}
}
rre1(i, p) {
x = s1[i] - s2[i];
if (j + x <= MAXN + n && f[i - 1][j + x]) {
re(k, s1[i]) res1[reslen1++] = ls1[i][k];
re(k, s2[i]) res2[reslen2++] = ls2[i][k];
j += x;
} else {
re(k, s2[i]) res1[reslen1++] = ls2[i][k];
re(k, s1[i]) res2[reslen2++] = ls1[i][k];
j -= x;
}
}
}
void pri()
{
if (reslen1 == -1) puts("No solution"); else {
printf("%d", reslen1); re(i, reslen1) printf(" %d", ++res1[i]); puts("");
printf("%d", reslen2); re(i, reslen2) printf(" %d", ++res2[i]); puts("");
}
}
int main()
{
init();
solve();
pri();
return 0;
}
【3】PKU1135：
本题的意思极难理解。可以将其类比为线段燃烧：有N个端点，M条线段连接它们，当某个端点被点燃后，与其关联的所有线段也将被同时点燃，当某条线段烧光后，其相关联的另一个端点将被它点燃（当该端点未烧掉时）。线段燃烧所需的时间与线段长度成正比，点燃烧的时间很短，忽略不计。在此过程中还有可能发生下面的事情：某条线段燃烧过程中，其另一端点也被点燃，此时该线段会在两头同时开始烧……现在，一开始点燃编号为1的点，求所有点和线段烧完的时间，以及最后烧完的线段（或点）。
分析：首先很容易发现一个事实，就是一个点开始烧的时间就是图中从1到这个点的最短路长度，这样，求出1到所有点的最短路长度，即得到了最后烧完的点的编号（最短路最长的点）。然后考虑线段，可以发现，图中的线段分为两类：设该线段两端点的最短路长度分别为d0和d1(d0<=d1)，该线段的长度（烧完的时间）为len，则若d0+len=d1，则该线段不会出现两头同时在烧的情况（因为该线段是全部烧完后再点燃另一端），否则若d0+len>d1，则该线段会出现两头同时在烧的情况，此时，该线段全部烧完的时间为d0+(d0+len-d1)/2。取最大值即可。
代码：
#include <iostream>
#include <stdio.h>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re2(i, l, r) for (int i=l; i<r; i++)
const int MAXN = 500, MAXM = 150000, INF = ~0U >> 2;
const double zero = 1e-7;
struct edge {
int a, b, len, pre, next;
} ed[MAXM + MAXM];
int n, m, dist[MAXN], q[MAXN + 1], res_x, res_y;
double res;
bool vst[MAXN];
void init_d()
{
re(i, n) ed[i].a = ed[i].pre = ed[i].next = i;
if (n % 2) m = n + 1; else m = n;
}
void add_edge(int a, int b, int len)
{
ed[m].a = a; ed[m].b = b; ed[m].len = len; ed[m].pre = ed[a].pre; ed[m].next = a; ed[a].pre = m; ed[ed[m].pre].next = m++;
ed[m].a = b; ed[m].b = a; ed[m].len = len; ed[m].pre = ed[b].pre; ed[m].next = b; ed[b].pre = m; ed[ed[m].pre].next = m++;
}
void solve()
{
dist[0] = 0; vst[0] = 1; re2(i, 1, n) {dist[i] = INF; vst[i] = 0;} q[0] = 0;
int i, j, d0, d1, l0;
for (int front=0, rear=0; !(front == rear + 1 || !front && rear == n); front<n ? front++ : front=0) {
i = q[front]; d0 = dist[i];
for (int p=ed[i].next; p != i; p=ed[p].next) {
j = ed[p].b; d1 = d0 + ed[p].len;
if (d1 < dist[j]) {
dist[j] = d1;
if (!vst[j]) {vst[j] = 1; q[rear<n ? ++rear : rear=0] = j;}
}
}
vst[i] = 0;
}
res = -1; re(i, n) if (dist[i] - zero > res) {res = dist[i]; res_x = res_y = i;}
double z;
re(i, n) {
d0 = dist[i];
for (int p=ed[i].next; p != i; p=ed[p].next) {
j = ed[p].b; if (j <= i) continue;
d1 = dist[j]; l0 = ed[p].len;
if (d0 + l0 == d1 || d1 + l0 == d0) continue;
z = d0 + (d1 + l0 - d0) / 2.0;
if (z - zero> res) {res = z; res_x = i; res_y = j;}
}
}
}
int main()
{
int No = 0, m0, a0, b0, l;
while (1) {
scanf("%d%d", &n, &m0);
if (!n) break;
No++; init_d();
re(i, m0) {
scanf("%d%d%d", &a0, &b0, &l);
add_edge(--a0, --b0, l);
}
solve();
if (No > 1) puts("");
printf("System #%d\n", No);
if (res_x == res_y)
printf("The last domino falls after %.1f seconds, at key domino %d.\n", res, ++res_x);
else
printf("The last domino falls after %.1f seconds, between key dominoes %d and %d.\n", res, ++res_x, ++res_y);
}
return 0;
}