愚人隨筆: 5月 2014

2014年5月19日星期一

247 - Calling Circles

有一家電信公司記錄了所有人之間打電話的紀錄，他們想找出所有的通話圈圈(calling circles)

舉例來說，如果A打給B，B打給C，C又打給A，ABC之間就可以跟任何一個人互相溝通，他們就形成一個calling circle。但假如D可以打給A，但A不能打給D，D跟A就不算calling circle。

輸入

每筆測資先給你總共的人數n，和通話紀錄m筆

接下來m行會有兩個人名(25字元以內)，代表前面的人打給後面的人(單向)。

輸出

每筆測資先輸出一行"Calling circles for data set x:"(x代表第幾筆)

接下來每行輸出一個calling circle中的所有人名，之間以逗號和空白隔開，順序都可以

Sample Input

5 6
Ben Alexander
Alexander Dolly
Dolly Ben
Dolly Benedict
Benedict Dolly
Alexander Aaron
14 34
John Aaron
Aaron Benedict
Betsy John
Betsy Ringo
Ringo Dolly
Benedict Paul
John Betsy
John Aaron
Benedict George
Dolly Ringo
Paul Martha
George Ben
Alexander George
Betsy Ringo
Alexander Stephen
Martha Stephen
Benedict Alexander
Stephen Paul
Betsy Ringo
Quincy Martha
Ben Patrick
Betsy Ringo
Patrick Stephen
Paul Alexander
Patrick Ben
Stephen Quincy
Ringo Betsy
Betsy Benedict
Betsy Benedict
Betsy Benedict
Betsy Benedict
Betsy Benedict
Betsy Benedict
Quincy Martha
0 0

Sample Output

Calling circles for data set 1:
Ben, Alexander, Dolly, Benedict
Aaron

Calling circles for data set 2:
John, Betsy, Ringo, Dolly
Aaron
Benedict
Paul, George, Martha, Ben, Alexander, Stephen, Quincy, Patrick

這題就是找出所有強連接元件(strong connected vertex)。

做法是以dfs搜索每個點並編號(存在dfn陣列裡)，同時把每個搜過的點丟到一個stack中，假如遇到編號比自己小的(之前搜過的點)，就代表有環產生，此時會把這個值(能到達最前面的點)紀錄在low陣列裡，每做完一次dfs都要檢查下一個的low如果比自己小，自己的low也要更新。

簡單的說，dfn是紀錄順序，而low是每個點可以到達最前面的點。

假如一個點x做完每條dfs而dfn仍然等於low(一開始是設為相等)，代表兩種情況：他不屬於一個環，或他是一個環中最前面的點，而這兩種情況其實都是強連接元件(只是第一個情況只有自己)。

這時候就把存在stack中的點一個一個丟出來，直到丟出x，這些點就是一個強連接元件，也就是一個calling circle。

注意題目的圖可能不連通，所以要dfs多次。

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <map>
#include <string>
#include <stack>

using namespace std;

map<string,int> trans;
char str[110][50];
int low[110],dfn[110],t,countt;
vector<int> v[110],ans[110];
stack<int> s;
bool used[110];

bool exist(string key){
    return trans.find(key) != trans.end();
}

void dfs(int cur){
    int next,children=0,i,x;
    low[cur]=t;
    dfn[cur]=t;
    t++;
    s.push(cur);
    for(i=0;i<v[cur].size();i++){
        next=v[cur][i];
        if(dfn[next]==0){
            children++;
            dfs(v[cur][i]);
            if(low[cur]>low[next])low[cur]=low[next];
        }
        else if(!used[next]){
            if(dfn[next]<low[cur]){
                low[cur]=dfn[next];
            }
        }
    }
    if(low[cur]==dfn[cur]){
        for(;;){
            x=s.top(); s.pop();
            used[x]=true;
            ans[countt].push_back(x);
            if(x==cur){
                countt++;
                break;
            }
        }
    }
    return;
}

