[ACM] POJ 1161 解题报告, 图论, 几何

好繁的一道题.. 看走眼了 1061才是数论题..才发现 思路:

区域看作一个Vertex, 对每个区域BFS求出能到达所有club的和最小值. 复杂度N2
Edge的构造:  一个region周围的点集按顺时针是 {p1, p2, p3 .. pk} 那么 (p1, p2) (p2, p3) … (p(k-1), pk) (pk, p1) 就是它的所有border, 其中任何一条边 (p[j], p[(j+1)%n]) 与也只与另外一个region’ 共享,  而region’ 做取边操作的时候, 这条共享边是颠倒的, 即 (p[(j+1)%n], p[j]) , 所以构造一个二维数组p[][], 上下三角形是对称的, 一对对称的元素就代表了相连的两个区域
club就存在所有靠着它的region内, 在这些region里面此club的步数都是0

细节:

以后这种繁题把变量名起的明白一点.. 多写点注释,  不然容易糊涂, 不太好写函数(其实可以.. 懒)

110行, 跑47ms, 还不错的样子..

Update: 这题数据比较弱, 用floyd简便很多, 因为为BFS准备比较麻烦, floyd直接开个数组全∞了事.. 复杂度N3

代码点下面 (没有任何可读性可言..)

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

struct __V__ {
    int e[200],n;
    bool eRec[201];
    int live[30],liveN;
    void link(int v) {
        if(eRec[v])
            return;
        eRec[v]=true;
        e[n++]=v;
        return;
    }
    void add(int l) {
        live[liveN++]=l;
        return;
    }
};

bool orz(int rec[],int L,int hasLive[],int hasLiveN,int steps) {
    for(int i=0;i<hasLiveN;i++) {
        if(steps<rec[hasLive[i]] || rec[hasLive[i]]==-1)
            rec[hasLive[i]]=steps;
    }
    for(int i=0;i<L;i++)
        if(rec[i]==-1)
            return false;
    return true;
}

int main() {
    __V__ V[201];
    int M;
    scanf("%d",&M);
    for(int i=1;i<=M;i++) {
        V[i].n=V[i].liveN=0;
        memset(V[i].eRec,false,sizeof(V[i].eRec));
    }

    int N,L,live[30];
    scanf("%d%d",&N,&L);
    for(int i=0;i<L;i++)
        scanf("%d",live+i);

    int border[251][251];
    for(int i=1;i<=N;i++)
        memset(border+i,0xff,sizeof(int)*(N+1));
    for(int i=1;i<=M;i++) {
        int n,p[250];
        scanf("%d",&n);
        for(int j=0;j<n;j++) {
            scanf("%d",p+j);
            for(int k=0;k<L;k++)
                if(live[k]==p[j])
                    V[i].add(k);
        }
        for(int j=0;j<n;j++)
            border[p[j]][p[(j+1)%n]]=i;
    }

    for(int i=1;i<=N;i++)
        for(int j=1;j<i;j++) {
            if(border[i][j]==-1)
                continue;
            if(border[j][i]==-1) {
                printf("BUG 1..\n");    //Debug
                exit(1);
            }
            int a=border[i][j],b=border[j][i];
            V[a].link(b);
            V[b].link(a);
        }

    //bfs
    int result=2E9;
    for(int start=1;start<=M;start++) {
        int seq[210],p0=0,p1=1,seqV[210];
        bool rec[201];
        memset(rec,false,sizeof(bool)*(M+1));
        seq[0]=start;
        seqV[0]=0;
        rec[start]=true;
        int liveRec[31];
        memset(liveRec,0xff,sizeof(liveRec));

        while(p0!=p1) {
            int foo=seq[p0];
            if(orz(liveRec,L,V[foo].live,V[foo].liveN,seqV[p0]))
                break;
            for(int i=0;i<V[foo].n;i++) {
                int to=V[foo].e[i];
                if(rec[to])
                    continue;
                seq[p1]=to;
                seqV[p1++]=seqV[p0]+1;
                rec[to]=true;
            }
            p0++;
        }

        int count=0;
        for(int i=0;i<L;i++)
            count+=liveRec[i];
        result=count<result?count:result;
    }

    printf("%d\n",result);
    return 0;
}

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.