首页 > 代码库 > codeforces 498C Array and Operations 网络流
codeforces 498C Array and Operations 网络流
传送门:cf 498C
给定一个长度为n的数组,已经m组下标对应关系(下标之和为奇数),现在可以对m组对应关系中的数同除一个大于1的整数,问最多能进行多少次这样的操作
要操作次数最大,每次处理的时候应该除质数。
下标之和为奇数,不难发现它构成了一张二分图。
枚举sqrt(10^9)的质数,找出n个数中各有多少个这样的质数k,然后建立对应的图,跑网络流最大流即可。
/****************************************************** * File Name: c.cpp * Author: kojimai * Create Time: 2014年12月25日 星期四 01时05分10秒 ******************************************************/ #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<queue> #include<iostream> using namespace std; bool prime[32333]; int a[105],x[105],y[105],e; int n,m,len[105],first[105],next[2333]; struct Edge { int x,y,f,next; }edge[2333]; void addedge(int x,int y) { edge[e].x = x;edge[e].y = y;edge[e].next = first[x];edge[e].f = min(len[x],len[y]);first[x] = e++;//每条边的流量为相连两点中含质数个数的较小值 edge[e].x = y;edge[e].y = x;edge[e].next = first[y];edge[e].f = 0;first[y] = e++; } void init() { memset(prime,false,sizeof(prime)); for(int i = 2;i <= 31622;i++) { if(!prime[i]) { for(int j = i + i;j <= 31622;j += i) prime[j] = true; } } e = 0; return; } int dis[105]; bool bfs(int s,int t) { memset(dis,-1,sizeof(dis)); dis[s] = 0; queue<int> p; p.push(s); while(!p.empty()) { int now = p.front();p.pop(); //cout<<" now = "<<now<<endl; for(int k = first[now];k != -1;k = edge[k].next) { if(edge[k].f && dis[edge[k].y] == -1) { dis[edge[k].y] = dis[now] + 1; if(edge[k].y == t) return true; p.push(edge[k].y); } } } return false; } int dfs(int now,int flow,int t) { int f; if(now == t) return flow; for(int k = first[now];k != -1;k = edge[k].next) { if(edge[k].f && dis[edge[k].y] == dis[now] + 1 && (f = dfs(edge[k].y,min(flow,edge[k].f),t))) { edge[k].f -= f; edge[k^1].f += f; return f; } } return 0; } int dinic(int s,int t) { int flow,ret = 0; while(bfs(s,t)) { while(flow = dfs(s,23333333,t)) ret += flow; } return ret; } int solve(int xx) {//处理只除以质数xx的情况下的最大操作次数 memset(len,0,sizeof(len)); for(int i = 1;i <= n;i++) { while(a[i] % xx == 0) { len[i]++;//找出每个数中有多少个质数xx a[i] /= xx; } } len[0] = len[n+1] =23333; e = 0; memset(first,-1,sizeof(first)); for(int i = 1;i <= m;i++) { if(x[i] % 2 == 1) addedge(x[i],y[i]); else addedge(y[i],x[i]); } for(int i = 1;i <= n;i+= 2) addedge(0,i); for(int i = 2;i <= n;i+= 2) addedge(i,n+1); int ret = dinic(0,n+1); return ret; } void adde(int x,int y) { edge[e].x = x;edge[e].y = y;edge[e].next = first[x]; if(x == 0) edge[e].f = 1; else if(y == n+1) edge[e].f = 1; else if(a[x] == a[y] && a[x] > 1)//当处理较大质数时,因为所有较小质数都已经处理过了,只要两数相等就是同样大的质数,且只能除一次 edge[e].f = 1; else edge[e].f = 0; first[x] = e++; edge[e].x = y;edge[e].y = x;edge[e].next = first[y];edge[e].f = 0;first[y] = e++; } int main() { init(); scanf("%d%d",&n,&m); for(int i = 1;i <= n;i++) { scanf("%d",&a[i]); } for(int i = 1;i <= m;i++) { scanf("%d%d",&x[i],&y[i]); } int ans = 0; for(int i = 2;i <= 31622;i++) { if(!prime[i]) ans += solve(i); } for(int i = 1;i <= n;i+= 2) adde(0,i); for(int i = 2;i <= n;i+= 2) adde(i,n+1); for(int i = 1;i <= m;i++) { if(x[i] % 2 == 1) adde(x[i],y[i]); else adde(y[i],x[i]); } ans += dinic(0,n+1);//处理剩下当质数大于sqrt(10^9)时的情况 cout << ans <<endl; return 0; }
codeforces 498C Array and Operations 网络流
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。