網路流模型之二分圖匹配問題
模型
給你一些物品，每一個物品都有自己的價值，但是有些物品兩兩之間會產生衝突，問能選出的物品最大的總價值
通用的的做法是在兩兩衝突的物品之間連邊
在建出的圖上跑黑白染色
由源點向所有的白點連邊，由所有的黑點向匯點連邊，由所有的白點向會與它產生衝突的黑點連邊
跑一個最大流即可
例題
[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\n",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\n",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\n",ans);
return 0;
}
