ZC's blog

自分が選んだ道を、ひざまずいても歩き終わる

ZC's avatar ZC

网络流24题

题目地址:

网络流24题真的好有质量~\ ($\ge $▽$\le $ ) /~!

进度: $\frac{7}{24}$

1. 飞行员配对方案问题

二分图模板

匈牙利(待填坑):

网络流:

2.负载平衡问题

等同于[HAOI2008]糖果传递 ,懒,直接搬题解

也有费用流做法(待填坑)

#include<bits/stdc++.h>
#define il __inline__ __attribute__ ((always_inline))
#define rg register
#define ll long long
#define Fur(i,x,y) for(rg int i=x;i<=y;i++)
using namespace std;
namespace IO{const char* ln="\n";const int str=1<<20;struct IN{char buf[str],*s,*t;bool _;IN():s(buf),t(buf),_(0){}il char gc(){return s==t&&((t=(s=buf)+fread(buf,1,str,stdin))==s)?EOF:(*s++);}IN&operator>>(char&ch){if(_)return *this;char c;while((c=gc())!=EOF&&isspace(c));if(c==EOF)_=1;else ch=c;return *this;}IN& operator>>(char* ch){if(_)return *this;char c;while((c=gc())!=EOF&&isspace(c));if(c==EOF)return _=1,*this;*ch=c;ch++;while((c=gc())!=EOF&&!isspace(c))*ch=c,ch++;if(c==EOF)_=1;return *this;}template<typename T>IN&operator>>(T&x){if(_)return *this;char c=gc();bool ff=0;while(c!=EOF&&(c<'0'||c>'9'))ff^=(c=='-'),c=gc();if(c==EOF){_=1;return *this;}x=0;while(c!=EOF&&'0'<=c&&c<='9')x=(x<<3)+(x<<1)+c-48,c=gc();if(c==EOF)_=1;if(ff)x=-x;return *this;}}in;struct OUT{char buf[str],*s,*t;OUT():s(buf),t(buf+str){}~OUT(){fwrite(buf,1,s-buf,stdout);}void pt(char c){(s==t)?(fwrite(s=buf,1,str,stdout),*s++=c):(*s++=c);}OUT&operator<<(const char*s){while(*s)pt(*s++);return *this;}OUT&operator<<(char*s){while(*s)pt(*s++);return *this;}template<typename T>OUT&operator<<(T x){if(!x)return pt('0'),*this;if(x<0)pt('-'),x=-x;char a[30],t=0;while(x)a[t++]=x%10,x/=10;while(t--)pt(a[t]+'0');return *this;}}out;}using namespace IO;
#define N 111
int n,a[N],t;
int main(){
    in>>n;ll s=0;
    Fur(i,1,n)in>>a[i],s+=a[i];
    s/=n;
    Fur(i,1,n)a[i]=a[i-1]-a[i]+s;
    sort(a+1,a+n+1);
    t=a[(n>>1)+1];s=0;
    Fur(i,1,n)s+=abs(a[i]-t);
    out<<s<<ln;
}

3.孤岛营救问题

背包+状态压缩

N很小

开三维保存状态$d[x][y][s]$,走到$x,y$,拥有钥匙状态为$s$的最小花费是多少。

$map[x_1][y_1][x_2][y_2]$存墙

坑点:

  1. 一个点可以放多个钥匙
  2. 初始点可以放钥匙
