最近捉的一些图论题

Posted on 2011-05-22 11:09 Mato_No1 阅读(403) 评论(0)  编辑 收藏 引用 所属分类: 图算法
【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 + 1else 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 = -1return;}
    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 + 1else 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<? 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<? ++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;
}

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理