HDU 3071. Gcd & Lcm game(RE)

http://acm.hdu.edu.cn/showproblem.php?pid=3071

#include 
#include 
using namespace std;
const int P[] = {2,2,2,2,2,2,3,3,3,3,5,5,7,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};
const int N = 205011, M = 35;

int l[2*N-1], r[2*N-1];
long long gcd_key[2*N-1]; long long lcm_key[2*N-1];
int left_child[2*N-1], right_child[2*N-1];
int parent[2*N-1]; int total, root;
int bottom[N];  int n, m;
long long num[N];

int a, b ,c, p; long long gcd, lcm;


long long f(int a){
    long long x = 0, y = 1;
    for (int i=0;i<35;i++,y<<=1){
        if (a%P[i]==0){
            x|=y; a/=P[i];
        }
    }
    return x;
}

int g(long long x){
    int a = 1; long long y = 1;
    for (int i=0;i<35;i++,y<<=1){
        if ((x&y)!=0){
            a = (a * P[i]) % p;
            x &=~ y;
        }
    }
    return a;
}



void updata(int now){
    gcd_key[now] = gcd_key[left_child[now]] & gcd_key[right_child[now]];
    lcm_key[now] = lcm_key[left_child[now]] | lcm_key[right_child[now]];
}

void query_gcd(int now){
    if (a<=l[now]&&r[now]<=b){
        gcd = gcd & gcd_key[now];
        return;
    }

    int m = (l[now]+r[now])/2;
    if (a<=m) query_gcd(left_child[now]);
    if (m< b) query_gcd(right_child[now]);
}
void query_lcm(int now){
    if (a<=l[now]&&r[now]<=b){
        lcm = lcm | lcm_key[now];
        return;
    }

    int m = (l[now]+r[now])/2;
    if (a<=m) query_lcm(left_child[now]);
    if (m< b) query_lcm(right_child[now]);
}

void modify(){
    int now = parent[bottom[a]];
    while (now!=-1){
        updata(now); now = parent[now];
    }
}


void build(int &now, int a, int b){
    now = total++;
    l[now] = a; r[now] = b;
    if (a==b){
        gcd_key[now] = lcm_key[now] = num[a];
        bottom[a] = now;
    }
    else {
        int m = (a+b)/2;
        build(left_child[now],a ,m); build(right_child[now],m+1 ,b);
        parent[left_child[now]] = now; parent[right_child[now]] = now;
        updata(now);
    }
}







void init(){
    int a;
    for (int i=1;i<=n;i++){
        scanf("%d", &a); num[i] = f(a);
    }
    total = 0;
    build(root,1,n);
}



int main(){
    //p = 100; cout << g(f(97)) << endl;
    parent[0] = -1; char ch;

    while(scanf("%d%d",&n, &m) == 2){
        init();
        while (m--){
            scanf(" %c", &ch);
            switch(ch){
                case 'C':
                    scanf("%d%d%d",&a, &b);
                    gcd_key[bottom[a]] = lcm_key[bottom[a]] = num[a] = f(b);
                    modify();
                break;
                case 'G':
                    scanf("%d%d%d",&a ,&b, &p);gcd = num[a];
                    query_gcd(root);
                    printf("%d\n", g(gcd));
                break;
                case 'L':
                    scanf("%d%d%d",&a, &b, &p);lcm = num[a];
                    query_lcm(root);
                    printf("%d\n", g(lcm));
            }
        }
    }
}

最大流。。。。

I. Fold-Forkson Method

As long as there is an open path through the residual graph, send the minimum of the residual capacities on the path.

1. First, We use a general dfs to find the augmenting path.
2. When we finding augmenting paths with breadth-first search. Things get changed. && we got .. Edmonds_Karp Algorithm .

/*
    ID: xiaodao
    PROG: ditch
    LANG: CPP
*/

#include 
#include 
using namespace std;
const int INF = 1000000;
const int N = 1001;
int stack[N], top; //Stack..
bool visited[N];

int C[N][N], F[N][N]; // Capacity, Flow..
int n, m, ans;

inline void push(int x){
    //cout << x << endl;
    stack[++top] = x;
    visited[x] = true;
}

inline void pop(){
    visited[stack[top]] = false;
    top--;
}

inline bool empty(){
    return top==-1;
}



void stat(){
    ans = 0;
    for (int i=2;i<=n;i++)
        ans += F[1][i];
}





bool find_path(){
    int cur[N];
    memset(visited, false, sizeof(visited));
    for (int i=1;i n) pop();
        else{
            push(v);
            if (v == n) return true;
            cur[u] = v + 1;
        }
    }

    return false;
}