#include<cstdio>
#include<ctype.h>
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC target("sse,sse2,avx,avx2,popcnt,tune=native")
#define il __inline__ __attribute__ ((always_inline))
#define rg register
#define Fur(i,x,y) for(rg int i=x;i<=y;i++)
using namespace std;
namespace IO{const char* ln="\n";const int str=1<<20;struct IN{char buf[str],*s,*t;bool _;IN():s(buf),t(buf),_(0){}il char gc(){return s==t&&((t=(s=buf)+fread(buf,1,str,stdin))==s)?EOF:(*s++);}IN&operator>>(char&ch){if(_)return *this;char c;while((c=gc())!=EOF&&isspace(c));if(c==EOF)_=1;else ch=c;return *this;}IN& operator>>(char* ch){if(_)return *this;char c;while((c=gc())!=EOF&&isspace(c));if(c==EOF)return _=1,*this;*ch=c;ch++;while((c=gc())!=EOF&&!isspace(c))*ch=c,ch++;if(c==EOF)_=1;return *this;}template<typename T>IN&operator>>(T&x){if(_)return *this;char c=gc();bool ff=0;while(c!=EOF&&(c<'0'||c>'9'))ff^=(c=='-'),c=gc();if(c==EOF){_=1;return *this;}x=0;while(c!=EOF&&'0'<=c&&c<='9')x=(x<<3)+(x<<1)+c-48,c=gc();if(c==EOF)_=1;if(ff)x=-x;return *this;}}in;struct OUT{char buf[str],*s,*t;OUT():s(buf),t(buf+str){}~OUT(){fwrite(buf,1,s-buf,stdout);}void pt(char c){(s==t)?(fwrite(s=buf,1,str,stdout),*s++=c):(*s++=c);}OUT&operator<<(const char*s){while(*s)pt(*s++);return *this;}OUT&operator<<(char*s){while(*s)pt(*s++);return *this;}template<typename T>OUT&operator<<(T x){if(!x)return pt('0'),*this;if(x<0)pt('-'),x=-x;char a[30],t=0;while(x)a[t++]=x%10,x/=10;while(t--)pt(a[t]+'0');return *this;}}out;}using namespace IO;
#define N 12
int n,m,k,P,S;
int d[N][N][1<<N],wa[N][N][N][N],a[N][N][N];
int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0},p[1000001],q[1000001],o[1000001];
int bfs(){
    int h=0,t=1,x,y,s,nx,ny,ns;
    p[0]=1;q[0]=1;o[0]=1;d[1][1][1]=1;
    Fur(i,1,a[1][1][0])d[1][1][1]|=(1<<a[1][1][i]);
    while(h<t){
        x=p[h];y=q[h];s=o[h++];
        Fur(i,0,3){
            nx=x+dx[i];ny=y+dy[i];
            if(nx<1||ny<1||nx>n||ny>m||!(s&(1<<wa[x][y][nx][ny])))continue;
            ns=s;Fur(j,1,a[nx][ny][0])ns|=(1<<a[nx][ny][j]);
            if(!d[nx][ny][ns]){
                d[nx][ny][ns]=d[x][y][s]+1;
                if(nx==n&&ny==m)return d[x][y][s];
                p[t]=nx,q[t]=ny,o[t++]=ns;
            }
        }
    }
    return -1;
}
int main(){
    in>>n>>m>>P>>k;
    int x,y,xx,yy,t;
    Fur(i,1,k){
        in>>x>>y>>xx>>yy>>t;
        if(!t)t=P+1;
        wa[xx][yy][x][y]=wa[x][y][xx][yy]=t;
    }
    in>>S;
    Fur(i,1,S)in>>x>>y>>a[x][y][++a[x][y][0]];
    out<<bfs()<<ln;
}

4. 魔术球问题

转换的思路很巧妙。

考虑一个点:

  1. 放在一根新的柱子上
  2. 放在与它加起来是完全平方数的点上

这样一看,如果一个柱子可以以某个点开始,也可以以某个点结束,那么一个点$x$就要拆成两个点$(x,x’)$

对于1,我们把源点与$x$连一条边权为1的边,把$x’$与汇点连一条边权为1的边

对于2,我们把能与$x$组成平方数的点与$x’​$连一条边。

当连完边后最大流无法增广时说明得新建一根柱子,如果柱子数$>n$那就说明无法继续添加数了。

关于输出,就自己看着代码意会意会吧$Q\omega Q$

