staza.cpp

Bài toán

Độ phức tạp

Code này của Nguyễn Tiến Trung Kiên

#include <stdio.h>

#include <string.h>

#include <stack>

#include <vector>

#include <algorithm>

using namespace std;

bool minimize(int &a, int b){ if (a>b) a=b; else return false; return true; }

bool maximize(int &a, int b){ if (a<b) a=b; else return false; return true; }

int n, m;

vector<int> a[12309];

int n_prstena;

vector<int> prsten[12309];

vector<int> prsteni[12309];

vector<int> mostovi[12309];

int travesal_time;

int discover[12309];

int lowlink[12309];

stack<int> st;

void visit(int u, int parent){

   int i, v;

   discover[u] = ++travesal_time;

   lowlink[u] = discover[u];

   st.push(u);

   for (i=0; v=a[u][i]; i++)

   if (v!=parent){

      if (discover[v]!=0) minimize(lowlink[u], discover[v]);

      else {

         visit(v, u);

         if (lowlink[v] < discover[u])

            minimize(lowlink[u], lowlink[v]);

         else if (lowlink[v]==discover[u]){

            n_prstena++;

            prsteni[u].push_back(n_prstena);

            do {

               prsten[n_prstena].push_back(st.top());

               st.pop();

            } while (prsten[n_prstena].back() != v);

         }

         else {

            mostovi[u].push_back(st.top());

            st.pop();

         }

      }

   }

}

int memo[12309][2];

#define STAZA 0

#define DJIR 1

int rec(int X, int sto_racunam){

   int profit=0, i, j;

   int &r = memo[X][sto_racunam];

   if (r>=0) return r; else r=0;

   for (i=0; i<mostovi[X].size(); i++)

   maximize(profit, 1+rec(mostovi[X][i], STAZA));

   for (i=0; i<prsteni[X].size(); i++){

      vector<int> &P = prsten[prsteni[X][i]];

      int best = 0;

      int smjer1=1, smjer2=1;

      int ciklus = P.size()+1;

      for (j=0; j<P.size(); j++){

         maximize(best, smjer1 + rec(P[j], STAZA));

         smjer1 += 1 + rec(P[j], DJIR);

         maximize(best, smjer2 + rec(P[P.size()-j-1], STAZA));

         smjer2 += 1 + rec(P[P.size()-j-1], DJIR);

         ciklus += rec(P[j], DJIR);

      }

      r += ciklus;

      maximize(profit, best-ciklus);

   }

   if (sto_racunam==STAZA) r += profit;

   return r;

}

main(){

   int i, p, q;

   scanf("%d%d", &n, &m);

   for (i=1; i<=m; i++){

      scanf("%d%d", &p, &q);

      a[p].push_back(q);

      a[q].push_back(p);

   }

   for (i=1; i<=n; i++) a[i].push_back(0);

   visit(1,0);

   memset(memo, -1, sizeof memo);

   printf("%d\n", rec(1,0));

}

Nhận xét