void add_path(){
    int u, v; int delta = INF;

    for (int i=0;i> m >> n;
    int x, y, c;
    for (int i=1;i<=m;i++){
        scanf("%d%d%d", &x, &y, &c);
        C[x][y] += c;
    }
}



int main(){
freopen("ditch.in","r",stdin);
freopen("ditch.out","w",stdout);
    init(); dfs_method();
    cout << ans << endl;
}
/*
    ID: xiaodao
    PROG: ditch
    LANG: CPP
*/

#include 
#include 
using namespace std;
const int INF = 1000000;
const int N = 1001;
struct rec{
    int v, p, k;
    // Vertex, Parient ,key
};
int C[N][N], F[N][N]; // Capacity, Flow..
bool V[N]; rec Q[N]; // Visited, Queue..
int head, tail;
int n, m, ans;

bool find_path(){
    memset(V, false, sizeof(V));
    Q[0].v = 1; Q[0].k = INF; V[1] = true;
    head = 0; tail = 1;
    int u, v;

    while (head> m >> n;
    int x, y, c;
    for (int i=1;i<=m;i++){
        scanf("%d%d%d", &x, &y, &c);
        C[x][y] += c;
    }
}

int main(){
freopen("ditch.in","r",stdin);
freopen("ditch.out","w",stdout);
    init(); Edmonds_Karp();
    cout << ans << endl;
}





II. Dinitz Blocking Flow Method

In each phase the algorithms builds a layered graph with breadth-first search on the residual graph.

/*
    ID: xiaodao
    PROG: ditch
    LANG: CPP
*/

#include 
#include 
#include 
using namespace std;
const int INF = 1000000;
const int N = 1001;
struct rec{
    int v, p, k;
    // Vertex, Key ...
    // Point to key ...
};
int C[N][N], F[N][N]; // Capacity, Flow..
int L[N]; // Leval ...
int n, m, ans;



void stat(){
    ans = 0;
    for (int i=2;i<=n;i++)
        ans += F[1][i];
}

void bfs(){
    memset(L, -1, sizeof(L));

    int Q[N], head, tail;

    head = 0; tail = 1; Q[0]  = 1;
    L[1] = 0;

    int u, v;
    while (headn){
                L[u] = -1;
                top--;
            }
            else{
                cache[u] = v+1; top++;
                stack[top].v = v;
                if (C[u][v] - F[u][v] < stack[top-1].k){
                    stack[top].k = C[u][v] - F[u][v];
                    stack[top].p = top-1;
                }
                else{
                    stack[top].k = stack[top-1].k;
                    stack[top].p = stack[top-1].p;
                }
            }
        }
        bfs();
    }
    stat();
}


void init(){
    memset(C, 0, sizeof(C));
    memset(F, 0, sizeof(F));
    cin >> m >> n;
    int x, y, c;
    for (int i=1;i<=m;i++){
        scanf("%d%d%d", &x, &y, &c);
        C[x][y] += c;
    }
}



int main(){
freopen("ditch.in","r",stdin);
freopen("ditch.out","w",stdout);
    init(); dinic();
    cout << ans << endl;
}





III. Push-Relabel Method.

Since 1976. A New Approach to the Maximum-Flow Problem ...
1. General push-relabel maximum flow algorithm.
2. Push-relabel algorithm with FIFO vertex selection rule...
(Although.. A still have some question between it and the Relabel_to_Frontalgorithm... )

/*
    ID: xiaodao
    PROG: ditch
    LANG: CPP
*/

#include 
#include 
using namespace std;
const int INF = 1000000;
const int N = 1001;
int C[N][N], F[N][N]; // Capacity, Flow..
int H[N], E[N]; // .Height, Excess ...
int n, m, ans;
//bool sign;




void push(int u, int v, int delta){
    F[u][v] += delta; F[v][u] -= delta;
    E[u] -= delta; E[v] += delta;
}

void relabel(int u){
    H[u]++;
}

void discharge(int u){
    for (int v=1;v<=n;v++){
        if (H[u] == H[v] + 1 && F[u][v] < C[u][v]){
            push(u, v, min(E[u], C[u][v] - F[u][v]));
            if (E[u]==0) return;
        }
    }
    relabel(u);
}







