Skip to content
Narrow screen resolution Wide screen resolution Auto adjust screen size Increase font size Decrease font size Default font size default color grey color
         
 | 
VNOI - Olympic tin học Việt Nam

Điểm tin VOJ

Số thành viên:6040
Số bài tập:1001
Số bài nộp:722923
Bài nộp hôm nay:0

Top 10 thành viên xuất sắc

HạngThành viênĐiểm
1mr_invincible587.9
2white_cobra418.6
3hieult403.4
4phaleq384.0
5vodanh9x368.2
6con_nha_ngheo352.0
7flash_mt350.2
8darksabers349.8
9yenthanh132345.3
10rockman9x_94343.1

Danh tiếng các thành viên

HạngThành viênĐiểm
1mr_invincible+213
2conankudo+149
3khuc_tuan+137
4tuananhnb93+129
5khanhptnk+108
6hphong+103
7flash_mt+99
8paulmcvn+71
9technolt+70
10hoangle+63

Topcoder Vietnam

HạngThành viênĐiểm
Diễn đàn
Forum
Help TRAVEL12 (1 đang xem) ,(1) Khách
Bài viết dưới cùng Gửi trả lời Được ưa thích: 0
CHỦ ĐỀ - Help TRAVEL12
#64739
CTK41 (Thành viên)
pktc
Biết code binary-indexed tree
Bài viết: 43
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Help TRAVEL12 8 năm, 5 tháng trước   (+0)
http://vn.spoj.pl/problems/TRAVEL12/
Thuat toan' minh la :duyet danh sach' ke ,voi moi canh (u,v) kiem tra v=trace[trace[trace[u]]] ko
code minh dc co' 55 diem
Code:
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#define maxn 10010
#define maxm 200010
#define For(i,a,b) for(int i=a;i<=b;i++)
#define DFor(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
long int n,m,a[maxm],h[maxm],trace[maxn],u[maxm],v[maxm];
bool Free[maxn],ok;
void input()
{
     scanf("%ld%ld",&n,&m);
     memset(h,0,sizeof(h));
     For(i,1,m)
     {
               scanf("%ld%ld",&u[i],&v[i]);
               h[u[i]]++;
               h[v[i]]++;
     }
     For(i,2,n+1) h[i]+=h[i-1];
     For(i,1,m)
     {
               a[h[u[i]]]=v[i];
               a[h[v[i]]]=u[i];
               h[u[i]]--;
               h[v[i]]--;
     }
}
void dfs(int u)
{
     Free[u]=false;
     For(i,h[u]+1,h[u+1])
     {
                         int v=a[i];
                         if(v==trace[trace[trace[u]]])
                         {
                                                      cout<<trace[trace[u]]<<" "<<trace[trace[trace[u]]]<<" "<<u<<" "<<trace[u]<<endl;
                                                      ok=true;
                                                      break;              
                         }
                         if(Free[v])
                         {
                                    trace[v]=u;
                                    dfs(v);
                                    Free[v]=false;
                         }
     }
}
int main()
{
    input();
    ok=false;
    memset(Free,true,sizeof(Free));
    For(i,1,n) 
    {
               trace[i]=0;
               dfs(i);
    }
    if(!ok) cout<<-1<<endl;
    //system("pause");
}
Moi nguoi cho hoi sai o dau,sua ho minh voi.Cam on moi nguoi
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#64740
pro39691010 (Thành viên)
ptnk8554517+5
Đã code là AC
Bài viết: 96
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: Help TRAVEL12 8 năm, 5 tháng trước   (+0)
Mih` cũng cài theo cách này chỉ ăn dc 85% test thou bạn ơi. Vì nếu thứ tự duyệt DFS khác nhau sẽ cho kết quả khác nhau. Nếu duyệt ko đúng thứ tự thì sẽ bị bỏ xót.
ví dụ như test này
1 2
2 3
3 4
4 5
2 4
1 5
Nếu thứ tự duyệt của bạn là 1 2 3 4 5 thì sẽ ko thấy dc ct 1 2 4 5 1
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#64743
CTK41 (Thành viên)
pktc
Biết code binary-indexed tree
Bài viết: 43
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: Help TRAVEL12 8 năm, 5 tháng trước   (+0)
Thuat toan' chuan bai nay la gi the^' cac' ban
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#68363
GreenNumber (Thành viên)
greennumber
Biết code binary-indexed tree
Bài viết: 43
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: Help TRAVEL12 8 năm, 1 tháng trước   (+0)
Các bạn có nghĩ tới tại sao người ta lại chỉ yêu cầu chu trình 4 cạnh 4 đỉnh mà không phải là 5 hay là 7, 8, 9, ... không ? Vì 4 = 2 + 2 đấy các bạn
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#69792
cuongtink21 (Thành viên)
cuongtink21
Đã biết code đệ quy
Bài viết: 19
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: Help TRAVEL12 8 năm trước   (+0)
Thuật toán của mình là :
-Với mỗi đỉnh BFS 1 lần ( BFS 2 tầng thôi )
-Nếu mà u ->v mà (free[v]=false)và (cha[u]<>v) và (d[u]+d[v]=3) (cả đỉnh s ban đầu nữa là 4) tạo ra được chu trình thì exit(true) luôn , và truy vết
?? Thuật Có TLE hoặc WA ko vậy ??
Kq chỉ được 80%
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#69814
vietthaitink21 (Thành viên)
vietthaitink21-
Đã code là AC
Bài viết: 85
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: Help TRAVEL12 8 năm trước   (+0)
cuongtink21 viết:
QUOTE:
Thuật toán của mình là :
-Với mỗi đỉnh BFS 1 lần ( BFS 2 tầng thôi )
-Nếu mà u ->v mà (free[v]=false)và (cha[u]<>v) và (d[u]+d[v]=3) (cả đỉnh s ban đầu nữa là 4) tạo ra được chu trình thì exit(true) luôn , và truy vết
?? Thuật Có TLE hoặc WA ko vậy ?? :?
Kq chỉ được 80%

bị Tle bạn ak
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#69823
vankiepsau95 (Thành viên)
vankiepsau95-
Nhắm mắt code không bug
Bài viết: 251
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: Help TRAVEL12 8 năm trước   (+0)
cuongtink21 viết:
QUOTE:
Thuật toán của mình là :
-Với mỗi đỉnh BFS 1 lần ( BFS 2 tầng thôi )
-Nếu mà u ->v mà (free[v]=false)và (cha[u]<>v) và (d[u]+d[v]=3) (cả đỉnh s ban đầu nữa là 4) tạo ra được chu trình thì exit(true) luôn , và truy vết
?? Thuật Có TLE hoặc WA ko vậy ?? :?
Kq chỉ được 80%

bạn bỏ cạnh trùng đi
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#69835
cuongtink21 (Thành viên)
cuongtink21
Đã biết code đệ quy
Bài viết: 19
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: Help TRAVEL12 8 năm trước   (+0)
Cạnh trùng nghĩa là sao bạn?
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#69836
cuongtink21 (Thành viên)
cuongtink21
Đã biết code đệ quy
Bài viết: 19
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: Help TRAVEL12 8 năm trước   (+0)
Cảm ơn bạn vietthaitink21 nhiều nha !
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#69898
Jeremy_Belpois_c3kt (Thành viên)
duthienkt
Đã biết code đệ quy
Bài viết: 19
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: Help TRAVEL12 8 năm trước   (+0)
Mình dùng cách này nhưng đc 85 điểm àùng một mảng số nguyên hai chiều A[1..n, 1..n]. Ban đầu các phần tử của A đều bằng 0. Ta duyệt các đỉnh theo thứ tự từ 1 đến n. Với đỉnh u, ta xét mọi cặp đỉnh x, y mà cả x và y kề với u. Nếu A[x,y] = 0 ta gán A[x,y] := u, ngược lại ta tìm được chu trình 4 đỉnh là x, u, y, A[x,y]. Mỗi lần thao tác ta sẽ thay một phần tử của mảng A đang có giá trị 0 thành một giá trị dương.
Có cách nào cải tiến để chạy nhanh hơn không
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
Bài viết trên cùng Gửi trả lời
Powered by FireBoardBài viết mới nhất từ diễn đàn cho các chương trình nhận tin RSS