2015プログラミングの美初試合第1試合C質数関連
時間制限:
2000ms
単一点時限:
1000ms
メモリの制限:
256MB
説明
2つの数aとb(a入力
第1の動作は、データ群数である数Tである.その後、各グループのデータには2行が含まれます.
第1の挙動Nは、集合Sの大きさである.第2の挙動N個の整数は、集合内の数を表す.
しゅつりょく
「Case#X:Y」のように、データのセットごとに1行出力します.Xはデータ番号であり、1からYは最大のサブセットのサイズである.
データ範囲
1 ≤ T ≤ 20
集合S内の数は2つ異なり、1〜500000の範囲である.
ミニデータ
1 ≤ N ≤ 15
ビッグデータ
1 ≤ N ≤ 1000
サンプル入力
サンプル出力
2.解題の考え方:本題は最大ストリームを利用して解決する.まず、すべての質量数に関連する数を見つけることができます.ここではss配列でマークします.次は図面作成プロセスです.数値a[i]が素数に関連している場合、iとソース点sとの間にエッジが接続される.そうでなければ、それと合流点tとの間にエッジを接続します.次に、数値a[i]=a[j]*p、またはa[j]=a[i]*pが見つかった場合、iとjの間にエッジが接続される.すべてのエッジの容量は1です.次に,この図について最大ストリームを解く.最小割合最大流の定理を用いて,n−maxflow()は質量数に関係なく点数が最も多いサブセットであることが分かった.
3.コード:
時間制限:
2000ms
単一点時限:
1000ms
メモリの制限:
256MB
説明
2つの数aとb(a
第1の動作は、データ群数である数Tである.その後、各グループのデータには2行が含まれます.
第1の挙動Nは、集合Sの大きさである.第2の挙動N個の整数は、集合内の数を表す.
しゅつりょく
「Case#X:Y」のように、データのセットごとに1行出力します.Xはデータ番号であり、1からYは最大のサブセットのサイズである.
データ範囲
1 ≤ T ≤ 20
集合S内の数は2つ異なり、1〜500000の範囲である.
ミニデータ
1 ≤ N ≤ 15
ビッグデータ
1 ≤ N ≤ 1000
サンプル入力
3
5
2 4 8 16 32
5
2 3 4 6 9
3
1 2 3
サンプル出力
Case #1: 3
Case #2: 3
Case #3: 22.解題の考え方:本題は最大ストリームを利用して解決する.まず、すべての質量数に関連する数を見つけることができます.ここではss配列でマークします.次は図面作成プロセスです.数値a[i]が素数に関連している場合、iとソース点sとの間にエッジが接続される.そうでなければ、それと合流点tとの間にエッジを接続します.次に、数値a[i]=a[j]*p、またはa[j]=a[i]*pが見つかった場合、iとjの間にエッジが接続される.すべてのエッジの容量は1です.次に,この図について最大ストリームを解く.最小割合最大流の定理を用いて,n−maxflow()は質量数に関係なく点数が最も多いサブセットであることが分かった.
3.コード:
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<string>
#include<sstream>
#include<set>
#include<vector>
#include<stack>
#include<map>
#include<queue>
#include<deque>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<ctime>
#include<functional>
using namespace std;
int ss[510000], T, a[1100];
bool prime[510000];
#define INF 1000000000
#define min(x, y) ((x) < (y) ? (x) : (y))
int n, m, i, q, h, mid, len, s, t, till[3100000], go[3100000], Next[3100000], f[3100000], D[3100000], n1[3100000];
bool cc[3100000];
void add(int x, int y, int z) {
Next[++len] = till[x];
till[x] = len;
go[len] = y;
f[len] = z;
}
void Ad(int x, int y, int z) {
add(x, y, z);
add(y, x, 0);
}
bool bfs() {
int q, h, i;
memset(D, 0, sizeof D);
memset(cc, 1, sizeof cc);
for (D[n1[q = h = 1] = s] = 1; q <= h; q++)
for (i = till[n1[q]]; i; i = Next[i])
if (f[i] && !D[go[i]]) D[n1[++h] = go[i]] = D[n1[q]] + 1;
return D[t];
}
int dfs(int k, int mi) {
if (k == t) return mi;
int i, tmp, sum = 0;
for (i = till[k]; i && mi; i = Next[i])
if (f[i] && D[go[i]] == D[k] + 1 && cc[go[i]]) {
tmp = dfs(go[i], min(mi, f[i]));
sum += tmp;
mi -= tmp;
f[i] -= tmp;
f[i ^ 1] += tmp;
}
if (!sum) cc[k] = false;
return sum;
}
int maxFlow() {
int sum = 0;
while (bfs()) sum += dfs(s, INF);
return sum;
}
int main()
{
freopen("t.txt", "r", stdin);
ss[1] = 0;
for (int i = 2; i <= 500000; i++)//
prime[i] = true;
for (int i = 2; i <= 500000; i++) {
for (int j = i + i; j <= 500000; j += i) prime[j] = false;
}
for (int i = 1; i <= 500000; i++)
for (int j = 1; j <= 500000 / i; j++)
if (prime[j]) ss[i * j] = 1 - ss[i];// 1
scanf("%d", &T);
for (int mm = 1; mm <= T; mm++) {
printf("Case #%d: ", mm);
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
len = 1;
s = 0;//
t = n + 1;//
for (int i = 0; i <= n + 1; i++)
till[i] = 0;
for (int i = 1; i <= n; i++)
if (ss[a[i]]) Ad(0, i, 1);// a[i] ， i
else Ad(i, n + 1, 1);// ，i
for (int i = 1; i <= n; i++)
if (ss[a[i]])
for (int j = 1; j <= n; j++)
if (!ss[a[j]]) {
if (a[i] > a[j]) {
if (a[i] % a[j] == 0 && prime[a[i] / a[j]]) Ad(i, j, 1);// a[i] a[i]/a[j]， i j
}
else {
if (a[j] % a[i] == 0 && prime[a[j] / a[i]]) Ad(i, j, 1);
}
}
printf("%d
", n - maxFlow());// Dinic ， ，
}
}