#include<bits/stdc++.h>
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC target("sse,sse2,avx,avx2,popcnt,tune=native")
#define il __inline__ __attribute__ ((always_inline))
#define rg register
#define MB template <class T>
#define Fur(i,x,y) for(rg int i=x;i<=y;i++)
#define clr(x,y) memset(x,y,sizeof(x))
#define inf 2000000000
#define fl(i,x) for(rg int i=head[x],to;to=e[i].to,i;i=e[i].nxt)
MB T MIN(T x,T y){return x<=y?x:y;}
using namespace std;
namespace IO{const char* ln="\n";const int str=1<<20;struct IN{char buf[str],*s,*t;bool _;IN():s(buf),t(buf),_(0){}il char gc(){return s==t&&((t=(s=buf)+fread(buf,1,str,stdin))==s)?EOF:(*s++);}IN&operator>>(char&ch){if(_)return *this;char c;while((c=gc())!=EOF&&isspace(c));if(c==EOF)_=1;else ch=c;return *this;}IN& operator>>(char* ch){if(_)return *this;char c;while((c=gc())!=EOF&&isspace(c));if(c==EOF)return _=1,*this;*ch=c;ch++;while((c=gc())!=EOF&&!isspace(c))*ch=c,ch++;if(c==EOF)_=1;return *this;}template<typename T>IN&operator>>(T&x){if(_)return *this;char c=gc();bool ff=0;while(c!=EOF&&(c<'0'||c>'9'))ff^=(c=='-'),c=gc();if(c==EOF){_=1;return *this;}x=0;while(c!=EOF&&'0'<=c&&c<='9')x=(x<<3)+(x<<1)+c-48,c=gc();if(c==EOF)_=1;if(ff)x=-x;return *this;}}in;struct OUT{char buf[str],*s,*t;OUT():s(buf),t(buf+str){}~OUT(){fwrite(buf,1,s-buf,stdout);}void pt(char c){(s==t)?(fwrite(s=buf,1,str,stdout),*s++=c):(*s++=c);}OUT&operator<<(const char*s){while(*s)pt(*s++);return *this;}OUT&operator<<(char*s){while(*s)pt(*s++);return *this;}template<typename T>OUT&operator<<(T x){if(!x)return pt('0'),*this;if(x<0)pt('-'),x=-x;char a[30],t=0;while(x)a[t++]=x%10,x/=10;while(t--)pt(a[t]+'0');return *this;}}out;}using namespace IO;
#define N 10010
int n,m,st,ed,cnt;
int head[N],d[N],q[N],top[N],nex[N];
struct edge{int to,nxt,w;}e[100011];
void add(int x,int y,int w){
    e[++cnt].to=y;e[cnt].w=w;e[cnt].nxt=head[x];head[x]=cnt;
    e[++cnt].to=x;e[cnt].w=0;e[cnt].nxt=head[y];head[y]=cnt;
}
bool bfs(){
    int h=0,t=1,x;
    clr(d,0);d[q[h]=st]=1;
    while(h<t){
        x=q[h++];if(x==ed)return 1;
        fl(i,x)if(e[i].w&&!d[to]){
            d[to]=d[x]+1;
            q[t++]=to;
        }
    }
    return 0;
}
int dfs(int x,int mf){
    if(x==ed)return mf;
    int us=0,w;
    fl(i,x)
    if(e[i].w&&d[to]==d[x]+1){
        w=dfs(to,MIN(mf-us,e[i].w));
        e[i].w-=w;e[i^1].w+=w;
        us+=w;if(to!=ed)nex[x>>1]=to>>1;
        if(us==mf)return mf;
    }
    if(!us)d[x]=-1;
    return us;
}
int work(){int ans=0;while(bfs())ans+=dfs(st,inf);return ans;}
bool v[N];
int main(){
    in>>n;
    st=N-2;ed=N-1;
    int d=0,tot=0,t;
    while(tot<=n){
        ++d;
        add(st,d<<1,1);add(d<<1|1,ed,1);
        for(rg int i=sqrt(d)+1;i*i<(d<<1);i++)add((i*i-d)<<1,d<<1|1,1);
        if(!work())top[++tot]=d;
    }
    out<<(--d)<<ln;
    Fur(i,1,n)
    if(!v[top[i]]){
        v[t=top[i]]=1;
        while(t)out<<t<<" ",v[t=nex[t]]=1;
        out<<ln;
    }
}

5. 软件补丁问题

最短路+状态压缩

将每个补丁状态压缩,然后跑最短路。

因为边太多,所以枚举就可以了

