本文主要是介绍Codeforces Round #284 (Div. 1) C，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
C. Array and Operations
题意：有n个数，a1~an；m对数i1/j1~im/jm(ik+jk为奇数)。每次操作取出其中一对ik/jk，使a[ik]和a[jk]同时除以一个不为1的正整数v。问最多能够进行几次操作。
思路：很容易得出，每次操作的v越小，接下来还能进行的操作就越多，进一步得出，v应该选择素数。因为每对数的和是奇数，所以可以建一个二部图，一个集合是奇数，一个集合是偶数。然后枚举所有范围内的素数，对每个素数建边跑最大流就可以了。
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
#include <map>
#include <vector>
#include <set>
#include <string>
#include <math.h>
using namespace std;#define INF 100000010
#define maxn 110 struct Edge{ int u; int v; int cap; int flow; Edge(int u,int v,int c):u(u),v(v),cap(c),flow(0){} Edge(){};
};
Edge edges[maxn*maxn]; int ne;
int head[maxn];
int next[maxn*maxn];
int N,M;
int L[maxn*maxn];
int D[maxn]; void init(){ memset(head,-1,sizeof(head)); memset(D,0,sizeof(D)); ne=0;
} int lv[maxn];
bool bfs(int s,int t){ memset(lv,-1,sizeof(lv)); lv[s]=0; queue<int> que; que.push(s); while(!que.empty()){ int cur=que.front(); que.pop(); for(int i=head[cur];i!=-1;i=next[i]){ Edge& e=edges[i]; if(lv[e.v]!=-1)continue; if(e.flow<e.cap){ lv[e.v]=lv[cur]+1; que.push(e.v); } } if(lv[t]!=-1)return 1; } return 0;
} int cur[maxn];
int dfs(int x,int a){ if(x==101||a==0)return a; int re=0; for(int& i=cur[x];i!=-1;i=next[i]){ Edge& e=edges[i]; int t; if(lv[e.v]==(lv[x]+1)&& (t=dfs( e.v , min(a,e.cap-e.flow))) ){ edges[i].flow+=t; edges[i^1].flow-=t; re+=t; a-=t; if(a==0)break; } } return re;
} int maxflow(int s,int t){ int flow=0; while(bfs(s,t)){memcpy(cur,head,sizeof(head)); flow+=dfs(s,INF); } return flow;
} void addedge(int u,int v,int c){ edges[ne]=Edge(u,v,c); next[ne]=head[u]; head[u]=ne; ne++; edges[ne]=Edge(v,u,0); next[ne]=head[v]; head[v]=ne; ne++;
} int a[maxn];
int x[maxn];
int y[maxn];vector<int> prime;int gcd(int a,int b){if(b==0)return a;return gcd(b,a%b);
}int main(){//int n,m;cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<=m;i++){cin>>x[i]>>y[i];if(x[i]%2==0)swap(x[i],y[i]); //确保x是奇数y是偶数 int g=gcd(a[x[i]],a[y[i]]);for(int j=2;j*j<=g;j++){if(g%j==0){prime.push_back(j);while(g%j==0)g/=j;}}if(g!=1)prime.push_back(g);}sort(prime.begin(),prime.end());vector<int>::iterator end;end=unique(prime.begin(),prime.end());int ans=0;//枚举素数for(vector<int>::iterator it=prime.begin() ;it!=end;it++){int k=*it;init();//源到奇数，偶数到汇 for(int i=1;i<=n;i++){int tmp=a[i];int cap=0;while(tmp%k==0){cap++;tmp/=k;}if(cap)if(i&1){addedge(0,i,cap);}else{addedge(i,101,cap);}}//奇数到偶数 for(int i=1;i<=m;i++){addedge(x[i],y[i],INF);} ans+=maxflow(0,101);}cout<<ans<<endl;return 0;
}这篇关于Codeforces Round #284 (Div. 1) C的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
