Network maximum flow, Ford-Fulkerson алгоритм маш энгийнээр, Монголын Үндэсний Оюутны Програмчлалын Олимпиад 14 анализ.

За сайн байцгаана уу. Хичээл их байгаа зав болохоороо пост бичнэ гээд байгаад байвал боломж бол гарахгүй юм байна ер нь. Тэгэхээр хамаагүй маш товч товч бичээд явья гэж бодлоо.

Үндэсний програмчлалын тэмцээн 4-н сарын 10-н 11-нд болсон. Одоогоор надад бүх бодлогууд нь ирээгүй байна, гэхдээ энэ тэмцээнд миний нэг бодлого сонгогдсон ба уг бодлогыхаа анализыг хийнэ. Гэснээс ганц ч баг бодоогүй байна лээ.

Үүнээс өмнө товчхон нетворк флов - урсгалын бодлогыг тайлбарлая.

Урсгалын бодлого маш олон янзаар гарч ирдэг. Жишээ нь хотын замын сүлжээ өгөгдсөн байгаа8 мөн зам бүр дээр явах машины тоог хязгаартай, энэ хязгаарууд нь бидэнд өгөгдсөн. Тэгвэл А гэсэн хотоос В гэсэн хотруу хамгийн ихдээ хэдэн машин явуулж болох вэ? Энэ бодлогыг Maximum Flow гэж нэрлэдэг.

Өөр нэгэн жишээ, Хотын сүлжээ замууд өгөгдсөн. Та тодорхой хэдэн тооны зам устгаж А В гэсэн 2 хотыг хооронд нь хүрэх боломжгүй болгох гэж байгаа. Зам бүрийг устгахад тодорхой зардалтай, таны даалгавар уг гарах зардалыг хамгийн бага байлгах юм. Энэ бодлогыг Minimum cut гэж нэрлэдэг.



Дээрх 2 бодлого 2уул өөр харагдаж байгаа ч, гайхалтай теорем, хариу яг ижил гардаг. Өөрөөр хэлвэл ямар нэгэн эерэг жинтэй чиглэлт графын хувьд, А оройгоос В оройн хувьд MaximumFlow = MinCut байдаг.


Жишээг зургаар харуулая.





s гэсэн оройгоос t гэсэн орой хүрэв хамгийн их урсгал 23 буюу дараах замуудыг ашигласан байх нь.





Одоо тэгвэл мөн 2 оройн хоорондахь MinCut-г олоё. Дээрх хэлсэн теоремоор хамгийн их урсгалтай тэнцүү 23 буюу дараах замуудыг устгах нь.





Алгоритмаа тайлбарлая

Өгөгдсөн графын хувьд s-с t хүрдэг ямар нэгэн замыг авч үзье, мөн үүнийгээ дэд зам гэж нэрлэе. Энэ нь бидэнд уг замд ашиглагдаж байгаа жингүүд бас мэдэгдэж байгаа ба эдгээрийгээ w1 w2 ... wk гэе. Тэгвэл энэ олсон замаар хамгийн ихдээ хэдий хэмжээний урсгал урсуулж болох вэ? энэ асуултын хариу min(w1, w2, ..., wk). Энэ хариуг урсгалын дэд хэмжээ гэе.
Дээрх жишээний хувьд дараах дэд замууд байж болох ба тухай бүрийх нь дэд урсгалууд нь хамгийн бага утгаад нь байхнээ.






Алгоритмд ашиглагдах ба нэгэн ухагдахууныг тайлбарлая


Ирмэгийг эргүүлэх


C(u -> v)-ээр хоёр хөрш u, v оройн хоорондахь боломжит урсгалын хэмжээг тэмдэглэе, мэдээж энэ чиглэлтэй шүү.
Тэгвэл ямар нэгэн дэд урсгал f уг хоёр хөрш оройгоор дамжвал

C(u -> v)-г f-ээр багасгаад

