随笔-141  评论-9  文章-3  trackbacks-0
USACO 4.3.3 Street Race(连通性,DFS)

第一问， 枚举地拿掉每个点u，看能否连通（dfs 到n），能连通的就是必需经过的点，对于点u 进行DFS，看会不会重复经过第一问中已经访问过的点，若都没有经过，则该u点符合第二问。

/*
ID: lorelei3
TASK: race3
LANG: C++
*/

#include <fstream>
#include <memory.h>

using namespace std;

const int MAX = 55;

ifstream fin("race3.in");
ofstream fout("race3.out");

int map[MAX][MAX];
int visited[MAX], ans1[MAX], ans2[MAX], cnt1, cnt2, n;

void input(){
    int i=0, in=0;
    while(fin>>in && in!=-2){
        int t=in;
        int c = ++map[i][0];
        map[i][c]=t;
        
        while(fin>>t && t!=-2){
            int c = ++map[i][0];
            map[i][c]=t;
        }
        i++;
    }
    fin>>in;
    n=i;
}

bool dfs1(int u){
    if(u==n)
        return true;

    for(int i=1; i<=map[u][0]; ++i){
        int v = map[u][i];
        if(visited[v]==0){
            visited[v]=1;
            if(dfs1(v))
                return true;
        }
    }
    return false;
}

bool rep;
void dfs2(int u){
    if(rep)
        return;
    if(visited[u]==2)
        return;

    visited[u]=2;
    for(int i=1; i<=map[u][0]; ++i){
        int v = map[u][i];
        if(visited[v]==1){
            rep=true;
            return;
        }
        dfs2(v);
    }
}

void solve(){
    for(int i=1; i<n; ++i){
        memset(visited, 0, sizeof(visited));
        visited[i]=1;
        visited[0]=1;
        if(!dfs1(0)){
            ans1[cnt1++] = i;
            rep = false;
            dfs2(i);
            if(rep == false)
                ans2[cnt2++] = i;
        }
    }
}

void output(){
    int i;
    fout<<cnt1;

    if(cnt1!=0){
        fout<<" ";
        for(i=0; i<cnt1-1; ++i)
            fout<<ans1[i]<<" ";
        fout<<ans1[cnt1-1];
    }
    fout<<endl;

    fout<<cnt2;
    if(cnt2!=0){
        fout<<" ";
        for(i=0; i<cnt2-1; ++i)
            fout<<ans2[i]<<" ";
        fout<<ans2[cnt2-1];
    }
    fout<<endl;
}

int main(){

    input();

    solve();

    output();

    return 0;
}
posted on 2011-01-29 20:01 小阮 阅读(333) 评论(0)  编辑 收藏 引用 所属分类: USACO

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


Powered by: 博客园 模板提供：沪江博客 Copyright ©2024 小阮