[SDOI2016]数字配对

题目

发现要求配对的条件是这样

\[a_j|a_i,\frac{a_i}{a_j}=p_1\]

我们考虑一下再来一个\(a_k\)，满足

\[a_k|a_j,\frac{a_j}{a_k}=p_2\]

显然\(a_i=a_jp_1,a_j=a_kp_2\)，于是\(a_i=p_1p_2\times a_k\)

显然\(p_1p_2\)不会是一个质数，于是我们大胆得出一个结论，如果\(a_i\)能和\(a_j\)配对，那么\(a_i\)就不能和其他能和\(a_j\)配对的数配对

于是经过这样一番简单分析，发现这是一二分图

那么做法就很显然了，我们将这张图来一个黑白染色，之后按照题目要求连边就好了

至于这道题要求在费用为正的情况下流量最大，最大费用最大流只能保证最大流的时候费用最大，不能保证费用为正

但是我们知道\(spfa\)去增广出的最长路肯定越来越小，于是我们一旦发现当前费用乘上流量小于\(0\)了，以后就不可能再使得费用为正了，于是在这个之后判断一下剩余流量退出就好了

当然，由于只会写板子，还是边权取反的最小费用最大流好写

代码

#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define re register
#define LL long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define int long long
const int maxn=205;
const int inf=99999999999;
inline int read() {
    char c=getchar();int r=1,x=0;
    while(c<'0'||c>'9') {if(c=='-') r=-1;c=getchar();}
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return r*x;
}
std::vector<int> v[maxn];
std::queue<int> q;
struct E{int v,nxt,f;LL w;}e[205*205*10];
int head[maxn],d[maxn],vis[maxn];
int a[maxn],b[maxn],c[maxn],col[maxn];
int S,T,n,num=1;
inline void C(int x,int y,LL w,int f) {
    e[++num].v=y;e[num].nxt=head[x];head[x]=num;
    e[num].f=f,e[num].w=w;
}
inline void add(int x,int y,LL w,int f) {C(x,y,-1*w,f),C(y,x,w,0);}
inline int SPFA() {
    for(re int i=S;i<=T;i++) vis[i]=0,d[i]=inf;
    q.push(T),d[T]=0;
    while(!q.empty()) {
        int k=q.front();q.pop();vis[k]=0;
        for(re int i=head[k];i;i=e[i].nxt) 
        if(e[i^1].f&&d[e[i].v]>d[k]+e[i^1].w) {
            d[e[i].v]=d[k]+e[i^1].w;
            if(!vis[e[i].v]) q.push(e[i].v),vis[e[i].v]=1;
        }
    }
    return d[S]<inf;
}
int dfs(int x,int now) {
    if(x==T||!now) return now;
    int flow=0,ff;vis[x]=1;
    for(re int i=head[x];i;i=e[i].nxt)
    if(!vis[e[i].v]&&e[i].f&&d[e[i].v]==d[x]+e[i^1].w) {
        ff=dfs(e[i].v,min(now,e[i].f));
        if(ff<=0) continue;
        now-=ff,flow+=ff;e[i].f-=ff,e[i^1].f+=ff;
        if(!now) break;
    }
    return flow;
}
inline int check(int x) {
    if(x==1) return 0;
    for(re int i=2;i*i<=x;i++)
        if(x%i==0) return 0;
    return 1;
}
void paint(int x,int now) {
    col[x]=now;
    for(re int i=0;i<v[x].size();i++)
    if(col[v[x][i]]==2) paint(v[x][i],now^1); 
}
signed main() {
    n=read();T=n+1;
    for(re int i=1;i<=n;i++) a[i]=read();
    for(re int i=1;i<=n;i++) b[i]=read();
    for(re int i=1;i<=n;i++) c[i]=read();
    for(re int i=1;i<=n;i++)
        for(re int j=1;j<=n;j++)
            if(a[i]%a[j]==0&&check(a[i]/a[j])) 
                v[i].push_back(j),v[j].push_back(i);
    for(re int i=1;i<=n;i++) col[i]=2;
    for(re int i=1;i<=n;i++) 
        if(col[i]==2) paint(i,1);
    for(re int i=1;i<=n;i++)
    if(col[i]) add(S,i,0,b[i]);
        else add(i,T,0,b[i]);
    for(re int i=1;i<=n;i++) {
        if(!col[i]) continue;
        for(re int j=0;j<v[i].size();j++) 
            add(i,v[i][j],(LL)c[i]*(LL)c[v[i][j]],inf);
    }
    int t=0,ans=0,flag=1,F=0;
    while(SPFA()) {
        vis[T]=1;
        while(vis[T]) {
            for(re int i=S;i<=T;i++) vis[i]=0;
            t=dfs(S,inf);
            if(ans+t*d[S]>0) {
                F+=(0-ans)/d[S];
                flag=0;break;
            }
            ans+=t*d[S],F+=t;
        }
        if(!flag) break;
    }
    printf("%lld\n",F);
    return 0;
}

[SDOI2016]数字配对

原文：https://www.cnblogs.com/asuldb/p/10559645.html