洛谷P4068 數字配對

2022-09-23 02:21:58 字數 1349 閱讀 7671

有 \(n\) 種數字,第 \(i\) 種數字是 \(a_i\)、有 \(b_i\) 個,權值是 \(c_i\)。

若兩個數字 \(a_i\)、\(a_j\) 滿足,\(a_i\) 是 \(a_j\) 的倍數,且 \(\frac\) 是一個質數,

那麼這兩個數字可以配對,並獲得 \(c_i \times c_j\) 的價值。

一個數字只能參與一次配對,可以不參與配對。

在獲得的價值總和不小於 0 的前提下,求最多進行多少次配對。

我們把每一個數字按照分解質因數後質因子(不去重)的數量的奇偶性分為兩類,顯然同一類中的任意兩個數字不能配對,因為他們的商一定有偶數個質因子,所以商一定不是質數。

那麼這兩個集合就是一個二分圖。我們考慮如下構建:

接下來跑最大費用最大流即可。最大流即為答案。

但是這個費用流與一般的費用流有所不同,因為一般的費用流要求是費用最大/小的時候的最大流,而此題要求“價值總和不小於 0”,也就是費用不小於 0 時的最大流。

顯然每一次增廣時的最長路不超過上一次增廣的最長路,如果這條最長路長度非負,那麼顯然越多越好;否則肯定要在費用不小於 0 的前提下越大越好,因為後面的增廣最長路會更短,所以收益更小。

#include #include #include #include using namespace std;

typedef long long ll;

const int n=210,m=6e5,inf=1e9;

int a[n],b[n],c[n],head[n],p[n],pre[n];

int n,s,t,tot=1;

ll maxflow,cost,dis[n];

bool vis[n];

struct edge

e[m];

void add(int from,int to,int flow,ll cost)

bool spfa()

bool addflow()

maxflow+=minflow;

cost+=minflow*dis[t];

}void mcmf()

}int main()

for (int i=1;i<=n;i++)

for (int j=1;j<=n;j++)

if ((p[i]&1) && abs(p[i]-p[j])==1 && (!(a[i]%a[j]) || !(a[j]%a[i])))

add(i,j,inf,1ll*c[i]*c[j]),add(j,i,0,-1ll*c[i]*c[j]);

mcmf();

printf("%lld\n",maxflow);

return 0;

}

P4068 SDOI2016 數字配對

洛谷 有 n 個數字,每個數字的權值為 a i 有 b i 個,價值為 c i 。 如果 a i 是 a j 的倍數,且 a i a j 為...

p4068 SDOI2016 數字配對

傳送門 分析 我們考慮對所有a i 質因數分解,然後記cnt i 為a i 是由幾個質數相乘得到的 然後我們建一個二分圖,左面為所有cnt i 為奇數的點,右面是為偶數的點 我們從源點向左麵點連容量b i 花費0的邊,從右面點向匯點連容量b i 花費0的邊 然後兩排點之間符合條件的點對連容量inf花...

洛谷p1009

用高精度計算出s 1 2 3 n n 50 其中 表示階乘,例如 5 5 4 3 2 1。 一個正整數n。 一個正整數s,表示計算結果。 輸...