【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;
}