「BZOJ4205」「FJ2015集训」卡牌配对
卡牌配对
「问题描述」
现在有一种卡牌游戏，每张卡牌上有三个属性值：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配对。
另外，请大胆使用渐进复杂度较高的算法！
「数据规模与约定」
对于10%的数据，n1,n2≤ 10；
对于50%的数据，n1,n2≤ 3000。
对于100%的数据，n1,n2≤ 30000，属性值为不超过200的正整数
题解
算法1：很明显的匹配，暴力构图+匈牙利算法复杂度O(nm)可以得到10分，dinic可以拿到60分。
算法2：考虑到按照匹配建图边数过多，我们采用将边分类的方法优化。考虑a项属性值能被x整除且b项能力值能被y整除的所有点，只要是在两侧一定能够匹配，所以我们在匹配的网络流模型中间增加一排这样的点，满足要求的左右点分别与它相连，边权为正无穷。考虑到x和y只需是质数，这样的点共有至多3*46*46个（1～200质数共46个），而200<2*3*5*7，所以两侧每个点至多连出3*3*3条边。于是我们构成了一个70000个点，2000000条边的网络流，依然是分层图，所以dinic有极佳的速度优势，通过100分数据。
匈牙利算法
|
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 |
#include<map> #include<set> #include<cmath> #include<cstdio> #include<cstring> #include<vector> #include<iostream> #define ll long long using namespace std; ll read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int gcd(int a,int b) { return b==0?a:gcd(b,a%b); } struct data{ int x,y,z; }a[30005],b[30005]; int n1,n2,ans; int pa[30005]; bool vis[30005]; vector<int>e[30005]; bool solve(int x) { for(register int i=0;i<e[x].size();i++) if(!vis[e[x][i]]) { vis[e[x][i]]=1; if(!pa[e[x][i]]||solve(pa[e[x][i]])) { pa[e[x][i]]=x; return 1; } } return 0; } int main() { freopen("card.in","r",stdin); freopen("card.out","w",stdout); n1=read();n2=read(); for(int i=1;i<=n1;i++) a[i].x=read(),a[i].y=read(),a[i].z=read(); for(int i=1;i<=n2;i++) b[i].x=read(),b[i].y=read(),b[i].z=read(); for(int i=1;i<=n1;i++) for(int j=1;j<=n2;j++) { int p=0; if(gcd(a[i].x,b[j].x)==1)p++; if(gcd(a[i].y,b[j].y)==1)p++; if(gcd(a[i].z,b[j].z)==1)p++; if(p<=1) e[i].push_back(j); } for(int i=1;i<=n1;i++) { memset(vis,0,sizeof(vis)); ans+=solve(i); } printf("%d\n",ans); return 0; } |
网络流
|
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 117 118 119 120 121 122 |
#include<map> #include<set> #include<cmath> #include<cstdio> #include<cstring> #include<vector> #include<iostream> #define inf 1000000000 #define ll long long using namespace std; ll read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } struct data{ int x,y,z; }a[30005],b[30005]; struct edge{ int to,next,v; }e[4000005]; int n1,n2,ans,tot,cnt=1,ind,T; int pri[205],id[50][50]; int q[70005],h[70005],last[70005]; vector<int>v[205]; bool mark[205]; void insert(int u,int v,int w) { e[++cnt]=(edge){v,last[u],w};last[u]=cnt; e[++cnt]=(edge){u,last[v],0};last[v]=cnt; } bool bfs() { int head=0,tail=1; memset(h,-1,sizeof(h)); q[0]=0;h[0]=0; while(head!=tail) { int x=q[head];head++; for(int i=last[x];i;i=e[i].next) if(h[e[i].to]==-1&&e[i].v) { h[e[i].to]=h[x]+1; q[tail++]=e[i].to; } } return h[T]!=-1; } int dfs(int x,int f) { if(x==T)return f; int w,used=0; for(int i=last[x];i;i=e[i].next) if(h[e[i].to]==h[x]+1) { w=dfs(e[i].to,min(e[i].v,f-used)); e[i].v-=w;e[i^1].v+=w;used+=w; if(used==f)return f; } if(!used)h[x]=-1; return used; } void pre() { for(int i=2;i<=200;i++) { if(!mark[i])pri[++tot]=i; for(int j=1;j<=tot&&pri[j]*i<=200;j++) { mark[pri[j]*i]=1; if(i%pri[j]==0)break; } } for(int i=2;i<=200;i++) for(int j=1;j<=tot;j++) if(i%pri[j]==0)v[i].push_back(j); } void build(int t,int f) { int x,y,z; if(!f)x=a[t].x,y=a[t].y,z=a[t].z; else x=b[t].x,y=b[t].y,z=b[t].z; for(int i=0;i<v[x].size();i++) for(int j=0;j<v[y].size();j++) if(!f)insert(t,n1+n2+id[v[x][i]][v[y][j]],1); else insert(n1+n2+id[v[x][i]][v[y][j]],n1+t,1); for(int i=0;i<v[x].size();i++) for(int j=0;j<v[z].size();j++) if(!f)insert(t,n1+n2+id[v[x][i]][v[z][j]]+46*46,1); else insert(n1+n2+id[v[x][i]][v[z][j]]+46*46,n1+t,1); for(int i=0;i<v[y].size();i++) for(int j=0;j<v[z].size();j++) if(!f)insert(t,n1+n2+id[v[y][i]][v[z][j]]+46*46*2,1); else insert(n1+n2+id[v[y][i]][v[z][j]]+46*46*2,n1+t,1); } int main() { freopen("card.in","r",stdin); freopen("card.out","w",stdout); pre(); n1=read();n2=read();T=n1+n2+46*46*3+1; for(int i=1;i<=n1;i++) a[i].x=read(),a[i].y=read(),a[i].z=read(); for(int i=1;i<=n2;i++) b[i].x=read(),b[i].y=read(),b[i].z=read(); for(int i=1;i<=46;i++) for(int j=1;j<=46;j++) id[i][j]=++ind; for(int i=1;i<=n1;i++) { insert(0,i,1);build(i,0); } for(int i=1;i<=n2;i++) { insert(n1+i,T,1);build(i,1); } while(bfs())ans+=dfs(0,inf); printf("%d\n",ans); return 0; } |
计数器 9318611
OI 课件=>
OI 课件=>
[…] 原题网址：http://www.lydsy.com/JudgeOnline/problem.php?id=4205 大致模型是二分图最大匹配，但暴力建边会T，考虑建中间节点，至少要有两项属性值不互质，但这样中间点数还是爆炸和边数，然而看了题解才知道中间点只要质数即可。（一开始反向边流量又忘记设为0了。。。 %hzwer http://hzwer.com/7428.html […]
%%%codeforces
黄学长神犇，%%%%