「CodeForces-498C」Array and Operations 给定n个点和m个边集，每次操作可以将相连边的两个点值同时除以一个公约数，问最大操作次数 题意 给定一个长为$n$的数组，以及$m$对下标为$(a,b)$的点
「CodeForces-498C」Array and Operations
给定n个点和m个边集，每次操作可以将相连边的两个点值同时除以一个公约数，问最大操作次数
题意
给定一个长为$n$的数组，以及$m$对下标为$(a,b)$的点对，且满足下标a+b为奇数（即奇数点只与偶数点匹配），每次操作可以将同一组的两个数同时除以一个公约数，问最多能进行多少次操作。
解法
显然题目所给的是一个二分图。
对于每个质因数分开考虑。对于奇数点，向源点连接一个容量为该因子个数的边；对于偶数点，则向汇点建立一个容量为因子数的边；对于有边相连的点对，建立容量为$inf$的边。
对于题给的数组$a[i]$，通过分解质因数的方式计算每个质因数所建图的最大流，求和即为所求解。
代码
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
using namespace std;
const int MAX_V=200+10;
const int INF=0x3f3f3f3f;
struct {int to,cap,rev;};
vector<edge> G[MAX_V]; //图的邻接表表示
int level[MAX_V]; //顶点到源点的距离标号
int iter[MAX_V]; //当前弧
void add(int from,int to,int cap)
{
G[from].push_back((edge){to,cap,G[to].size()});
G[to].push_back((edge){from,0,G[from].size()-1});
}
//计算从源点出发的距离标号
void bfs(int s)
{
memset(level,-1,sizeof(level));
queue<int> que;
level[s]=0;
que.push(s);
while(!que.empty())
{
int v=que.front();que.pop();
for(int i=0;i<G[v].size();i++)
{
edge &e=G[v][i];
if(e.cap>0&&level[e.to]<0)
{
level[e.to]=level[v]+1;
que.push(e.to);
}
}
}
}
//通过DFS寻找增广路
int dfs(int v,int t,int f)
{
if(v==t) return f;
for(int &i=iter[v];i<G[v].size();i++)
{
edge &e=G[v][i];
if(e.cap>0 && level[v]<level[e.to])
{
int d=dfs(e.to,t,min(f,e.cap));
if(d>0)
{
e.cap-=d;
G[e.to][e.rev].cap+=d;
return d;
}
}
}
return 0;
}
//求解从s到t的最大流
int max_flow(int s,int t)
{
int flow=0;
for(;;)
{
bfs(s);
if(level[t]<0) return flow;
memset(iter,0,sizeof(iter));
int f;
while((f=dfs(s,t,INF))>0) flow+=f;
}
}
int n,m,a[105],u[105],v[105],s,t,ans=0;
void solve(int x)
{
for(int i=0;i<MAX_V;i++) G[i].clear();
for(int i=1;i<=n;i++)
{
int tot=0;
while(a[i]%x==0) a[i]/=x,tot++;
if(i%2) add(s,i,tot);
else add(i,t,tot);
}
for(int i=0;i<m;i++) add(u[i],v[i],INF);
ans+=max_flow(s,t);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=0;i<m;i++)
{
scanf("%d%d",&u[i],&v[i]);
if(v[i]&1) swap(u[i],v[i]);
}
s=0,t=n+1;
for(int i=1;i<=n;i++)
{
for(int j=2;j*j<=a[i];j++)
if(a[i]%j==0) solve(j);
if(a[i]>1) solve(a[i]);
}
printf("%dn",ans);
return 0;
}
原文:大专栏 「CodeForces-498C」Array and Operations(数论+网络流)