现在有一种卡牌游戏，每张卡牌上有三个属性值：A,B,C。把卡牌分为X,Y两类，分别有n1,n2张。 两张卡牌能够配对，当且仅当，存在至多一项属性值使得两张卡牌该项属性值互质，且两张卡牌类别不同。 比如一张X类卡牌属性值分别是225,233,101，一张Y类卡牌属性值分别为115,466,99。那么这两张牌是可以配对的，因为只有101和99一组属性互质。 游戏的目的是最大化匹配上的卡牌组数，当然每张卡牌只能用一次。
数据第一行两个数n1，n2，空格分割。 接下来n1行，每行3个数，依次表示每张X类卡牌的3项属性值。 接下来n2行，每行3个数，依次表示每张Y类卡牌的3项属性值。
输出一个整数：最多能够匹配的数目。
2 2 2 2 2 2 5 5 2 2 5 5 5 5
2 【提示】 样例中第一张X类卡牌和第一张Y类卡牌能配对，第二张X类卡牌和两张Y类卡牌都能配对。所以最佳方案是第一张X和第一张Y配对，第二张X和第二张Y配对。 另外，请大胆使用渐进复杂度较高的算法！
对于100%的数据，n1,n2≤ 30000，属性值为不超过200的正整数
又一道场上想不出来的题。 首先考虑普通网络流匹配：左边是一类卡牌，右边是另一类卡牌，两两之间看能否配对连一条容量为1的边，做一次Dinic出解。 但是完整数据中两边点数都是3万，肯定无法两两连边。这时候我们想到优化建图：我们肯定是要构造一些特殊信息点，将符合信息的卡牌分别连向它们，以此减少边数、完成匹配。 照例从源点向每一个X卡牌连一条容量为1的边，每一个Y卡牌向汇点连一条容量为1的边，限制匹配次数。 考虑中间辅助匹配的信息点是什么：至多一组数互质等价于至少两组数不互质。不互质，意味着有公约数；而至少两组数的话，我们可以分拆成三种情况：一对卡牌的AB满足条件、AC满足条件、BC满足条件。 公约数怎么处理？我们可以把所有公约数二元组看成一个信息点。以12为例，我们在中间建一列信息点\((x,y)\)，所有满足\(x|A\)且\(y|B\)的X卡牌向这个点连一条容量为1的边，相应地从这个点向满足条件的Y卡牌连一条容量为1的边。我们发现，这样恰好可以使得满足AB都不互质的卡牌们进行配对过程。 同理建出其他两组信息点。三组信息点同时存在时，我们发现不论如何，一张X卡牌最多通过一种方式也就是一组信息点和另一边的某一张Y卡牌配对，同样地Y卡牌不论如何也只会通过一种方式配对。即使是ABC都满足的一对卡牌，也最多只会选择从某一组信息点流过。 建模完成，过程优美。 但是\((x,y)\)的点数足足有\(3*200*200\)个，太多了。其实有公约数不就是有公质因子吗？200以内的素数仅仅有46个，所以现在我们只需要把信息点的\((x,y)\)变更成质数的组合\((p_i,p_j)\)，按上述连边即可。信息点点数仅仅有\(3*46*46=6348\)个。 Dinic是跑得过的，有极大的速度优势。
#include <cstdio> #include <queue> using namespace std; const int N=30005,INF=1000000000,SZ=68000,M=6000000; int p[N],pcnt,minp[N],id[N]; bool vis[N]; int n1,n2,a[N*2][3]; int h[SZ],tot=1; int S,T,dis[SZ],cur[SZ]; queue<int> q; struct Edge{int v,f,next;}e[M*2]; inline void addEdge(int u,int v,int f){ e[++tot]=(Edge){v,f,h[u]}; h[u]=tot; e[++tot]=(Edge){u,0,h[v]}; h[v]=tot; } void sieve(){ minp[1]=1; for(int i=2;i<=200;i++){ if(!vis[i]){ p[++pcnt]=i; minp[i]=i; id[i]=pcnt; } for(int j=1;j<=pcnt&&i*p[j]<=200;j++){ int x=i*p[j]; vis[x]=true; if(i%p[j]==0){ minp[x]=p[j]; break; } minp[x]=p[j]; } } } bool bfs(){ for(int i=1;i<=T;i++) dis[i]=-1,cur[i]=h[i]; while(!q.empty()) q.pop(); q.push(S); dis[S]=0; while(!q.empty()){ int u=q.front(); q.pop(); for(int i=h[u],v;i;i=e[i].next) if(e[i].f&&dis[v=e[i].v]==-1){ dis[v]=dis[u]+1; if(v==T) return true; q.push(v); } } return dis[T]!=-1; } int dfs(int u,int flow){ if(u==T) return flow; int res=0,get; for(int i=cur[u],v;i&&flow;i=e[i].next) if(e[i].f&&dis[v=e[i].v]==dis[u]+1){ get=dfs(v,min(flow,e[i].f)); e[i].f-=get; e[i^1].f+=get; if(e[i].f) cur[u]=i; flow-=get; res+=get; } if(!res) dis[u]=-1; return res; } int dinic(){ int res=0; while(bfs()) res+=dfs(S,INF); return res; } void deal(int x,int *l,int &cnt){ cnt=0; while(x!=1){ l[++cnt]=id[minp[x]]; int p=minp[x]; while(x%p==0) x/=p; } } int main(){ sieve(); scanf("%d%d",&n1,&n2); for(int i=1;i<=n1+n2;i++) scanf("%d%d%d",&a[i][0],&a[i][1],&a[i][2]); S=n1+n2+46*46*3+1; T=S+1; for(int i=1;i<=n1;i++) addEdge(S,i,1); for(int i=1;i<=n2;i++) addEdge(n1+i,T,1); int l1[5],l2[5],l3[5],t1,t2,t3; for(int u=1;u<=n1+n2;u++){ deal(a[u][0],l1,t1); deal(a[u][1],l2,t2); deal(a[u][2],l3,t3); for(int i=1;i<=t1;i++) for(int j=1;j<=t2;j++){ int id=46*(l1[i]-1)+(l2[j]-1)+1; u<=n1?addEdge(u,n1+n2+id,1):addEdge(n1+n2+id,u,1); } for(int i=1;i<=t1;i++) for(int j=1;j<=t3;j++){ int id=46*(l1[i]-1)+(l3[j]-1)+1; u<=n1?addEdge(u,n1+n2+46*46+id,1):addEdge(n1+n2+46*46+id,u,1); } for(int i=1;i<=t2;i++) for(int j=1;j<=t3;j++){ int id=46*(l2[i]-1)+(l3[j]-1)+1; u<=n1?addEdge(u,n1+n2+2*46*46+id,1):addEdge(n1+n2+2*46*46+id,u,1); } } printf("%d\n",dinic()); return 0; }
转载于:https://www.cnblogs.com/RogerDTZ/p/9279181.html
相关资源：各显卡算力对照表！