Мод

Энэ удаагийхаа постоор модны бодлогын талаар зөвлөмж өгөөд, IOI 2010 - Traffic Congestion, Модтой тоглоё 1 мөн дараагийн постуудад IOI 2011 Race, IOI 2009 Region зэрэг бодлогуудын бодолтыг бас бусад бодолтуудын хамт заахыг хичээе.



Модны бодлого ихэвчлэн Динамик Програмчлал, Рекурс, Гүний нэвтрэлт, Divide and Conquer-аар бодогддог. Тэгээд хамгийн чухал зүйл бол Рекурсыг маш сайн ойлгосон байх хэрэгтэй. Рекурсын буцал, дуудалтыг ашиглан маш гоё бодолт, мөн том том алгоритмууд бичигддэг.

Модыг эхлээд аль нэг оройгоос нь өлгөөд доош нь цувуулсан байдалтай төсөөлөх хэрэгтэй, үүнийг бид Rooted Tree гэдэг. Чанар ёсоор аль ч оройгоос өлгөсөн ялгаагүй. Жишээ нь доорх модыг 3 гэсэн оройгоос нь өлгөсөн байна.

 За шууд дараах 2 бодлого дээр бодолт хийе:

Модтой тоглоё 1:

Бидэнд чиглэлгүй, жинтэй мод өгөгдсөн бол модны жинг ол. Энд замын жин гэж тухайн зам дээр байгаа бүх ирмэгүүдын жингүүдийн үржвэр. Харин модны жин гэж бүх хос оройг холбох замуудын жингийн нийлбэрийг хэлнэ. Хариуг 10^9+7 жиш. Бүтэн өгүүлбэрийг эндээс уншиж болно.

Дээрх жишээнд бид Х гэсэн оройн хоёр дэд модын жингүүдийг олчихсон тус тус w1, w2 гэж үзье. Тэгвэл одоо Х орой орсон бүх замуудын жинг олохын тулд дараах 3-н тохиолдлыг авч үзнэ. Х орой зүүн дэд модонд орсон бүх замуудын, мөн баруун дэд модонд орсон, мөн 2 дэд модонд хоюуланд нь орсон гэж тус тусад нь олоод нэмэхэд бодлогын хариу гарна.

Х орой зүүн дэд модонд оросн замуудтай хариуг сонирхоё. w1*c1, баруун дэд модны хувьд w2*c2, хоюуланд нь орсон гэвэл w1*w2*c1*c2. Бүтэн бодлогын хариу w1*c1+w2*c2+w1*w2*c1*c2. Код-оо бичихдээ дараахь зохицуулалтыг хийе. dp[i]-ээр i орой орсон замуудын жин ба мэдээж i оройн доор орших модонд харгалзах. Дээрх жишээн хувьд w1*c1+w2*c2 нийлбэрийг хадгалж байна гэсэн үг. dfs(i) функц маань i үндэстэй дэд мод болгоны хувьд жинхэнэ хариу буюу дээрх жишээн хувьд w1*c1+w2*c2+w1*w2*c1*c2 нийлбэрийг хадгална. Тэгэхээр бодлогын хариу бүх дэд модны хувьд нийлбэр гарна. Мэдээж энэ бүх үйлдэлүүд дурын оройгоос рекурс дуудалт хийсний дараа буюу рекурс буцалт хийх үед хийгдэнэ. Дээрх тохиолдолд би дээр зөвхөн жишээ авсан ба орой бүрийн хувьд 2 зангилаатай байна гэж байхгүй. Тэгэхээр рекурс дуудалт бүрт бодолт хийнэ гэсэн үг. C++ код:

#define mp make_pair
#define pb push_back
using namespace std;
long long toint(string s) { istringstream in(s); long long x; in>>x; return x; }
template<class T> string tostring(T x) { ostringstream out; out<<x; return out.str();}
vector< pair<int, int> >v[100010];
long long dp[100010];
long long dfs(int dad, int child){
    long long ret = 0;
    dp[child]=1ll;
    for(vector< pair<int, int> >::iterator it=v[child].begin(); it!=v[child].end(); it++){
        int u = it->first;
        if(dad==u)continue;
        ret = (ret + dfs(child, u))%1000000007;
        long long subtree = (dp[u]*it->second)%1000000007;
        ret = (ret + (dp[child]*subtree)%1000000007)%1000000007;
        dp[child] = (dp[child] + subtree)%1000000007;
    }
    return ret;
}
int main(int argc, char *argv[]) {
   //freopen("mtree.in", "r", stdin);
   //freopen("mtree.out", "w", stdout);
   int n;
   scanf("%d", &n);
   for(int i=0; i<n-1; i++){
      int a, b, c;
      scanf("%d%d%d", &a, &b, &c);
      a--, --b;
      v[a].pb( mp(b, c) );
      v[b].pb( mp(a, c) );
   }
   printf("%I64d\n", dfs(-1, 0));
return 0;
}

IOI 2010 - Traffic Congestion: Монгол өгүүлбэрийг эндээс

Модоо мөн л Rooted Tree болгоё. dp[i]-ээр i дугаар орой дээр цэнгэлдэхийг барьсан гэвэл үүсэж болох хагмийн их замын түгжрээг тэмдэглэе. Бүх оройн хувьд олж чадвал эдгээрийн хамгийн бага нь хариу болно. m-ээр i орой эцэг нь болох бүх моднуудын гарч болох замын түгжрэлийн нийлбэрийг хадгалая. Үүнийг юун ашиглах болохыг доорх зургаар харуулая:

 C++ code:

#define mp make_pair
#define pb push_back
using namespace std;
long long toint(string s) { istringstream in(s); long long x; in>>x; return x; }
template<class T> string tostring(T x) { ostringstream out; out<<x; return out.str();}
vector<int>fans;
vector<int>v[1000010];
int dp[1000010];
int sum;
int dfs(int dad, int child){
    int m=0;//
    int ret = fans[child];
    for(int i=0; i<v[child].size(); i++){
        int u = v[child][i];
        if(u==dad)continue;
        int temp = dfs(child, u);
        m = max(m, temp);
        ret += temp;
    }
    m = max(m, sum-ret);
    dp[child] = m;
    return ret;
}
int main(int argc, char *argv[]) {
    int n;
    freopen("traffic.in", "r", stdin);
    freopen("traffic.out", "w", stdout);
    scanf("%d", &n);
    for(int i=0; i<=n; i++){
       int t;
       scanf("%d", &t);
       sum += t;
       fans.pb(t);
    }
    for(int i=0; i<=n; i++){
       int x, y;
       scanf("%d%d", &x, &y);
       v[x].pb(y);
       v[y].pb(x);
    }
    dfs(-1, 0);
    for(int i=0; i<=n; i++)printf("%d\n", dp[i]);
//system("pause");
return 0;
}

Тайлбарлахад их төвөгтэй байнаа. Ойлгомжгүй байвал уучлаарай. IOI бэлдэж байгаа хүүхдүүдэд зөвлөхөд Codeforces, topcoder-н графуудыг эхлээд дуусгаачээ :)