首页 > 代码库 > 【费用流】bzoj1661 [BeiJing wc2012]连连看
【费用流】bzoj1661 [BeiJing wc2012]连连看
将每个数拆点,互相连边,然后满足条件的数对之间互相连边,跑最大费用流,答案是流量和费用分别除以2。
一定要i->j、j->i都连上,否则可能会出现一个数在一边被选择了,在另一边的另一个匹配中又被选择的情况。
#include<cstdio>#include<algorithm>#include<cmath>#include<cstring>#include<queue>using namespace std;#define MAXN 2002#define MAXM 500001#define INF 2147483647int S,T,n,A,B;int en,u[MAXM],v[MAXM],first[MAXN],next[MAXM],cap[MAXM],cost[MAXM];//Next Arraybool inq[MAXN];int d[MAXN]/*spfa*/,p[MAXN]/*spfa*/,a[MAXN]/*可改进量*/;queue<int>q;void Init_MCMF(){memset(first,-1,sizeof(first));en=0;S=0;T=(B<<1|1);}void AddEdge(const int &U,const int &V,const int &W,const int &C){u[en]=U; v[en]=V; cap[en]=W; cost[en]=C; next[en]=first[U]; first[U]=en++;u[en]=V; v[en]=U; cost[en]=-C; next[en]=first[V]; first[V]=en++;}bool Spfa(int &Flow,int &Cost){ memset(d,0x7f,sizeof(d)); memset(inq,0,sizeof(inq)); d[S]=0; inq[S]=1; p[S]=0; a[S]=INF; q.push(S); while(!q.empty()) { int U=q.front(); q.pop(); inq[U]=0; for(int i=first[U];i!=-1;i=next[i]) if(cap[i] && d[v[i]]>d[U]+cost[i]) { d[v[i]]=d[U]+cost[i]; p[v[i]]=i; a[v[i]]=min(a[U],cap[i]); if(!inq[v[i]]) {q.push(v[i]); inq[v[i]]=1;} } } if(d[T]>2100000000) return 0; Flow+=a[T]; Cost+=d[T]*a[T]; int U=T; while(U!=S) { cap[p[U]]-=a[T]; cap[p[U]^1]+=a[T]; U=u[p[U]]; } return 1;}int Mincost(){ int Flow=0,Cost=0; while(Spfa(Flow,Cost)); printf("%d %d\n",Flow>>1,(-Cost)>>1);}int gcd(int a,int b){return b==0?a:gcd(b,a%b);}int sqr(const int &x){return x*x;}bool check(const int &a,const int &b){ int t=a*a-b*b; if(sqr((int)sqrt(t))!=t) return 0; if(gcd(b,(int)sqrt(t))==1) return 1; return 0;}int main(){ scanf("%d%d",&A,&B); Init_MCMF(); for(int i=A;i<=B;++i) for(int j=A;j<i;++j) if(check(i,j)) { AddEdge(i,j+B,1,-i-j); AddEdge(j,i+B,1,-i-j); } for(int i=A;i<=B;++i) { AddEdge(S,i,1,0); AddEdge(i+B,T,1,0); } Mincost(); return 0;}
【费用流】bzoj1661 [BeiJing wc2012]连连看
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。