#include<bits/stdc++.h>
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC target("sse,sse2,avx,avx2,popcnt,tune=native")
#define il __inline__ __attribute__ ((always_inline))
#define rg register
#define MB template <class T>
#define Fur(i,x,y) for(rg int i=x;i<=y;i++)
#define clr(x,y) memset(x,y,sizeof(x))
#define inf 2000000000
#define fl(i,x) for(rg int i=head[x],to;to=e[i].to,i;i=e[i].nxt)
MB T MIN(T x,T y){return x<=y?x:y;}
using namespace std;
namespace IO{const char* ln="\n";const int str=1<<20;struct IN{char buf[str],*s,*t;bool _;IN():s(buf),t(buf),_(0){}il char gc(){return s==t&&((t=(s=buf)+fread(buf,1,str,stdin))==s)?EOF:(*s++);}IN&operator>>(char&ch){if(_)return *this;char c;while((c=gc())!=EOF&&isspace(c));if(c==EOF)_=1;else ch=c;return *this;}IN& operator>>(char* ch){if(_)return *this;char c;while((c=gc())!=EOF&&isspace(c));if(c==EOF)return _=1,*this;*ch=c;ch++;while((c=gc())!=EOF&&!isspace(c))*ch=c,ch++;if(c==EOF)_=1;return *this;}template<typename T>IN&operator>>(T&x){if(_)return *this;char c=gc();bool ff=0;while(c!=EOF&&(c<'0'||c>'9'))ff^=(c=='-'),c=gc();if(c==EOF){_=1;return *this;}x=0;while(c!=EOF&&'0'<=c&&c<='9')x=(x<<3)+(x<<1)+c-48,c=gc();if(c==EOF)_=1;if(ff)x=-x;return *this;}}in;struct OUT{char buf[str],*s,*t;OUT():s(buf),t(buf+str){}~OUT(){fwrite(buf,1,s-buf,stdout);}void pt(char c){(s==t)?(fwrite(s=buf,1,str,stdout),*s++=c):(*s++=c);}OUT&operator<<(const char*s){while(*s)pt(*s++);return *this;}OUT&operator<<(char*s){while(*s)pt(*s++);return *this;}template<typename T>OUT&operator<<(T x){if(!x)return pt('0'),*this;if(x<0)pt('-'),x=-x;char a[30],t=0;while(x)a[t++]=x%10,x/=10;while(t--)pt(a[t]+'0');return *this;}}out;}using namespace IO;
#define N 22
int n,m;
int d[1<<N],b1[101],b2[101],f1[101],f2[101],c[101];
struct cmp{bool operator()(int x,int y){return d[x]>d[y];}};
priority_queue<int,vector<int>,cmp>q;
bool v[1<<N];
void spfa(){
    clr(d,126);
    d[(1<<n)-1]=0;q.push((1<<n)-1);
    while(!q.empty()){
        rg int x=q.top(),to;q.pop();v[x]=0;
        Fur(i,1,m)
        if((b1[i]&x)==b1[i]&&!(b2[i]&x)){
            to=(x&(~f1[i]))|f2[i];
            if(d[x]+c[i]<d[to]){
                d[to]=d[x]+c[i];
                if(!v[to])q.push(to),v[to]=1;
            }
        }
    }
    if(d[0]==2122219134)d[0]=0;
}
int main(){
    in>>n>>m;
    char s1[N],s2[N];
    Fur(i,1,m){
        in>>c[i]>>s1>>s2;
        Fur(j,0,n-1){
            if(s1[j]=='+')b1[i]|=(1<<j);
            if(s1[j]=='-')b2[i]|=(1<<j);
            if(s2[j]=='-')f1[i]|=(1<<j);
            if(s2[j]=='+')f2[i]|=(1<<j);
        }
    }
    spfa();
    out<<d[0]<<ln;
}

6. 圆桌问题

和飞行员配对方案问题差不多嘛。

也是网络流二分图,再加个输出。

大概的套路就是匹配的直接都连边1,然后源点汇点什么的按题意写就可以了

输出的就是有连边的,而且这条边已经用过了(e[i^1]))。

