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(){
}

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;
}

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 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;

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));

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

int u, v;
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;
}
}

}
}

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;
}