題目描述:
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=30
在歐式平面圖上找長度為k的簡單環, 環中不允許有其他點, 圖是聯通圖.
其中邊不能穿過點(題中沒說明白, 只說了邊不能"cross")
算法分析:
因為是聯通圖, 我們只需要遞歸的貪心的去找邊就可以了. 枚舉一個向量, 然后按照順(逆)時針的貪心規則去把"區域"找出來.
非法情況有以下幾種:
1. unboundry edge , 可能沒有其他的聯通邊.
2. complex circle , 遇到了"反向邊", 或者在"封口"的時候, 下一個邊不是初始邊.
3. 并非inner region, 在遞歸的過程中不斷收集角度, 最后等于多邊形內角和才可以哦~
如果不是聯通圖或者邊可以穿過點, 那就爽了...
zoj 1030
#include<iostream>
#include<cstring>
#include<complex>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<cmath>
using namespace std;
#define debug
typedef complex <double> pnt;
const int N = 205;
const double eps = 1e-8;
const double pi = acos(-1.0);
double tmp[N][N], dis[N][N];
pnt p[N];
vector<int> to[N];
vector<pair<double,int> > G[N];
bool done[N][N], vis[N], visit[N];
int stk[N], tp, n;
inline double fix(double x,double d = 0, double u = 2*pi){
while(x < d) x += 2*pi;
while(x >= u) x -= 2*pi;
return x;
}
int dfs(int u, int f, double angle){
// cout<< u+1 <<" "<<angle<<endl;
if(vis[u]) {
if(stk[0] != u) return -1; // not simple cycle
int v = lower_bound(G[u].begin(), G[u].end(),make_pair(tmp[u][f],f)) - G[u].begin();
v = (v - 1 + G[u].size()) % G[u].size();
v = G[u][v].second;
if(!vis[v]) return -1;
// answer
angle += fix(tmp[u][f] - tmp[u][v]);
// cout<<f+1<<" "<<v+1<<" "<<angle<<endl;
if(abs(angle - (tp-2) * pi) > eps) return -1; // outside region
// cout<<".."<<endl;
return tp;
}
vis[u] = 1;
if(G[u].size() == 1) return -1; // unboundry edge
int v = lower_bound(G[u].begin(), G[u].end(), make_pair(tmp[u][f],f)) - G[u].begin();
v = (v - 1 + G[u].size()) % G[u].size();
v = G[u][v].second;
done[u][v] = 1;
stk[tp++] = u;
return dfs(v,u,angle + fix(tmp[u][f] - tmp[u][v]));
}
int main(){
int cas;
cin >> cas;
while(cas --){
int m, id, v, x, y;
cin >> n;
for(int i = 0; i < n; i++){
cin >> id >> x >> y >> m;
id --;
p[id] = pnt(x,y);
to[id].clear();
for(int j =0; j < m; j++){
cin >> v; v--;
to[id].push_back(v);
}
}
for(int i =0; i < n; i++)
for(int j =0; j < n; j++) if(i != j)
tmp[i][j] =fix( arg(p[j] - p[i]));
for(int i = 0; i < n; i++){
G[i].clear();
for(int j = 0; j < to[i].size(); j++){
G[i].push_back(make_pair(tmp[i][to[i][j]] , to[i][j]));
}
sort(G[i].begin(), G[i].end());
}
int s, ans = 0;
cin >> s;
memset(done, 0, sizeof(done));
for(int i = 0; i < n; i++){
for(int j = 0; j < G[i].size(); j++) {
int v = G[i][j].second;
// cout<<"i j: "<<i+1<<" "<<v+1<<endl;
if(done[i][v]) continue;
memset(vis,0,sizeof(vis));
vis[i] = 1; tp = 1; stk[0] = i;
if( s == dfs(v,i,0))
ans ++;
// cout<<endl;
}
}
cout << ans << endl;
}
}
posted on 2012-09-04 14:39
西月弦 閱讀(351)
評論(0) 編輯 收藏 引用 所屬分類:
解題報告