USACO 4.3.3 Buy Street Race 街道賽跑 race3
本文正體字版由OpenCC轉換
一道基礎的連通分量的圖論題。這個題默認了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;
}
上次修改時間 2017-02-03