C(v -> u)-г f-ээр нэмэгдүүлэе.

Ингэх нь юун ашигтай вэ гэхээр, бодоо үзээрэй, ямар нэгэн урсгалыг явуулчаад буцаана гэдэг нь энэ урсгалыг ашиглаагүйтэй адил.

За одоо дараах үйлдэлийг боломжгүй болтол нь хийе.

0 flow = 0

1 Хэрэв олдвол ямар нэгэн дэд зам ол, DFS.

2 Дэд урсгалыг ол flow-н утгыг уг утгаараа нэмэгдүүл.

3 Дэд зам-г бүрдүүлж байгаа бүх (u -> v)-н хувьд C(u->v)-г дэд урсгалаар багасгаж, C(v->u)-г дэд урсгалаар нэмэгдүүл.

4 1рүү оч.


За хө ингээд болоо. Дээрх алгоритмыг Ford-Fulkerson гэдэг, олсон хүнийх нь нэр. Хугацааны үнэлгээний хувьд дэд замыг O(V+E), мөн бид ядаж 1 урсгалыг дамжуулж байгаа тэгэхээр O((V+E)*flow). Энэ ер нь бол ихэнх тохиолдолд хангалттай үнэлгээ уг бодлогын хувьд.


MinCut бодлогын хувьд утгыг нь тэгээд олчихдог юм байж. Яаж устгагдсан ирмэгүүдийг олох вэ? энэ бодлогыг энэ талаар судлаж сонирхож байгаа хүмүүст өөрсөдөд нь үлдээе, энгийн амархан олдно. Туслах үүднээс, дээр хэрэглэгдэж байгаа С гэсэн хүснэгт бодлогын хариуг олсны дараа ямархуу байдалтай болж гэдэгийг ажиглаараа, энэ хүснэгтээс ирмэгийг олно.
Дараа дараагийхаа постоор хэрхэн алгоритмаа сайжруулах мөн жишээ бодлогуудын бодолт харуулая.


За одоо өөрийн бодлогоруугаа ороё.
Бодлогын өгүүлбэрийг энд дарж уншина уу.


Бодлого бол s гэсэн оройгоос t гэсэн орой хүртэл хоорондоо аль ч ирмэг оройгоор огтлолцоогүй байх 2 зам олох ба замуудын нийлбэр хамгийн бага байх ёстой. Энэ бодлогонд s=1, t=V гэж бэхлэсэн байгаа.


d(s,u)-ээр s оройгоос u хүрэх хамгийн богино замын хэмжээг тэмдэглэе. w(u,v)-ээр хэрэв u, v гэсэн орой хоорондоо u->v гэх чиглэлээр холбогдсон хөрш оройнууд бол тухайн ирмэгийн жинг тэмдэглэе.


Одоо s-ээс богино замын алгоритм Дижкстра хийн богино замуудыг олоё. Ингэхдээ бид s-дээр оройтой Т гэсэн модыг байгуулж чадна. Уг модон дээр байгаа u гэсэн орой бүрийн хувьд бид s->u богино замыг мэдэж чадна, энд мэдээж эд нар нь хөрш байх албагүй. P1-ээр T модондээр орших s->t замыг гэж үзье, бас мод байна шүү. Одоо графыхаа бүх w(u, v) ирмэгийн хувьд дараах өөрчлөлтийг хийе. w'(u,v) = w(u,v) − d(s,v) + d(s,u). Ингэхдээ Т модондээр байгаа бүх ирмэгүүдийн жинг 0 байхаар мөн Т модонд харъяалагдахгүй ирмэгүүдийн хувьд сөрөг тоо байхааргүй зохицуулаарай.

Одоо байгаа мэдээллээ ашиглан дахин шинэ граф байгуулая. Шинэ граф нь s-рүү орсон ирмэгийг хасна, мөн P1 модонд харьяалагдаж байгаа 0 утгатай ирмэгүүдийн хувьд чиглэлийг нь урвуулна.