int main()
{
    int n,i,j,cur,m,a,b,c=1,num;
    char s1[50],s2[50];
    while(scanf("%d %d",&n,&m)!=EOF){
        if(n==0 && m==0)break;
        countt=0;
        t=1;
        memset(low,0,sizeof(low));
        memset(dfn,0,sizeof(dfn));
        memset(used,false,sizeof(used));
        if(c!=1)printf("\n");
        printf("Calling circles for data set %d:\n",c++);
        for(i=0;i<m;i++){
            scanf("%s %s",s1,s2);
            if(!exist(s1)){
                trans[s1]=countt;
                sscanf(s1,"%s",str[countt]);
                countt++;
            }
            if(!exist(s2)){
                trans[s2]=countt;
                sscanf(s2,"%s",str[countt]);
                countt++;
            }
            a=trans[s1]; b=trans[s2];
            v[a].push_back(b);
        }
        num=countt;
        countt=0;
        for(i=0;i<num;i++){
            if(!used[i]){
                dfs(i);
            }
        }
        for(i=0;i<countt;i++){
            for(j=0;j<ans[i].size();j++){
                if(j!=0)printf(", ");
                printf("%s",str[ans[i][j]]);
            }
            printf("\n");
        }
        trans.clear();
        for(i=0;i<n;i++){
            v[i].clear();
            ans[i].clear();
        }
    }
    return 0;
}

2014年5月18日星期日

10199 - Tourist Guide

在一座城市中有n個區塊，m條雙向的道路將區塊連結起來，而假如兩個區塊間必須經過另一個區塊，則那個區塊會有一台測速照相機。
你的朋友不太會開車，他想知道所有相機的位置，請寫個程式幫幫他。
輸入一開始給n，接著n個區塊的名字，然後是m跟每條道路連接的區塊。

Sample Input

6
sugarloaf
maracana
copacabana
ipanema
corcovado
lapa
7
ipanema copacabana
copacabana sugarloaf
ipanema sugarloaf
maracana lapa
sugarloaf maracana
corcovado sugarloaf
lapa corcovado
5
guanabarabay
downtown
botanicgarden
colombo
sambodromo
4
guanabarabay sambodromo
downtown sambodromo
sambodromo botanicgarden
colombo sambodromo
0

Sample Output

City map #1: 1 camera(s) found
sugarloaf

City map #2: 1 camera(s) found
sambodromo

這題是個滿基本的找割點問題。在沒有環的情況下，假如一個點連接兩個以上的點，那就是割點( 移除他後整張圖會被割開 )。
用dfs向下搜尋，每搜尋一個點就幫他編號，如果搜尋到編號比自己小的(之前編號過)就代表有環。
要注意這題可能一開始就沒有完全相連，所以可能要dfs多次

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <map>
#include <string>

using namespace std;

map<string,int> trans;
int low[110],dfn[110],t;
vector<int> v[110],ans;
char s[110][50];
bool used[110];

int compare(const void *a,const void *b){
return strcmp((char *)a,(char *)b);
}

void dfs(int pa,int cur){
int next,children=0,i;
bool flag=false;
low[cur]=t;
dfn[cur]=t;
used[cur]=true;
t++;
for(i=0;i<v[cur].size();i++){
next=v[cur][i];
if(dfn[next]==0){
children++;
dfs(cur,v[cur][i]);
if(low[cur]>low[next])low[cur]=low[next];
if(low[next]>=dfn[cur]){
flag=true;
}
}
else if (pa != next){
if(dfn[next]<low[cur])low[cur]=dfn[next];
}
}
if(flag && (children>1 || pa!=-1)){
ans.push_back(cur);
}
return;
}

int main()
{
int n,i,j,cur,m,a,b,c=1;
char s1[50],s2[50];
while(scanf("%d",&n)!=EOF){
if(n==0)break;
memset(low,0,sizeof(low));
memset(dfn,0,sizeof(dfn));
memset(used,false,sizeof(used));
t=1;
for(i=0;i<n;i++){
scanf("%s",s[i]);
}
qsort(s,n,sizeof(char[50]),compare);
for(i=0;i<n;i++){
trans[s[i]]=i;
}
scanf("%d",&m);
for(i=0;i<m;i++){
scanf("%s %s",s1,s2);
a=trans[s1]; b=trans[s2];
v[a].push_back(b);
v[b].push_back(a);
}
for(i=0;i<n;i++){
if(!used[i])dfs(-1,i);
}
sort(ans.begin(),ans.end());
if(c!=1)printf("\n");
printf("City map #%d: %d camera(s) found\n",c++,ans.size());
for(i=0;i<ans.size();i++){
printf("%s\n",s[ans[i]]);
}
for(i=0;i<n;i++){
v[i].clear();
}
ans.clear();
trans.clear();
}
return 0;
}

2014年5月7日星期三