#include<bits/stdc++.h>
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC target("sse,sse2,avx,avx2,popcnt,tune=native")
#define il __inline__ __attribute__ ((always_inline))
#define rg register
#define MB template <class T>
#define Fur(i,x,y) for(rg int i=x;i<=y;i++)
#define clr(x,y) memset(x,y,sizeof(x))
#define inf 2000000000
#define fl(i,x) for(rg int i=head[x],to;to=e[i].to,i;i=e[i].nxt)
MB T MIN(T x,T y){return x<=y?x:y;}
using namespace std;
namespace IO{const char* ln="\n";const int str=1<<20;struct IN{char buf[str],*s,*t;bool _;IN():s(buf),t(buf),_(0){}il char gc(){return s==t&&((t=(s=buf)+fread(buf,1,str,stdin))==s)?EOF:(*s++);}IN&operator>>(char&ch){if(_)return *this;char c;while((c=gc())!=EOF&&isspace(c));if(c==EOF)_=1;else ch=c;return *this;}IN& operator>>(char* ch){if(_)return *this;char c;while((c=gc())!=EOF&&isspace(c));if(c==EOF)return _=1,*this;*ch=c;ch++;while((c=gc())!=EOF&&!isspace(c))*ch=c,ch++;if(c==EOF)_=1;return *this;}template<typename T>IN&operator>>(T&x){if(_)return *this;char c=gc();bool ff=0;while(c!=EOF&&(c<'0'||c>'9'))ff^=(c=='-'),c=gc();if(c==EOF){_=1;return *this;}x=0;while(c!=EOF&&'0'<=c&&c<='9')x=(x<<3)+(x<<1)+c-48,c=gc();if(c==EOF)_=1;if(ff)x=-x;return *this;}}in;struct OUT{char buf[str],*s,*t;OUT():s(buf),t(buf+str){}~OUT(){fwrite(buf,1,s-buf,stdout);}void pt(char c){(s==t)?(fwrite(s=buf,1,str,stdout),*s++=c):(*s++=c);}OUT&operator<<(const char*s){while(*s)pt(*s++);return *this;}OUT&operator<<(char*s){while(*s)pt(*s++);return *this;}template<typename T>OUT&operator<<(T x){if(!x)return pt('0'),*this;if(x<0)pt('-'),x=-x;char a[30],t=0;while(x)a[t++]=x%10,x/=10;while(t--)pt(a[t]+'0');return *this;}}out;}using namespace IO;
#define N 1001
int n,m,st,ed,cnt=1;
int head[N],d[N],q[N];
struct edge{int to,nxt,w;}e[1000011];
void add(int x,int y,int w){
    e[++cnt].to=y;e[cnt].w=w;e[cnt].nxt=head[x];head[x]=cnt;
    e[++cnt].to=x;e[cnt].w=0;e[cnt].nxt=head[y];head[y]=cnt;
}
bool bfs(){
    int h=0,t=1,x;
    clr(d,0);d[q[h]=st]=1;
    while(h<t){
        x=q[h++];if(x==ed)return 1;
        fl(i,x)if(e[i].w&&!d[to]){
            d[to]=d[x]+1;
            q[t++]=to;
        }
    }
    return 0;
}
int dfs(int x,int mf){
    if(x==ed)return mf;
    int us=0,w;
    fl(i,x)
    if(e[i].w&&d[to]==d[x]+1){
        w=dfs(to,MIN(mf-us,e[i].w));
        e[i].w-=w;e[i^1].w+=w;
        us+=w;
        if(us==mf)return mf;
    }
    if(!us)d[x]=-1;
    return us;
}
int main(){
    in>>m>>n;
    st=N-2;ed=N-1;
    int x,sum=0;
    Fur(i,1,m){
        in>>x,add(st,i,x),sum+=x;
        Fur(j,m+1,m+n)add(i,j,1);
    }
    Fur(i,m+1,m+n)in>>x,add(i,ed,x);
    while(bfs())sum-=dfs(st,inf);
    if(sum)out<<"0\n";
    else{
        out<<"1\n";
        Fur(i,1,m){
            fl(j,i)if(to!=st&&to!=ed&&e[j^1].w)out<<to-m<<" ";
            out<<ln;
        }
    }
}

7.试题库问题

也是水题吧。

用网络流可能比二分图容易写点。

套路和上一道一样,稍微改一下就可以了。