Шинэ граф дээрээ дахин s-ээс эхлэн дахин Дижкстра хийн s->t богино замыг илэрхийлэх модыг олоод P2 гэе. P1 P2 хоюуланд нь харьяалагдах урвуулсан ирмэгийг хасая. Үлдсэн граф бодлогын хариу! энд 0 урттай цикл оршин байж болно. Бодлогын бүтэн хариу утга юу байх вэ? үүнийг уншигчдад үлдээе.


UPDATE
Жишээ болгон алгоритмын ажиллах процессыг доорх зурган жишээгээр харууллаа. Одоо бүр ойлгомжтой байх.



Бодлогыг ЭНД дарж бодно уу.

Нэгэнд энэ пост маань урсгалаар эхэлсэн учир энэ бодлогыг урсгалаар бодогдож болно, би гэхдээ одоо постоо үргэлжлүүлж чадахгүй нь, бодоход туслах нэг санаа нэмээд дараагийн урсгалын жишээ бодлогууд, нэмэлт сайжруулалт дээр бодолтыг тайлбарлая.


Vk гэсэн орой бүрийн хувьд (Vk(in) -> Vk(out)) гэсэн өөрчлөлт хийн графаа өргөтгөөд үз, ийм техник ер нь бол огтлож болохгүй гэсэн хязгаарлалтад тусладаг.



Жич: Монголоороо алдаатай бичсэн бол уучлаарай.

2014 оны улсын мэдээлэл зүйн олимпиадын 2 ын даваа багш нарын бодлогууд

За сайн байцгаана уу, багш нарын бодлогийн анализийг хийх гэж үзлээ хэхэ

Бодлогуудын өгүүлбэрийг энд дараад харж болно.



Эхний бодлого "Геометр прогресс" -ийн хувьд (1<=k<m<=100)  тул k аас m дүгээр тоонуудаа үүсгэж байгаад өгөгдсөн N ширхэг тооноосоо хайгаад тоолж болно. N<=100000 тул шууд хайхад амжина. Гэхдээ N тоонуудаа эрэмбэлж байгаад бинар хайлт хийгээд тоолвол илүү хурдасна. Бичсэн source оо хамт хийв.

#include<cstdio>
#include<algorithm>
#include<vector>
#include<cmath>

using namespace std;

long long member, A[100005];
int n, b, q, k, m, sum, i;

bool search(long long num)
{
  int x, y, z;    
   
  x = 0;
  y = n-1;
  while (x <= y)
  {
    z = (x+y)/2;
    if (A[z] == num) return 1;
    if (num < A[z]) y = z-1;
      else x = z+1;  
  }  
  return 0;
}

main()
{
  freopen("geometer.in", "r", stdin);
  freopen("geometer.out", "w", stdout);
 
  scanf("%d %d %d",&n,&b,&q);
  scanf("%d %d",&k,&m);
  for (i=0; i<n; i++)
    scanf("%lld",&A[i]);
  sort(A,A+n);
  member = b;
  for (i=2; i<=k; i++)
    member = member*q;
 
  sum = 0;
  for (i=k; i<=m; i++)
  {
    if (search(member)) sum++;
    member = member*q;
    if (member > A[n-1]) break;
  }
  printf("%d\n",sum);

}

Дараагийн бодлого "16 суурьтай палиндром тоо" -н дээр өгөгдсөн тоон дээрээ 1 ээс эхлээд ижил хэмжээгээр нэмж үүссэн тоогоо 16 тын тооллын системд шилжүүлээд палиндром эсэхийг шалгаад дараа нь хасч шалгаад явахад  хугацаандаа амжина гэж бодож байна.