UVA 670 - The dog task

670 - The dog task

Bob喜歡跟他的狗一起散步，但狗狗跑得比較快，所以狗狗會在散步的過程中跑到其他有趣的地方，只要在每個會合點跟Bob相遇就好了。狗狗的速度是Bob的兩倍，而在兩個會合點之間狗狗頂多只能去一個有趣的地方。

輸入的第一行是有幾筆資料，每筆開頭給兩個數字(<=100)，第一個n是Bob會經過多少個會合點，第二個m是地圖上有多少有趣的地方。
接下來第一行是每個會合點的座標，下一行是有趣的點的座標。(最標是絕對值<=1000的int)

輸出先輸出狗狗總共會經過幾個點(會合點+有趣的點)，下一行是照順序印出他經過的座標。這個題目可能有多種答案，每一種都可以。

Sample Input

1

4 5
1 4 5 7 5 2 -2 4
-4 -2 3 9 1 2 -1 3 8 -3

Sample Output

6
1 4 3 9 5 7 5 2 1 2 -2 4

想法

簡單的說就是個二分匹配的題目，每個會合點配對一個有趣點(記得最後一個沒有)。
其實題目根本沒什麼，但卻WA了好幾次......
最後發現的問題真的很令人困惑，竟然是出在比較距離的地方，我一開始沒有開根號。
像這樣：
int dis(int a,int b,int c,int d){
int xx=x[a][b]-x[c][d];
int yy=y[a][b]-y[c][d];
return xx*xx+yy*yy;
}
結果加了sqrt後就AC了.....但是這根本不合理啊啊啊！直接用平方比較應該比浮點運算更沒有誤差，而且題目的座標在1000以內，應該也不會有overflow的問題才對啊！

總之是謎啊......

#include <cstdio>
#include <cstring>
#include <cmath>

using namespace std;

int n,m,x[2][110],y[2][110];
bool select[110];
int match[2][110]={0};

double dis(int a,int b,int c,int d){
int xx=x[a][b]-x[c][d];
int yy=y[a][b]-y[c][d];
return sqrt(xx*xx+yy*yy);
}

bool reach(int a,int b)
{
if(2*dis(0,a+1,0,a)>=dis(1,b,0,a)+dis(0,a+1,1,b))return true;
else return false;
}

bool find(int no)
{
int i;
for(i=1;i<=m;i++){
if(select[i])continue;
if(!reach(no,i))continue;
select[i]=true;
if(match[1][i]==0){
match[0][no]=i; match[1][i]=no;
return true;
}
else {
if(find(match[1][i])){
match[0][no]=i; match[1][i]=no;
return true;
}
}
}
return false;
}

int main()
{
int N,t,ans,i,j;
scanf("%d",&N);
for(t=1;t<=N;t++){
scanf("%d %d",&n,&m);
memset(match,0,sizeof(match));
ans=0;
for(i=1;i<=n;i++){
scanf("%d %d",&x[0][i],&y[0][i]);
}
for(i=1;i<=m;i++){
scanf("%d %d",&x[1][i],&y[1][i]);
}
for(j=1;j<n;j++){
memset(select,false,sizeof(select));
if(find(j)){
ans++;
}
}
printf("%d\n",n+ans);
for(i=1;i<=n;i++){
printf("%d %d",x[0][i],y[0][i]);
if(match[0][i]!=0){
printf(" %d %d",x[1][match[0][i]],y[1][match[0][i]]);
}
if(i!=n)printf(" ");
}
printf("\n");
if(t<N)printf("\n");
}
return 0;
}

愚人隨筆

2014年5月19日星期一

UVA 247 - Calling Circles

247 - Calling Circles

Sample Input

Sample Output

2014年5月18日星期日

UVA 10199 - Tourist Guide

10199 - Tourist Guide

Sample Input

Sample Output

2014年5月7日星期三

UVA 670 - The dog task

670 - The dog task

Sample Input

Sample Output

2014年5月19日 星期一

UVA 247 - Calling Circles

247 - Calling Circles

Sample Input

Sample Output

2014年5月18日 星期日

UVA 10199 - Tourist Guide

10199 - Tourist Guide

Sample Input

Sample Output

2014年5月7日 星期三

UVA 670 - The dog task

670 - The dog task

Sample Input

Sample Output

2014年5月19日星期一

2014年5月18日星期日

2014年5月7日星期三