解題區/解題區 - UVa

UVa 11985 - Prime Independence

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

給 N 個數字，找到最大子集滿足任 A, B 數字，A 不為 B 的質數倍。

Sample Input

1
2
3
4
5
6
7
3
5
2 4 8 16 32
5
2 3 4 6 9
3
1 2 3

Sample Output

1
2
3
Case 1: 3
Case 2: 3
Case 3: 2

Solution

看起來就是一個二分圖找最大獨立集，但是建造的速度要夠快，少說也要 500 ms，然後在二分匹配上必須採用很快速的最大流，這裡採用 dinic 版本，網路上搜索到這個版本挺不錯的。

為了遇見妳，已經撒了無數 TLE。
求到妳接受的那個瞬間，神啊！謝謝祢的禮物才讓我們相遇。

對於最大流算法，一般而言會經過不斷地溯洄沖減， Dinic 分層圖的方式進行計算，但是可以利用指針對於每個節點進行記錄，在沖減時，對指針結果的下一條邊進行計算，而不對於每一個點的所有邊重頭來過。

接著，分層圖可以利用沖減時，進行計算，即當找到瓶頸時，更新該點的層次。取代一般重新使用 bfs 的分層計算。

最大獨立集 = 點數 - 最大匹配數。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <queue>
#include <stack>
#include <assert.h>
#include <set>
using namespace std;
const int MAXV = 40010;
const int MAXE = MAXV * 200 * 2;
const int INF = 1<<29;
typedef struct Edge {
    int v, cap, flow;
    Edge *next, *re;
} Edge;
class MaxFlow {
    public:
    Edge edge[MAXE], *adj[MAXV], *pre[MAXV], *arc[MAXV];
    int e, n, level[MAXV], lvCnt[MAXV], Q[MAXV];
    void Init(int x) {
        n = x, e = 0;
        for (int i = 0; i < n; ++i) adj[i] = NULL;
    }
    void Addedge(int x, int y, int flow){
        edge[e].v = y, edge[e].cap = flow, edge[e].next = adj[x];
        edge[e].re = &edge[e+1], adj[x] = &edge[e++];
        edge[e].v = x, edge[e].cap = 0, edge[e].next = adj[y];
        edge[e].re = &edge[e-1], adj[y] = &edge[e++];
    }
    void Bfs(int v){
        int front = 0, rear = 0, r = 0, dis = 0;
        for (int i = 0; i < n; ++i) level[i] = n, lvCnt[i] = 0;
        level[v] = 0, ++lvCnt[0];
        Q[rear++] = v;
        while (front != rear){
            if (front == r) ++dis, r = rear;
            v = Q[front++];
            for (Edge *i = adj[v]; i != NULL; i = i->next) {
                int t = i->v;
                if (level[t] == n) level[t] = dis, Q[rear++] = t, ++lvCnt[dis];
            }
        }
    }
    int Maxflow(int s, int t){
        int ret = 0, i, j;
        Bfs(t);
        for (i = 0; i < n; ++i) pre[i] = NULL, arc[i] = adj[i];
        for (i = 0; i < e; ++i) edge[i].flow = edge[i].cap;
        i = s;
        while (level[s] < n){
            while (arc[i] && (level[i] != level[arc[i]->v]+1 || !arc[i]->flow)) 
                arc[i] = arc[i]->next;
            if (arc[i]){
                j = arc[i]->v;
                pre[j] = arc[i];
                i = j;
                if (i == t){
                    int update = INF;
                    for (Edge *p = pre[t]; p != NULL; p = pre[p->re->v])
                        if (update > p->flow) update = p->flow;
                    ret += update;
                    for (Edge *p = pre[t]; p != NULL; p = pre[p->re->v])
                        p->flow -= update, p->re->flow += update;
                    i = s;
                }
            }
            else{
                int depth = n-1;
                for (Edge *p = adj[i]; p != NULL; p = p->next)
                    if (p->flow && depth > level[p->v]) depth = level[p->v];
                if (--lvCnt[level[i]] == 0) return ret;
                level[i] = depth+1;
                ++lvCnt[level[i]];
                arc[i] = adj[i];
                if (i != s) i = pre[i]->re->v;
            }
        }
        return ret;
    }
} g;
#define MAXL (500000>>5)+1
#define GET(x) (mark[x>>5]>>(x&31)&1)
#define SET(x) (mark[x>>5] |= 1<<(x&31))
int mark[MAXL];
int P[100000], Pt = 0;
vector<int> pfactor[524288];
int A[MAXV], RE[524288], XY[524288];
void sieve() {
    register int i, j, k;
    SET(1);
    int n = 500000;
    for(i = 2; i <= n; i++) {
        if(!GET(i)) {
            XY[i] = 1;
//			for(k = n/i, j = i*k; k >= i; k--, j -= i)
//				SET(j);
            for (j = i+i; j <= n; j += i)
                SET(j), XY[j] = XY[j/i] + 1, pfactor[j].push_back(i);
            pfactor[i].push_back(i);
            P[Pt++] = i;
        }
    }
}
int main() {
    sieve();
    int testcase, cases = 0;
    int n, x;
    scanf("%d", &testcase);
    while (testcase--) {
   		scanf("%d", &n);
   		memset(RE, -1, sizeof(RE));
   		for (int i = 0; i < n; i++) {
   			scanf("%d", &A[i]);
   			RE[A[i]] = i;
   		}
   		g.Init(n + 2);
   		int source = n, sink = n + 1;
   		for (int i = 0; i < n; i++) {
   			if (XY[A[i]]&1)
   				g.Addedge(source, i, 1);
   			else
   				g.Addedge(i, sink, 1);
   			for (int j = 0; j < pfactor[A[i]].size(); j++) {
   				int y = A[i] / pfactor[A[i]][j];
   				if (RE[y] != -1) {
   					if (XY[y]&1)
   						g.Addedge(RE[y], i, 1);
   					else
   						g.Addedge(i, RE[y], 1);
   				}
   			}
   		}
   		printf("Case %d: %d\n", ++cases, n - g.Maxflow(source, sink));
   	}
    return 0;
}
/*
3
5
2 4 8 16 32
5
2 3 4 6 9
3
1 2 3
1000
3
7 35 105
*/