fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <iostream>
  3. #include <string>
  4. #include <cmath>
  5. #include <vector>
  6. #include <map>
  7. #include <limits>
  8. #include <queue>
  9. #include <stack>
  10. #include <fstream>
  11. #define maxN 10002
  12. using namespace std;
  13. int n,m; // n la so sensor , m la so target
  14. int cnt=0;
  15. double rC ; // ban kinh truyen tin ;
  16. double rS ; // ban kinh bao phu
  17. int cntNaive=0;
  18. int used[maxN];
  19. int a[2001][2001];
  20. double x[2001],y[2001];
  21. int d[maxN], par[maxN];
  22. bool visit[maxN];
  23. void input()   // nhap vao cac toa do cua sensor va base voi qui uoc (x[0],y[0]) la toa do do cua base;
  24.     {   
  25.         cin >> n >> m  >> rC >> rS ;
  26.         for(int i = 0 ; i <= n ; i++)  // nhap vap vi tri cua base station ( x[0],y[0]) va toa do cua n sensor;
  27.                 cin >> x[i] >> y[i];
  28.         for(int i = n+1 ; i<= n+m ;i++) // nhap vao vi tri cua m target ;
  29.                 cin >> x[i] >> y[i];
  30.     }
  31. double distance (double x,double y,double z, double t )  // tinh khoang cach
  32.     {
  33.         double seg = sqrt((x-z)*(x-z)+(y-t)*(y-t));
  34.         return seg;
  35.     }
  36. void graphModel() // dua ve mo hinh do thi
  37.     {
  38.         for(int i = 0 ; i <= n ; i++)   // noi cac canh giua cac sensor va base station;
  39.             for( int j = 0 ; j <= n ;j ++)
  40.                 {
  41.                     if(i==j)
  42.                         a[i][j]=0;
  43.                     else
  44.                         {
  45.                             if(distance(x[i],y[i],x[j],y[j]) <= rC )
  46.                                 a[i][j]=1;
  47.                                 a[j][i]=1;
  48.                         }                        
  49.                 }
  50.         for(int i = n+1 ; i <= n+m ; i++) // noi canh giua target va sensor neu khoang cach  <= rS
  51.             for(int j = 1 ;j <=n ; j++)
  52.                 if(distance(x[i],y[i],x[j],y[j]) <= rS){
  53.                     a[i][j]=1;
  54.                     a[j][i]=1;
  55.                 }
  56.     }
  57. void fix(){
  58.     for(int i = 1 ; i <=m+ n; i++){   // ham cap nhat lai ket qua sau khi de qui
  59.         used[i]=0;
  60.     }
  61. }
  62. void bfs(int s)  // xet s la dinh dang xet , o bai toan nay ta se bfs tu base station
  63.  {
  64.     fill_n(d, n + 1, 0);
  65.     fill_n(par, n + 1, -1);
  66.     fill_n(visit, n + 1, false); // ham kiem tra la da tham dinh hay chua 
  67.     queue <int> q;
  68.     q.push(s);
  69.     visit[s] = true;
  70.     while (!q.empty()) 
  71.     {
  72.         int u = q.front();
  73.         q.pop();
  74.         for (int v = 0 ;  v <= n ; v++) 
  75.         {
  76.             if(a[v][u]==1 && used [v]==0)
  77.                 if (!visit[v]) 
  78.                 {
  79.                     d[v]     = d[u] + 1; // cap nhat do dai duong di ngan nhat
  80.                     par[v]   = u; // truy vet duong di
  81.                     visit[v] = true;
  82.                     q.push(v);
  83.                 }
  84.         }
  85.     }
  86. }
  87. void delete_vertex(int s) // xoa mot dinh
  88.     {
  89.         for(int i = 0 ; i <= m+n; i++)
  90.             {
  91.                 a[s][i]=0;
  92.                 a[i][s]=0;
  93.             }
  94.     }
  95. void delete_edge(int s, int t) // xoa canh s->t
  96.     {
  97.         a[s][t]=0;
  98.         a[t][s]=0;
  99.     }
  100. void add_edge(int s,int t)
  101.     {
  102.         a[s][t]=1;
  103.         a[t][s]=1;
  104.     }
  105. int checkPath(int source){
  106.     int sea=-1;
  107.     bfs(0);
  108.     int abc=INT_MAX;
  109.     for(int i =1 ; i <= n; i++){
  110.         if(a[source][i] == 1 && d[i] != 0 && used[i]==0){
  111.             if(abc> d[i]){
  112.                 abc=d[i];
  113.                 sea=i;
  114.             }
  115.         }
  116.     }
  117.     if(sea==-1){
  118.         return 0;
  119.     }
  120.     return sea;
  121. }
  122. void naive(int source) // ham phu. tinh so duong di phan biet tu source den sink ( source o day chinh la target )
  123.     {
  124.             int search=-1;
  125.             bfs(0);  // bfs tu di?nh root la 0 (chinh la base station)
  126.             int abc=INT_MAX;
  127.             if(checkPath(source)==0){
  128.                 return;
  129.             }
  130.             else{
  131.                 cnt++;
  132.                 int temp=checkPath(source);
  133.                 while(temp!=source){
  134.                     used[temp]=1;   // danh dau nhung dinh bi bo
  135.                     temp=par[temp];
  136.                 }
  137.                 naive(source);
  138.         }                   
  139.     }   
  140. int MebDisjPath(int source)
  141.     {  
  142.         int search=-1,res=0;
  143.  
  144.         /*bfs(0); // tinh do dai duong di tu cac target, sensor toi base station;
  145.         int cnt=INT_MAX; 
  146.         for(int i=1;i <=n ; i++){
  147.             cout << d[i] << endl;
  148.         }
  149.         for(int i = 1 ; i <= n ; i++)  // tim sensor ma ke voi source va do dai duong di tu no cho den base la ngan nhat
  150.                 cout << a[source][i] << endl;
  151.                 if(a[source][i]==1 && d[i] != 0)
  152.                     {
  153.                         if(cnt > d[i])
  154.                             {
  155.                                 cnt = d[i];
  156.                                 search = i;
  157.                             }
  158.                 
  159.                     } 
  160.  
  161.         if(search==-1)
  162.             return 0;
  163.         
  164.         int temp1=0;
  165.         int length=d[search]+1;
  166.         res=naive(source);
  167.         while(temp1 <= length)
  168.             {
  169.                 if(temp1==0)
  170.                     {
  171.                         delete_edge(source,search);
  172.                         int ans=naive(source);
  173.                         if(ans <= res )
  174.                             add_edge(source,search);
  175.                         else
  176.                             res=ans ;// cap nhat dap an va khong them canh vua xoa ;
  177.                     temp1++;
  178.                     search=par[search];
  179.                     }
  180.                 else  // tuong tu truong hop temp1=0;
  181.                     {   
  182.                         int vertex=par[search];
  183.                         delete_edge(search,vertex);
  184.                         int ans=naive(source);
  185.                         if(ans <= res )
  186.                             add_edge(search,vertex);
  187.                         else
  188.                             res=ans ;
  189.                     temp1++;
  190.                     search=par[search];
  191.                     }
  192.             } */
  193.         return res;
  194.     } 
  195. int main()
  196.     {   
  197.  
  198.         freopen("nhap.inp","r",stdin);
  199.         freopen("ra.out","w",stdout);
  200.         input();
  201.         graphModel();
  202.         cnt=0;
  203.         int example ;
  204.         cin >> example;
  205.         cout << "hello" << endl;
  206.         /*cout << "Ket qua cua bien search trong ham MeDisPath(3) la : ";
  207.         MebDisjPath(3); */
  208.         naive(3); int l = cnt; fix();
  209.         cnt=0 ; naive(4); int r= cnt; fix();
  210.         cout << "Ket qua cua ham naive(3) va naive(4) la: \n" << l <<" \n " << r << endl;
  211.         // naive(3);
  212.         //cout << "So duong di phan biet tu target " << example <<" toi base station la: " << MebDisjPath(example)  << endl;
  213.  
  214.     }
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
2
2
1
1
0 0
0.1 0.1
0.2 0.2
0.12 0.12
0.13 0.13
3
stdout
copy 
Standard output is empty
https://ideone.com/R9N8Hs
language:
C++ (gcc 8.3)
created:
12 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!