Жишээ нь : n тоо өгөгдөх үед n+1 -ийг шалгаад дараа нь n-1 ииг шалгаад дараа нь n+2 , n-2 , n+3 гэх мэт шалгаад хамгийн эхэнд бодлогийн нөхцөлийг хангасан нь манай шийд болно гэсэн үг.

#include<cstdio>
#include<algorithm>
#include<vector>
#include<cmath>

using namespace std;

vector <int> a;    

bool checker(int x)
{
  int i, l;
  a.clear();
  while (x != 0)   
  {
    a.push_back(x%16);    
    x = x/16;
  }
  l = a.size();
  for (i=0; i<l/2; i++)
    if (a[i] != a[l-i-1]) return 0;
  return 1;  
}

main()
{
  int i, t, num, j;      
      
  freopen("palind16.in", "r", stdin);
  freopen("palind16.out", "w", stdout);

  scanf("%d", &t);
  for (i=1; i<=t; i++)  
  {
    scanf("%d", &num);  
    j = -1;
    while (i)
    {
      j++;
      if (checker(num+j)) { printf("%d\n", num+j); break;}
      if (checker(num-j) && num-j>0) { printf("%d\n", num-j); break;}
    }
  }
}

Сүүлчийн бодлого "Битийн дараалал" - ын хувьд DP хэрэглэж бодож болно. A[0][i] гэдэг нь 0 оор төгссөн i урттай дарааллын тоо ба A[1][i] нь 1 ээр төгссөн i урттай дарааллын тоог хадгалдаг гэж үзъе. Эндээс манай хариу A[0][N]+A[1][N] байна гэсэн үг. A[0][i] нь i-1 урттай 0 ээр төгссөн боломжуудын ард 0 ийг нэмж боломж үүсгэж болно. Мөн i-1 урттай 1 ээр төгссөн боломжуудын ард 0 ийг нэмж боломж үүсгэж ба эндээс боломж давхардаж тоологдохгүй нь харагдаж байна. Иймд A[0][i]=A[0][i-1]+A[1][i-1] гэсэн үг. Харин A[1][i] нь i-1 урттай 0 ээр төгссөн боломжуудын ард 1 ийг нэмж боломжуудыг үүсгэж болно. Харин i-1 урттай 1 ээр төгссөн боломжуудын ард 1 нэмж боломж үүсгэж болохгүй. Учир нь бодлогийн нөхцөлд 1 -ийн цифр дараалж орж болохгүй. Иймд A[1][i]=A[0][i] гэсэн үг. Эндээс бичээд үзэхэд N тооны хувьд бодлогийн хариу N+2 дахь фибоначчийн харагдана. Гэхдээ (1<=N<=100) тул урт тооны үйлдэл хийнэ.

#include<cstdio>
#include<algorithm>
#include<vector>
#include<cmath>

using namespace std;

int A[3][50]={0}, n, i, j, i0, i1, i2, d, dig0, dig1, dig2, r, ii;

main()
{
  freopen("bit.in", "r", stdin);
  freopen("bit.out", "w", stdout);
  
  scanf("%d",&n);
  
  A[0][0] = 1; dig0 = 0;
  A[1][0] = 1; dig1 = 0;
  i0 = 0; i1 = 1; i2 = 2;
  for (i=0; i<n; i++)
  {
    r = 0;
    dig2 = max(dig0, dig1);
    for (j=0; j<=dig2; j++)  
    {
      A[i2][j] = (A[i1][j] + A[i0][j] + r)%10;
      r = (A[i1][j] + A[i0][j] + r)/10;  
    }
    if (r) { dig2++; A[i2][dig2]=r; }
    ii = i0; i0 = i1; i1 = i2; i2= ii;
    d = dig0; dig0 = dig1; dig1 = dig2; dig2 = d;
  }
  for (i = dig1; i>=0; i--)
    printf("%d",A[i1][i]);
}

Анх удаагаа анализ хийж байгаа болхоор алдаа гаргасан байж магад .

Бичсэн Б. Гантүшиг ;)