BZOJ 3158 千钧一发 (最大流->二分图带权最大独立集)

和方格取数问题很像啊

但这道题不能像网格那样黑白染色构造二分图，所以考虑拆点建出二分图

我们容易找出数之间的互斥关系，在不能同时选的两个点之间连一条流量为$inf$的边

由于我们是拆点建的图，所以对于两个点$x,y$，$x1$向$y2$连边，$y1$向$x2$连边，边权均为$inf$

然后就是最大权闭合图的裸题了，源点$S$向所有$1$点连边，所有$2$点向汇点$T$连边，边权为$b_{i}$

跑最大流。最终答案是$sum b_{i}-$最大流$/2$，$/2$是因为拆点求出的是$2$倍的最小割

 1 #include <cmath>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #define N1 2010
 6 #define M1 1010000
 7 #define ll long long
 8 using namespace std;
 9 
10 const int inf=0x3f3f3f3f;
11 int gint()
12 {
13     int ret=0,fh=1; char c=getchar();
14     while(c<'0'||c>'9'){if(c=='-')fh=-1;c=getchar();}
15     while(c>='0'&&c<='9'){ret=ret*10+c-'0';c=getchar();}
16     return ret*fh;
17 }
18 int gcd(int x,int y){ if(!y) return x; return gcd(y,x%y); }
19 struct Edge{
20 int head[N1],to[M1<<1],nxt[M1<<1],flow[M1<<1],cte;
21 void ae(int u,int v,int f)
22 {
23     cte++; to[cte]=v; nxt[cte]=head[u];
24     head[u]=cte; flow[cte]=f;
25 }
26 }e;
27 
28 int n,m,hd,tl,S,T;
29 int dep[N1],cur[N1],que[M1];
30 int bfs()
31 {
32     int x,j,v;
33     memset(dep,-1,(T+1)<<2); memcpy(cur,e.head,(T+1)<<2);
34     hd=1,tl=0; que[++tl]=S; dep[S]=0;
35     while(hd<=tl)
36     {
37         x=que[hd++];
38         for(j=e.head[x];j;j=e.nxt[j])
39         {
40             v=e.to[j];
41             if( e.flow[j]>0 && dep[v]==-1 )
42                 dep[v]=dep[x]+1, que[++tl]=v;
43         }
44     }
45     return dep[T]!=-1;
46 }
47 int dfs(int x,int limit)
48 {
49     int j,v,flow,ans=0;
50     if(x==T||!limit) return limit;
51     for(j=cur[x];j;j=e.nxt[j])
52     {
53         v=e.to[j]; cur[x]=j;
54         if( dep[v]==dep[x]+1 && (flow=dfs(v,min(e.flow[j],limit))) )
55         {
56             e.flow[j]-=flow; limit-=flow;
57             e.flow[j^1]+=flow; ans+=flow;
58             if(!limit) break;
59         }
60     }
61     return ans;
62 }
63 int Dinic()
64 {
65     int ans=0;
66     while(bfs())
67         ans+=dfs(S,inf);
68     return ans;
69 }
70 
71 int a[N1],b[N1];
72 int main()
73 {
74     scanf("%d",&n); S=0; T=n+n+1;
75     int i,j,sum=0,ans;ll k; e.cte=1;
76     for(i=1;i<=n;i++) a[i]=gint();
77     for(i=1;i<=n;i++) b[i]=gint(), sum+=b[i]; 
78     for(i=1;i<=n;i++) for(j=1;j<=n;j++)
79     {
80         if(i==j) continue;
81         if(gcd(a[i],a[j])>1) continue;
82         k=sqrt(1ll*a[i]*a[i]+1ll*a[j]*a[j]);
83         if(1ll*k*k!=1ll*a[i]*a[i]+1ll*a[j]*a[j]) continue;
84         e.ae(i,j+n,inf); e.ae(j+n,i,0);
85     }
86     for(i=1;i<=n;i++) e.ae(S,i,b[i]), e.ae(i,S,0), e.ae(i+n,T,b[i]), e.ae(T,i+n,0);
87     ans=Dinic();
88     printf("%d
",sum-ans/2);
89     bfs();
90     S=T; bfs();
91     return 0;
92 }