void push_relabel(){
    memset(E, 0, sizeof(E));
    memset(H, 0, sizeof(H));
    E[1] = INF; H[1] = n;

    for (int i=2;i<=n;i++){
        if (C[1][i] > 0) {
            push(1, i, C[1][i]);
            if (i!=n) H[i] = 1;
        }
    }


    do{
        //As long as there is legal push or relabel operation
        for (int u=2;u> m >> n;
    int x, y, c;
    for (int i=1;i<=m;i++){
        scanf("%d%d%d", &x, &y, &c);
        C[x][y] += c;
    }
}


int main(){
freopen("ditch.in","r",stdin);
freopen("ditch.out","w",stdout);
    init(); push_relabel();
    cout << E[n] << endl;
}
/*
    ID: xiaodao
    PROG: ditch
    LANG: CPP
*/

#include 
#include 
using namespace std;
const int INF = 1000000;
const int N = 1001;
int C[N][N], F[N][N]; // Capacity, Flow..
int H[N], E[N]; // .Height, Excess ...
int Q[N]; int head, tail; // Queue...
int n, m, ans;



void push(int u, int v, int delta){
    F[u][v] += delta; F[v][u] -= delta;
    E[u] -= delta; E[v] += delta;
}

void relabel(int u){
    /*
    H[u] = INF;
    for (int v=1;v<=n;v++){
        if (F[u][v] < C[u][v])
            H[u] = min(H[u], H[v]+1);
    }
    */
    H[u]++;
}

void discharge(int u){
    for (int v=1;v<=n;v++){
        if (H[u] == H[v] + 1 && F[u][v] < C[u][v]){
            if (v!=n && E[v] == 0) {
                Q[tail] = v;
                tail = (tail + 1) % N;
            }
            push(u, v, min(E[u], C[u][v] - F[u][v]));
            if (E[u] == 0) return;
        }
    }

    Q[tail] = u;
    tail = (tail + 1) % N;
    relabel(u);
}






void push_relabel(){
    memset(E, 0, sizeof(E));
    memset(H, 0, sizeof(H));
    E[1] = INF; H[1] = n;
    head = 0; tail = 0;
    for (int i=2;i<=n;i++){
        if (C[1][i] > 0) {
            push(1, i, C[1][i]);
            if (i!=n) H[i] = 1, Q[tail++] = i;
        }
    }

    while (head!=tail){
        discharge(Q[head]);
        head = (head + 1) % N;
    }
}

void init(){
    memset(C, 0, sizeof(C));
    memset(F, 0, sizeof(F));
    cin >> m >> n;
    int x, y, c;
    for (int i=1;i<=m;i++){
        scanf("%d%d%d", &x, &y, &c);
        C[x][y] += c;
    }
}

int main(){
freopen("ditch.in","r",stdin);
freopen("ditch.out","w",stdout);
    init(); push_relabel();
    cout << E[n] << endl;
}

/*
    ID: xiaodao
    PROG: ditch
    LANG: CPP
*/

#include 
#include 
#include 
using namespace std;
const int INF = 1000000;
const int N = 1001;
int C[N][N], F[N][N]; // Capacity, Flow..
int H[N], E[N]; // .Height, Excess ...
int n, m, ans;
bool changed;



void push(int u, int v, int delta){
    F[u][v] += delta; F[v][u] -= delta;
    E[u] -= delta; E[v] += delta;
}

void relabel(int u){

    /*
    H[u] = INF;
    for (int v=1;v<=n;v++){
        if (F[u][v] < C[u][v])
            H[u] = min(H[u], H[v]+1);
    }*/
    H[u]++;
}

void discharge(int u){
    if (E[u]==0){
        changed = false;
        return;
    }

    changed = true;
    for (int v=1;v<=n;v++){
        if (u == v) continue;
        if (H[u] > H[v] && F[u][v] < C[u][v]){
            push(u, v, min(E[u], C[u][v] - F[u][v]));
            if (E[u]==0) {changed = false; return;}
        }
    }
    relabel(u);
}






void relabel_to_front(){
    //Relabel-to-front algorithm, ie. using FIFO heuristic

    //1.Send as much flow from s as possible.
    memset(E, 0, sizeof(E));
    memset(H, 0, sizeof(H));
    E[1] = INF; H[1] = n;
    for (int i=2;i<=n;i++){
        if (C[1][i] > 0) {
            push(1, i, C[1][i]);
            if (i!=n) H[i] = 1;
        }
    }

    //2.Build a list of all nodes except s and t.
    list L;
    for (int i=2;i::iterator it=L.begin();
    while (it!=L.end()){
        //1.Discharge the current node.
        discharge(*it);
        //2.If the height of the current node changed:
        if (changed){
            L.push_front(*it); L.erase(it);
            it = L.begin();
        }
        else
            it++;
    }
}

void init(){
    memset(C, 0, sizeof(C));
    memset(F, 0, sizeof(F));
    cin >> m >> n;
    int x, y, c;
    for (int i=1;i<=m;i++){
        scanf("%d%d%d", &x, &y, &c);
        C[x][y] += c;
    }
}

int main(){
freopen("ditch.in","r",stdin);
freopen("ditch.out","w",stdout);
    init(); relabel_to_front();
    cout << E[n] << endl;
}

External link :

http://en.wikipedia.org/wiki/Push-relabel_maximum_flow_algorithm
http://www.nocow.cn/index.php/Translate:USACO/ditch

上午参加了高中理科实验班的 “谢师宴” 去了(地点在东大街的尽头,南淝河边上的梦城大酒店。#) ,所谓谢师宴嘛其实呢是希望散伙饭可以有老师来参加^ ^,不过班里面的几位班干为这件事情筹备了好久,(而且我总是隐隐觉得好像过了这一次就再也不能把高中班里的同学再聚到一起了。。)

所以。。。这也是我这次回合肥的原因之一。
ゆっくり読んでください …