USACO 4.3.3 Buy Street Race 街道賽跑 race3

一道基礎的連通分量的圖論題。這個題默認了0爲起點,N爲終點,如果不放心可以再讀入的時候判斷起點和終點,即入度爲0的點爲起點,出度爲0的點爲終點。

該題有兩問,第一問很簡單,可以嘗試去掉每一個點,判斷從起點到終點是否有通路,如果沒有則該點爲“必經點”。

第二問終點在於理解題意。首先可以確定第二問的解集是第一問的子集,所以我們可以第一問得出的每個點深搜,記錄下可以到達的點。然後去掉該點,從起點深搜。如果不存在兩次深搜皆可到達的點,就說明它是分割點。

/*
ID: cmykrgb1
PROG: race3
LANG: C++
*/
#include <iostream>
#include <fstream>
#define MAX 101
using namespace std;
ifstream fi("race3.in");
ofstream fo("race3.out");

int adjl[MAX][MAX];
int ans[MAX][2];
bool used[MAX],tused[MAX];
int N,start,end;

void init()
{
    int a=0,i=0;
    while (a!=-1)
    {
        fi >> a;
        while (a>=0)
        {
            adjl[i][ ++adjl[i][0] ]=a;
            used[a]=true;
            fi >> a;
        }
        i++;
    }
    N=i-2;
    for (i=0;i<=N;i++)
    {
        if (adjl[i][0]==0)
            end=i;
        if (!used[i])
            start=i;
    }
}

void dfs3(int i)
{
    int k,j;
    for (k=1;k<=adjl[i][0];k++)
    {
        j=adjl[i][k];
        if (!tused[j])
        {
            tused[j]=true;
            dfs3(j);
        }
    }
}

void dfs2(int i)
{
    int k,j;
    for (k=1;k<=adjl[i][0];k++)
    {
        j=adjl[i][k];
        if (!used[j])
        {
            used[j]=true;
            dfs2(j);
        }
    }
}

void question2()
{
    int i,j,k;
    for (i=1;i<=N-1;i++)
    {
        memset(used,0,sizeof(used));
        memset(tused,0,sizeof(tused));
        dfs2(i);
        tused[i]=true;
        tused[0]=true;
        dfs3(0);
        k=1;
        for (j=0;j<=N;j++)
            if (j!=i && used[j] && tused[j])
            {
                k=0;
                break;
            }
        if (k)
            ans[ ++ans[0][1] ][1]=i;
    }
}

void dfs1(int i)
{
    int k,j;
    for (k=1;k<=adjl[i][0];k++)
    {
        j=adjl[i][k];
        if (!used[j])
        {
            used[j]=true;
            dfs1(j);
        }
    }
}

void question1()
{
    int i;
    for (i=1;i<=N-1;i++)
    {
        memset(used,0,sizeof(used));
        used[i]=true;
        dfs1(0);
        if (!used[N])
            ans[ ++ans[0][0] ][0]=i;
    }
}

void print()
{
    int i;
    fo << ans[0][0];
    for (i=1;i<=ans[0][0];i++)
        fo <<' ' << ans[i][0];
    fo << endl;
    fo << ans[0][1];
    for (i=1;i<=ans[0][1];i++)
        fo <<' ' << ans[i][1];
    fo << endl;
    fi.close();
    fo.close();
}

int main()
{
    init();
    question1();
    question2();
    print();
    return 0;
}

相關日誌