#include<bits/stdc++.h>
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC target("sse,sse2,avx,avx2,popcnt,tune=native")
#define il __inline__ __attribute__ ((always_inline))
#define rg register
#define MB template <class T>
#define Fur(i,x,y) for(rg int i=x;i<=y;i++)
#define clr(x,y) memset(x,y,sizeof(x))
#define inf 2000000000
#define fl(i,x) for(rg int i=head[x],to;to=e[i].to,i;i=e[i].nxt)
MB T MIN(T x,T y){return x<=y?x:y;}
using namespace std;
namespace IO{const char* ln="\n";const int str=1<<20;struct IN{char buf[str],*s,*t;bool _;IN():s(buf),t(buf),_(0){}il char gc(){return s==t&&((t=(s=buf)+fread(buf,1,str,stdin))==s)?EOF:(*s++);}IN&operator>>(char&ch){if(_)return *this;char c;while((c=gc())!=EOF&&isspace(c));if(c==EOF)_=1;else ch=c;return *this;}IN& operator>>(char* ch){if(_)return *this;char c;while((c=gc())!=EOF&&isspace(c));if(c==EOF)return _=1,*this;*ch=c;ch++;while((c=gc())!=EOF&&!isspace(c))*ch=c,ch++;if(c==EOF)_=1;return *this;}template<typename T>IN&operator>>(T&x){if(_)return *this;char c=gc();bool ff=0;while(c!=EOF&&(c<'0'||c>'9'))ff^=(c=='-'),c=gc();if(c==EOF){_=1;return *this;}x=0;while(c!=EOF&&'0'<=c&&c<='9')x=(x<<3)+(x<<1)+c-48,c=gc();if(c==EOF)_=1;if(ff)x=-x;return *this;}}in;struct OUT{char buf[str],*s,*t;OUT():s(buf),t(buf+str){}~OUT(){fwrite(buf,1,s-buf,stdout);}void pt(char c){(s==t)?(fwrite(s=buf,1,str,stdout),*s++=c):(*s++=c);}OUT&operator<<(const char*s){while(*s)pt(*s++);return *this;}OUT&operator<<(char*s){while(*s)pt(*s++);return *this;}template<typename T>OUT&operator<<(T x){if(!x)return pt('0'),*this;if(x<0)pt('-'),x=-x;char a[30],t=0;while(x)a[t++]=x%10,x/=10;while(t--)pt(a[t]+'0');return *this;}}out;}using namespace IO;
#define N 2001
int n,k,st,ed,cnt=1;
int head[N],d[N],q[N];
struct edge{int to,nxt,w;}e[1000011];
void add(int x,int y,int w){
    e[++cnt].to=y;e[cnt].w=w;e[cnt].nxt=head[x];head[x]=cnt;
    e[++cnt].to=x;e[cnt].w=0;e[cnt].nxt=head[y];head[y]=cnt;
}
bool bfs(){
    int h=0,t=1,x;
    clr(d,0);d[q[h]=st]=1;
    while(h<t){
        x=q[h++];if(x==ed)return 1;
        fl(i,x)if(e[i].w&&!d[to]){
            d[to]=d[x]+1;
            q[t++]=to;
        }
    }
    return 0;
}
int dfs(int x,int mf){
    if(x==ed)return mf;
    int us=0,w;
    fl(i,x)
    if(e[i].w&&d[to]==d[x]+1){
        w=dfs(to,MIN(mf-us,e[i].w));
        e[i].w-=w;e[i^1].w+=w;
        us+=w;
        if(us==mf)return mf;
    }
    if(!us)d[x]=-1;
    return us;
}
int main(){
    in>>k>>n;
    st=N-2;ed=N-1;
    int x,t,sum=0;
    Fur(i,1,k)in>>x,add(st,i,x),sum+=x;
    Fur(i,k+1,k+n){
        add(i,ed,1);
        in>>t;while(t--)in>>x,add(x,i,1);
    }
    while(bfs())sum-=dfs(st,inf);
    if(sum)out<<"No Solution!\n";
    else Fur(i,1,k){
            out<<i<<": ";
            fl(j,i)if(to!=st&&to!=ed&&e[j^1].w)out<<to-k<<" ";
            out<<ln;
        }
}