模型
给你一些物品，每一个物品都有自己的价值，但是有些物品两两之间会产生冲突，问能选出的物品最大的总价值
通用的的做法是在两两冲突的物品之间连边
在建出的图上跑黑白染色
由源点向所有的白点连边，由所有的黑点向汇点连边，由所有的白点向会与它产生冲突的黑点连边
跑一个最大流即可
例题
[SDOI2016]数字配对
分析
设 (cnt[i]) 为 (a[i]) 分解质因数后质因数所有幂次的和。
如果 (a[i]) 和 (a[j]) 会产生冲突，那么 (cnt[i]) 和 (cnt[j]) 的奇偶性一定是相反的。
所以我们只要把 (cnt) 为奇数的染成白色，把所有 (cnt) 为偶数的染成黑色。
这样问题就转化为了二分图的模型。
然后由源点向所有白点连流量为 (b[i])，费用为 (0) 的边。
由白点向所有会与它产生冲突的黑点连流量为无穷大，费用为对应价值的边。
黑点同理。
因为题目中还有价值总和不小于 (0) 的限制。
所以不能直接跑最大费用最大流。
要在费用变为 (0) 的时候停止增广。
因为在增广的过程中费用一定是逐渐变小的。
代码
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#define rg register
inline int read(){
rg int x=0,fh=1;
rg char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') fh=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*fh;
}
const int maxn=5e4+5;
int h[maxn],tot=2,n,m,s,t,ans;
struct asd{
int to,nxt,val;
long long cost;
}b[maxn<<1];
void ad(rg int aa,rg int bb,rg int cc,rg long long dd){
b[tot].to=bb;
b[tot].val=cc;
b[tot].cost=dd;
b[tot].nxt=h[aa];
h[aa]=tot++;
}
long long dis[maxn],ans2;
int pre[maxn],incf[maxn],ans1;
bool inq[maxn];
std::queue<int> q;
bool spfa(){
memset(dis,0xcf,sizeof(dis));
memset(pre,0,sizeof(pre));
memset(incf,0,sizeof(incf));
inq[s]=1,dis[s]=0,incf[s]=0x3f3f3f3f;
q.push(s);
while(!q.empty()){
rg int now=q.front();
q.pop();
inq[now]=0;
for(rg int i=h[now];i!=-1;i=b[i].nxt){
rg int u=b[i].to;
if(b[i].val && dis[u]<dis[now]+b[i].cost){
dis[u]=dis[now]+b[i].cost;
incf[u]=std::min(incf[now],b[i].val);
pre[u]=i;
if(!inq[u]){
inq[u]=1;
q.push(u);
}
}
}
}
return dis[t]!=dis[0];
}
void updat(){
rg int now=t,i;
ans2+=dis[now]*incf[now];
if(ans2<0){
ans1-=(ans2-dis[now]*incf[now])/dis[now];
printf("%d
",ans1);
std::exit(0);
}
ans1+=incf[now];
while(now!=s){
i=pre[now];
b[i].val-=incf[t];
b[i^1].val+=incf[t];
now=b[i^1].to;
}
}
int jla[maxn],jlb[maxn],jlc[maxn],cnt[maxn];
int div(rg int now){
rg int ncnt=0;
for(rg int i=2;i*i<=now;i++){
if(now%i==0){
while(now%i==0){
now/=i;
ncnt++;
}
}
}
if(now>1) ncnt++;
return ncnt;
}
int main(){
memset(h,-1,sizeof(h));
n=read();
s=n+1,t=n+2;
for(rg int i=1;i<=n;i++) jla[i]=read();
for(rg int i=1;i<=n;i++) jlb[i]=read();
for(rg int i=1;i<=n;i++) jlc[i]=read();
for(rg int i=1;i<=n;i++) cnt[i]=div(jla[i]);
for(rg int i=1;i<=n;i++){
if(cnt[i]&1){
ad(s,i,jlb[i],0);
ad(i,s,0,0);
} else {
ad(i,t,jlb[i],0);
ad(t,i,0,0);
}
}
for(rg int i=1;i<=n;i++){
if(cnt[i]&1){
for(rg int j=1;j<=n;j++){
if(cnt[j]&1) continue;
if((cnt[i]==cnt[j]+1 && jla[i]%jla[j]==0) || (cnt[j]==cnt[i]+1 && jla[j]%jla[i]==0)){
ad(i,j,0x3f3f3f3f,1LL*jlc[i]*jlc[j]);
ad(j,i,0,-1LL*jlc[i]*jlc[j]);
}
}
}
}
while(spfa()) updat();
printf("%d
",ans1);
return 0;
}
bzoj3158千钧一发
分析
可以证明，任意两个偶数满足 (2)
任意两个奇数满足 (1)
((2a+1)^2+(2b+1)^2=2(2a^2+2b^2+2a+2b+1))
一定不是完全平方数，因为括号里的东西显然是一个奇数，不能再分出一个 (2)
所以可以把奇数作为白点，偶数作为黑点
跑一个最小割就行了
代码
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cmath>
#include<cstring>
#include<map>
#define rg register
inline int read(){
rg int x=0,fh=1;
rg char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') fh=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*fh;
}
const int maxn=1e6+5;
int h[maxn],h2[maxn],tot=2,s,t;
std::map<int,int> mp[maxn],id[maxn];
struct asd{
int to,nxt,val;
}b[maxn<<1];
void ad(rg int aa,rg int bb,rg int cc){
b[tot].to=bb;
b[tot].nxt=h[aa];
b[tot].val=cc;
h[aa]=tot++;
}
int q[maxn],head,tail,dep[maxn],mmax;
bool bfs(){
for(rg int i=1;i<=mmax;i++){
h[i]=h2[i];
dep[i]=0;
}
q[head=tail=1]=s;
dep[s]=1;
while(head<=tail){
rg int now=q[head++];
for(rg int i=h[now];i!=-1;i=b[i].nxt){
rg int u=b[i].to;
if(b[i].val && !dep[u]){
dep[u]=dep[now]+1;
q[++tail]=u;
}
}
}
return dep[t]!=0;
}
int dfs(rg int now,rg int ac1){
if(now==t) return ac1;
rg int ac2=0;
for(rg int i=h[now];i!=-1;i=b[i].nxt){
h[now]=i;
rg int u=b[i].to;
if(b[i].val && dep[u]==dep[now]+1){
rg int nans=dfs(u,std::min(b[i].val,ac1));
b[i].val-=nans;
b[i^1].val+=nans;
ac1-=nans;
ac2+=nans;
}
if(ac1==0) break;
}
if(ac2==0) dep[now]=0;
return ac2;
}
int n,a[maxn],val[maxn];
bool jud(rg long long val){
rg long long sqr=sqrt(val);
return sqr*sqr==val;
}
int gcd(rg int aa,rg int bb){
return bb==0?aa:gcd(bb,aa%bb);
}
int ans=0,col[maxn];
int main(){
memset(h,-1,sizeof(h));
n=read();
s=n+1,t=n+2,mmax=n+2;
for(rg int i=1;i<=n;i++){
a[i]=read();
}
for(rg int i=1;i<=n;i++){
val[i]=read();
ans+=val[i];
if(a[i]&1){
ad(s,i,val[i]);
ad(i,s,0);
} else {
ad(i,t,val[i]);
ad(t,i,0);
}
}
for(rg int i=1;i<=n;i++){
if(a[i]&1){
for(rg int j=1;j<=n;j++){
if((a[j]&1)==0){
if(jud(1LL*a[i]*a[i]+1LL*a[j]*a[j]) && gcd(a[i],a[j])==1){
ad(i,j,0x3f3f3f3f);
ad(j,i,0);
}
}
}
}
}
for(rg int i=1;i<=mmax;i++) h2[i]=h[i];
while(bfs()) ans-=dfs(s,0x3f3f3f3f);
printf("%d
",ans);
return 0;
}