You have written on a piece of paper an array of n positive integers a[1], a[2], ..., a[n] and m good pairs of integers (i1, j1), (i2, j2), ..., (im, jm). Each good pair (ik, jk) meets the following conditions: ik + jk is an odd number and 1 ≤ ik < jk ≤ n.
In one operation you can perform a sequence of actions:
Determine the maximum number of operations you can sequentially perform on the given array. Note that one pair may be used several times in the described operations.
Input
The first line contains two space-separated integers n, m (2 ≤ n ≤ 100, 1 ≤ m ≤ 100).
The second line contains n space-separated integers a[1], a[2], ..., a[n] (1 ≤ a[i] ≤ 109) — the description of the array.
The following m lines contain the description of good pairs. The k-th line contains two space-separated integers ik, jk (1 ≤ ik < jk ≤ n, ik + jk is an odd number).
It is guaranteed that all the good pairs are distinct.
Output
Output the answer for the problem.
Examples
3 2
8 3 8
1 2
2 3
0
3 2
8 12 8
1 2
2 3
2
sol：看到两个坐标相加一定是奇数，而且这个数据范围100,100，容易联想到网络流，而且分组就是下标奇偶分成两组。
建图就呼之欲出了，对于每个质因数建一张图，源点S向每个奇数下标连上那个数字中那个质因数个数，同理偶数下标向汇点T连边，对于奇偶之间就连上他们质因数个数的较小值
#include <bits/stdc++.h> using namespace std; typedef int ll; inline ll read() { ll s=0; bool f=0; char ch=‘ ‘; while(!isdigit(ch)) { f|=(ch==‘-‘); ch=getchar(); } while(isdigit(ch)) { s=(s<<3)+(s<<1)+(ch^48); ch=getchar(); } return (f)?(-s):(s); } #define R(x) x=read() inline void write(ll x) { if(x<0) { putchar(‘-‘); x=-x; } if(x<10) { putchar(x+‘0‘); return; } write(x/10); putchar((x%10)+‘0‘); return; } #define W(x) write(x),putchar(‘ ‘) #define Wl(x) write(x),putchar(‘\n‘) const int N=205,M=1005,inf=0x3f3f3f3f; int n,m,a[N],Ges[N]; int S,T; struct Edge { int U,V; }E[N]; int Prim[100005]; bool Bo[100005]; inline void Shai(int Up) { int i,j; Bo[0]=Bo[1]=1; for(i=2;i<=Up;i++) { if(!Bo[i]) Prim[++*Prim]=i; for(j=1;j<=*Prim&&i*Prim[j]<=Up;j++) { Bo[i*Prim[j]]=1; if(i%Prim[j]==0) break; } } } namespace Picture { int tot=0,Next[M],to[M],Val[M],head[N]; inline void Init(); inline void add(int x,int y,int z); inline bool bfs(int S); inline int dfs(int S,int T,int Dist); inline int Max_Flow(); inline void Init() { tot=0; memset(head,0,sizeof head); } inline void add(int x,int y,int z) { Next[++tot]=head[x]; to[tot]=y; Val[tot]=z; head[x]=tot; Next[++tot]=head[y]; to[tot]=x; Val[tot]=0; head[y]=tot; } int Depth[N]; inline bool bfs(int S) { memset(Depth,0,sizeof Depth); int i; queue<int>Queue; while(!Queue.empty()) Queue.pop(); Depth[S]=1; Queue.push(S); while(!Queue.empty()) { int x=Queue.front(); Queue.pop(); for(i=head[x];i;i=Next[i]) if(Val[i]>0&&Depth[to[i]]==0) { Depth[to[i]]=Depth[x]+1; Queue.push(to[i]); } } return (Depth[T]==0)?0:1; } inline int dfs(int x,int Dist) { if(x==T) return Dist; int i; for(i=head[x];i;i=Next[i]) { if(Depth[to[i]]==Depth[x]+1&&Val[i]>0) { int oo=dfs(to[i],min(Dist,Val[i])); if(oo>0) { Val[i]-=oo; (i&1)?Val[i+1]+=oo:Val[i-1]+=oo; return oo; } } } return 0; } inline int Max_Flow() { int ans=0; while(bfs(S)) { ans+=dfs(S,inf); } return ans; } } #define Pic Picture int main() { int i,j,ans=0; R(n); R(m); S=0; T=n+1; for(i=1;i<=n;i++) R(a[i]); for(i=1;i<=m;i++) { R(E[i].U); R(E[i].V); if(E[i].U%2==0) swap(E[i].U,E[i].V); } Shai(100000); for(i=1;i<=*Prim;i++) { memset(Ges,0,sizeof Ges); Pic::Init(); for(j=1;j<=n;j++) { while(a[j]%Prim[i]==0) { a[j]/=Prim[i]; Ges[j]++; } } for(j=1;j<=n;j++) { if(j&1) Pic::add(S,j,Ges[j]); else Pic::add(j,T,Ges[j]); } for(j=1;j<=m;j++) { Pic::add(E[j].U,E[j].V,min(Ges[E[j].U],Ges[E[j].V])); } ans+=Pic::Max_Flow(); } Pic::Init(); for(i=1;i<=n;i++) if(a[i]!=1) { if(i&1) Pic::add(S,i,1); else Pic::add(i,T,1); } for(i=1;i<=m;i++) if(a[E[i].U]==a[E[i].V]&&a[E[i].U]!=1) { Pic::add(E[i].U,E[i].V,1); } ans+=Pic::Max_Flow(); Wl(ans); return 0; } /* Input 3 2 8 3 8 1 2 2 3 Output 0 Input 3 2 8 12 8 1 2 2 3 Output 2 */
原文：https://www.cnblogs.com/gaojunonly1/p/10742826.html