Shinbokuow - 不试着去思考的话，不就已经死去了吗

BZOJ2673: [Wf2011]Chips Challenge 网络流+费用流

9 年前

Tags: 网络流费用流有上下界网络流
Posted in water | 7 Comments

Codechef 14.12 RIN 网络流+最小割

9 年前

Tags: 网络流最小割
Posted in Something | 5 Comments

Codechef 14.6 TWOCOMP 树链求交+网络流

9 年前

Tags: 树链求交网络流
Posted in Something | 0 Comments

BZOJ4177: Mike的农场最小割+网络流

10 年前

Tags: 网络流最小割
Posted in BZOJ | 2 Comments

BZOJ4205: 卡牌配对

10 年前

题解:

首先暴力连边匹配肯定是不行的...

由于 $200$ 以内的质数仅有 $46$ 个,我们构造三类点 $ab(p_1,p_2),ac(p_1,p_2),bc(p_1,p_2)$ 分别表示参数1能被 $p_1$ 整除,参数2能被 $p_2$ 整除,剩下的依此类推.

然后对于左侧的点向符合条件的中间点连边.

对于右侧的点从符合条件的中间点连边.

这样做事实上是边分组,很显然是正确的.

直接用dinic玩就行了.

代码:

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

#include<cstdio>
#include<cctype>
#include<cstring>
#include<climits>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
  
#define inf 0x3f3f3f3f
  
struct Solver{
    static const int V=100010;
    static const int E=3000010;
    int head[V],next[E],flow[E],end[E],ind,d[V];
    inline void reset(){
        memset(head,-1,sizeof head);
        ind=0;
    }
    inline void addedge(int a,int b,int f){
        int q=ind++;
        end[q]=b;
        next[q]=head[a];
        head[a]=q;
        flow[q]=f;
    }
    inline void make(int a,int b,int f){
        addedge(a,b,f);
        addedge(b,a,0);
    }
    inline bool bfs(int s,int t){
        static int q[V];
        int fr=0,ta=0;
        memset(d,-1,sizeof d);
        d[q[ta++]=s]=0;
        while(fr!=ta){
            int i=q[fr++];
            for(int j=head[i];j!=-1;j=next[j])
                if(flow[j]&&d[end[j]]==-1)
                    d[q[ta++]=end[j]]=d[i]+1;
        }
        return d[t]!=-1;
    }
    inline int dinic(int p,int t,int Maxflow){
        if(p==t)
            return Maxflow;
        int last=Maxflow;
        for(int j=head[p];j!=-1;j=next[j])
            if(flow[j]&&d[end[j]]==d[p]+1){
                int to=dinic(end[j],t,flow[j]>last?last:flow[j]);
                if(to){
                    flow[j]-=to;
                    flow[j^1]+=to;
                    if(!(last-=to))
                        return Maxflow;
                }
            }
        d[p]=-1;
        return Maxflow-last;
    }
    inline int Maxflow(int s,int t){
        int re=0;
        while(bfs(s,t))
            re+=dinic(s,t,inf);
        return re;
    }
}g;
  
#define N 210
int p[N],cnt;
bool np[N];
inline void pre(){
    int i,j;
    for(i=2;i<=200;++i){
        if(!np[i])
            p[++cnt]=i;
        for(j=1;j<=cnt&&p[j]*i<=200;++j){
            np[i*p[j]]=1;
            if(i%p[j]==0)
                break;
        }
    }
}
int a[51][51],b[51][51],c[51][51];
int x[2][30010],y[2][30010],z[2][30010];
  
vector<int>v[N];
int main(){
    pre();
    int n,m;
    cin>>n>>m;
    int i,j,k;
    for(i=1;i<=n;++i)
        scanf("%d%d%d",&x[0][i],&y[0][i],&z[0][i]);
    for(i=1;i<=m;++i)
        scanf("%d%d%d",&x[1][i],&y[1][i],&z[1][i]);
      
    for(i=1;i<=200;++i)
        for(j=1;j<=cnt;++j)
            if(i%p[j]==0)
                v[i].push_back(j);
      
    int id=n+m;
    for(i=1;i<=cnt;++i)
        for(j=1;j<=cnt;++j){
            a[i][j]=++id;
            b[i][j]=++id;
            c[i][j]=++id;
        }
      
    int s=0,t=++id;
      
    g.reset();
    for(i=1;i<=n;++i)
        g.make(s,i,1);
    for(i=1;i<=m;++i)
        g.make(n+i,t,1);
      
    int p,q;
    for(i=1;i<=n;++i){
        for(j=0;j<v[x[0][i]].size();++j)
            for(k=0;k<v[y[0][i]].size();++k){
                p=v[x[0][i]][j];
                q=v[y[0][i]][k];
                g.make(i,a[p][q],1);
            }
        for(j=0;j<v[x[0][i]].size();++j)
            for(k=0;k<v[z[0][i]].size();++k){
                p=v[x[0][i]][j];
                q=v[z[0][i]][k];
                g.make(i,b[p][q],1);
            }
        for(j=0;j<v[y[0][i]].size();++j)
            for(k=0;k<v[z[0][i]].size();++k){
                p=v[y[0][i]][j];
                q=v[z[0][i]][k];
                g.make(i,c[p][q],1);
            }
    }
    for(i=1;i<=m;++i){
        for(j=0;j<v[x[1][i]].size();++j)
            for(k=0;k<v[y[1][i]].size();++k){
                p=v[x[1][i]][j];
                q=v[y[1][i]][k];
                g.make(a[p][q],n+i,1);
            }
        for(j=0;j<v[x[1][i]].size();++j)
            for(k=0;k<v[z[1][i]].size();++k){
                p=v[x[1][i]][j];
                q=v[z[1][i]][k];
                g.make(b[p][q],n+i,1);
            }
        for(j=0;j<v[y[1][i]].size();++j)
            for(k=0;k<v[z[1][i]].size();++k){
                p=v[y[1][i]][j];
                q=v[z[1][i]][k];
                g.make(c[p][q],n+i,1);
            }
    }
      
    cout<<g.Maxflow(s,t)<<endl;
      
    return 0;
}

Tags: 网络流数学
Posted in BZOJ | 0 Comments

BZOJ1443: [JSOI2009]游戏Game 二分图+博弈论+网络流

10 年前

思路:

首先将图黑白二染色变成二分图.

然后求出一组最大匹配.

如果某个点不在匹配中,那么先手选择这个点.

那么后手只能走向一个匹配点(否则就不是最大匹配了).于是先手就可以沿着匹配边走回来.

那么此时如果后手还能走的话,就必定走到一个匹配点上.(否则就存在增广路了).于是先手又沿着匹配边走回来.

最后总是后手无路可走.因此先手必胜.

因此如果某个点不是最大匹配的必须点.就可以选择这个点.

如何找出这个呢?

在残量网络上,从 $S$ 出发能够遍历到的左端的点,以及从 $T$ 出发能够反向遍历到的右端的点.

证明的话,就是如果能够遍历到,就证明可以被换掉,而使得匹配数不减少.(稍微脑补一下)

(注意总点数要开2W,我不知道为什么)

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
  
#define INF ~0U>>1
struct Solver{
    static const int V=20010;
    static const int E=V<<2;
    int head[V],next[E],end[E],flow[E],ind;
    int gap[V],d[V],stk[V],top,cur[V];
    inline void reset(){
        ind=top=0,memset(head,-1,sizeof head);
    }
    inline void addedge(int a,int b,int f){
        int q=ind++;
        end[q]=b,next[q]=head[a],head[a]=q,flow[q]=f;
    }
    inline void make(int a,int b,int f){
        //printf("%d %d %d\n",a,b,f);
        addedge(a,b,f),addedge(b,a,0);
    }
    inline void bfs(int T){
        static int q[V];
        int fr=0,ta=0;
        memset(d,-1,sizeof d),memset(gap,0,sizeof gap),++gap[d[T]=0],q[ta++]=T;
        while(fr^ta){
            int i=q[fr++];
            for(int j=head[i];j!=-1;j=next[j])if(d[end[j]]==-1)
                ++gap[d[end[j]]=d[i]+1],q[ta++]=end[j];
        }
    }
    inline int Maxflow(int S,int T){
        int re=0,ins,Min,i,u=S;
        bfs(T),memcpy(cur,head,sizeof cur);
        while(d[S]<T-S+1){
            if(u==T){
                for(Min=INF,i=0;i<top;++i)if(Min>flow[stk[i]])Min=flow[stk[i]],ins=i;
                for(re+=Min,i=0;i<top;++i)flow[stk[i]]-=Min,flow[stk[i]^1]+=Min;
                u=end[stk[top=ins]^1];
            }
            if(u!=T&&!gap[d[u]-1])break;
            bool find=0;
            for(int&j=cur[u];j!=-1;j=next[j])if(flow[j]&&d[end[j]]+1==d[u]){
                find=1,ins=j;break;
            }
            if(find){
                stk[top++]=cur[u]=ins,u=end[ins];
            }
            else{
                Min=T-S+1;
                for(int j=head[u];j!=-1;j=next[j])if(flow[j]&&d[end[j]]<Min)
                    cur[u]=j,Min=d[end[j]];
                if(!--gap[d[u]])break;
                ++gap[d[u]=Min+1];
                if(u!=S)u=end[stk[--top]^1];
            }
        }
        return re;
    }
}Stg;
  
#define N 110
char s[N];
int lab[N][N],x[N*N],y[N*N];
  
int res[N*N],nums;
  
bool vis[N*N];
inline void bfs(int S,bool rev){
    static int q[N*N];
    int fr=0,ta=0;
    memset(vis,0,sizeof vis),vis[S]=1,q[ta++]=S;
    while(fr^ta){
        int i=q[fr++];
        for(int j=Stg.head[i];j!=-1;j=Stg.next[j])if(Stg.flow[j^rev]&&!vis[Stg.end[j]])
            vis[Stg.end[j]]=1,q[ta++]=Stg.end[j];
    }
}
  
int main(){
    int n,m;scanf("%d%d",&n,&m);
    register int i,j;
    int cnt=0;
    for(i=1;i<=n;++i){
        scanf("%s",s+1);
        for(j=1;j<=m;++j)if(s[j]!='#')lab[i][j]=++cnt,x[cnt]=i,y[cnt]=j;
    }
      
    int S=0,T=cnt+1,num0=0,num1=0;
    Stg.reset();
    for(i=1;i<=n;++i)for(j=1;j<=m;++j)if(lab[i][j]){
        if((i+j)&1){
            ++num1;
            Stg.make(S,lab[i][j],1);
            if(lab[i-1][j])Stg.make(lab[i][j],lab[i-1][j],INF);
            if(lab[i+1][j])Stg.make(lab[i][j],lab[i+1][j],INF);
            if(lab[i][j-1])Stg.make(lab[i][j],lab[i][j-1],INF);
            if(lab[i][j+1])Stg.make(lab[i][j],lab[i][j+1],INF);
        }
        else
            ++num0,Stg.make(lab[i][j],T,1);
    }
      
    if(num0==0&&num1==0){
        puts("LOSE");
        return 0;
    }
      
    int re=Stg.Maxflow(S,T);
      
    /*for(i=S;i<=T;++i)for(j=Stg.head[i];j!=-1;j=Stg.next[j])
        printf("%d %d %d\n",i,Stg.end[j],Stg.flow[j]);*/
    if(num0==num1&&re==num0){
        puts("LOSE");
        return 0;
    }
    puts("WIN");
      
    bfs(S,0);
    for(i=1;i<=n;++i)for(j=1;j<=m;++j)if(lab[i][j]&&((i+j)&1)&&vis[lab[i][j]])res[++nums]=lab[i][j];
    bfs(T,1);
    for(i=1;i<=n;++i)for(j=1;j<=m;++j)if(lab[i][j]&&((i+j)%2==0)&&vis[lab[i][j]])res[++nums]=lab[i][j];
    sort(res+1,res+nums+1);
      
    for(i=1;i<=nums;++i){
        printf("%d %d\n",x[res[i]],y[res[i]]);
    }
      
    return 0;
}

Tags: 二分图博弈论网络流
Posted in BZOJ | 2 Comments

BZOJ1570:[JSOI2008]Blue Mary的旅行暴力+网络流

10 年前

思路:

暴力枚举答案,然后将点分层,边总是从该层连向下一层.

然后判断最大流是不是满足题意.

具体连边看代码.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
  
#define INF ~0U>>1
struct Solver{
    static const int V=50*100;
    static const int E=2450*100*2;
    int head[V],next[E],end[E],flow[E],ind;
    int d[V],gap[V],stk[V],top,cur[V];
    inline void reset(){
        ind=top=0,memset(head,-1,sizeof head);
    }
    inline void addedge(int a,int b,int f){
        int q=ind++;end[q]=b,next[q]=head[a],head[a]=q,flow[q]=f;
    }
    inline void make(int a,int b,int f){
        /*printf("%d %d %d\n",a,b,f);*/addedge(a,b,f),addedge(b,a,0);
    }
    inline void bfs(int T){
        static int q[V];int fr=0,ta=0;
        memset(gap,0,sizeof gap),memset(d,-1,sizeof d),++gap[d[T]=0],q[ta++]=T;
        while(fr^ta){
            int i=q[fr++];
            for(int j=head[i];j!=-1;j=next[j])if(d[end[j]]==-1)
                ++gap[d[end[j]]=d[i]+1],q[ta++]=end[j];
        }
    }
    inline int Maxflow(int S,int T){
        bfs(T),memcpy(cur,head,sizeof cur);
        int re=0,Min,ins,i,u=S;
        while(d[S]<T-S+1){
            if(u==T){
                for(Min=INF,i=0;i<top;++i)if(Min>flow[stk[i]])ins=i,Min=flow[stk[i]];
                for(re+=Min,i=0;i<top;++i)flow[stk[i]]-=Min,flow[stk[i]^1]+=Min;
                u=end[stk[top=ins]^1];
            }
            if(u!=T&&!gap[d[u]-1])break;
            bool find=0;
            for(int&j=cur[u];j!=-1;j=next[j])if(flow[j]&&d[end[j]]+1==d[u]){
                find=1,ins=j;break;
            }
            if(find){stk[top++]=cur[u]=ins,u=end[ins];}
            else{
                Min=T-S+1;
                for(int j=head[u];j!=-1;j=next[j])if(flow[j]&&d[end[j]]<Min)
                    cur[u]=j,Min=d[end[j]];
                if(!--gap[d[u]])break;
                ++gap[d[u]=Min+1];
                if(u!=S)u=end[stk[--top]^1];
            }
        }
        return re;
    }
}Stg;
  
struct Edge{
    int u,v,f;
}E[2510];
  
#define get(x,dep) ((dep-1)*n+x)
int main(){
    int n,m,T;scanf("%d%d%d",&n,&m,&T);
    register int i,j;
    for(i=1;i<=m;++i)scanf("%d%d%d",&E[i].u,&E[i].v,&E[i].f);
      
    int re;
    for(re=1;;++re){
        Stg.reset();
        for(i=1;i<=m;++i)for(j=1;j<=re;++j)Stg.make(get(E[i].u,j),get(E[i].v,j+1),E[i].f);
        for(j=1;j<=re;++j)Stg.make(0,get(1,j),INF);
        for(j=2;j<=re+1;++j)Stg.make(get(n,j),n*(re+1)+1,INF);
        int now=Stg.Maxflow(0,n*(re+1)+1);
        //printf("%d\n",now);
        if(now>=T)break;
    }
      
    printf("%d\n",re);
      
    return 0;
}

Tags: 暴力网络流
Posted in BZOJ | 0 Comments

BZOJ1189:[HNOI2007]紧急疏散evacuate 二分+最大流

10 年前

思路:

首先bfs求出每个空地到每个门的最短距离,注意中间不能经过任何门.好像是原题说过只要经过门就算是退出了.

随后我们二分答案,从原点到每块空地连容量为1的边,从每扇门到汇点连容量为(当前二分的答案)时间的边,对于每块空地和每扇门,若距离不超过时间,则从空地到门连一条容量为1的边.

好像唯一的trick就是从门到汇点的边?不过大家自己YY一下吧.

反正不难.

#include<cstdio>
#include<cstring>
#include<queue>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
  
#define INF 0x3f3f3f3f
  
#define N 21
#define M 21
int n,m;
char s[M];
  
int ty[N][M];
  
int d[N][M];
  
static const int dx[]={-1,1,0,0},dy[]={0,0,1,-1};
struct Ins{
    int x,y;
    Ins(){}
    Ins(int _x,int _y):x(_x),y(_y){}
};
void bfs(int x,int y){
    static queue<Ins>q;
    d[x][y]=0,q.push(Ins(x,y));
    while(!q.empty()){
        Ins tmp=q.front();q.pop();
        for(int k=0;k<4;++k){
            int nx=tmp.x+dx[k],ny=tmp.y+dy[k];
            if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&ty[nx][ny]==1&&d[nx][ny]==-1)
                d[nx][ny]=d[tmp.x][tmp.y]+1,q.push(Ins(nx,ny));
        }
    }
}
  
struct MaxflowSolver{
    static const int V=1010,E=200010;
    int head[V],next[E],end[E],flow[E],ind,d[V],inq[V];
    inline void reset(){ind=0,memset(head,-1,sizeof head);}
    inline void addedge(int a,int b,int f){int q=ind++;end[q]=b,next[q]=head[a],head[a]=q,flow[q]=f;}
    inline void make(int a,int b,int f){addedge(a,b,f),addedge(b,a,0);}
    inline bool bfs(int S,int T){
        static int q[V];int fr=0,ta=0;
        memset(d,-1,sizeof d),d[S]=0,q[ta++]=S;
        while(fr^ta){
            int i=q[fr++];for(int j=head[i];j!=-1;j=next[j])if(flow[j]&&d[end[j]]==-1)d[end[j]]=d[i]+1,q[ta++]=end[j];
        }return d[T]!=-1;
    }
    inline int dinic(int p,int T,int Maxflow){
        if(p==T)return Maxflow;
        int last=Maxflow;
        for(int j=head[p];j!=-1;j=next[j])if(flow[j]&&d[end[j]]==d[p]+1){
            int to=dinic(end[j],T,last>flow[j]?flow[j]:last);
            if(to){flow[j]-=to,flow[j^1]+=to;if(!(last-=to))return Maxflow;}
        }d[p]=-1;return Maxflow-last;
    }
    inline int Maxflow(int S,int T){
        int res=0;while(bfs(S,T))res+=dinic(S,T,INF);return res;
    }
}Stg;
  
int lab[N][M];
  
int main(){
    scanf("%d%d",&n,&m);register int i,j;
    for(i=1;i<=n;++i){
        scanf("%s",s+1);
        for(j=1;j<=m;++j)if(s[j]=='.')ty[i][j]=1;else if(s[j]=='D')ty[i][j]=2;
    }
      
    int id=0;for(i=1;i<=n;++i)for(j=1;j<=m;++j)if(ty[i][j])lab[i][j]=++id;
      
    int L=0,R=1<<30,mid;
    while(L<R){
        mid=(L+R)>>1;
        Stg.reset();
        int cnt=0;
        for(i=1;i<=n;++i)for(j=1;j<=m;++j)if(ty[i][j]==1)Stg.make(0,lab[i][j],1),++cnt;
        for(i=1;i<=n;++i)for(j=1;j<=m;++j)if(ty[i][j]==2)Stg.make(lab[i][j],n*m+1,mid);
        for(i=1;i<=n;++i)for(j=1;j<=m;++j)if(ty[i][j]==2){
            memset(d,-1,sizeof d),bfs(i,j);
            for(int p=1;p<=n;++p)for(int q=1;q<=m;++q)if(ty[p][q]==1&&d[p][q]!=-1)
                if(d[p][q]<=mid)Stg.make(lab[p][q],lab[i][j],1);
        }
        if(Stg.Maxflow(0,n*m+1)==cnt)R=mid;else L=mid+1;
    }
      
    if(L==1<<30)puts("impossible");else printf("%d",L);
    return 0;
}

Tags: 二分网络流
Posted in BZOJ | 0 Comments

BZOJ1822:[JSOI2010]Frozen Nova 冷冻波二分+计算几何+网络流

10 年前

思路:

一眼网络流,套一个二分就行了.

关键是如何判断巫妖和精灵之间能否有圆阻挡.

一开始我是进行了复杂的判断:如果线段平行于x轴或者平行于y轴直接特判;

否则求出圆心到直线的距离,如果距离不超过半径,则用一个简单的公式求出圆心到直线最近点的横坐标,利用这个横坐标与线段两个端点的横坐标比较,得出结果.

可是数据跟我想的根本不是一回事啊啊啊!

根本只需要判断距离啊啊啊!!而且相切的情况不算相交啊啊啊!!

什么坑爹数据,我是领教到了.

#include<cstdio>
#include<cstring>
#include<climits>
#include<iostream>
#include<algorithm>
using namespace std;
 
typedef long long LL;
 
#define INF 0x3f3f3f3f
 
#define N 210
#define M 210
#define P 210
 
struct MaxflowSolver{
    static const int V=410;
    static const int E=100010;
    int head[V],next[E],end[E],flow[E],ind,d[V];
    inline void reset(){ind=0,memset(head,-1,sizeof head);}
    inline void addedge(int a,int b,int f){int q=ind++;end[q]=b,next[q]=head[a],head[a]=q,flow[q]=f;}
    inline void make(int a,int b,int f){addedge(a,b,f),addedge(b,a,0);}
    inline bool bfs(int S,int T){
        static int q[V];int fr=0,ta=0;
        memset(d,-1,sizeof d),d[S]=0,q[ta++]=S;
        while(fr^ta){
            int i=q[fr++];for(int j=head[i];j!=-1;j=next[j])if(flow[j]&&d[end[j]]==-1)d[end[j]]=d[i]+1,q[ta++]=end[j];
        }return d[T]!=-1;
    }
    inline int dinic(int p,int T,int Maxflow){
        if(p==T)return Maxflow;
        int last=Maxflow;
        for(int j=head[p];j!=-1;j=next[j])if(flow[j]&&d[end[j]]==d[p]+1){
            int to=dinic(end[j],T,last>flow[j]?flow[j]:last);
            if(to){flow[j]-=to,flow[j^1]+=to;if(!(last-=to))return Maxflow;}
        }d[p]=-1;return Maxflow-last;
    }
    inline int Maxflow(int S,int T){
        int res=0;while(bfs(S,T))res+=dinic(S,T,INF);return res;
    }
}Stg;
int x1[N],y1[N],x2[M],y2[M],lim[N],cd[N],ox[P],oy[P],r[P];
 
int G[N][M];
 
inline int sqr(int x){return x*x;}
 
 
 
int main(){
    int n,m,p;scanf("%d%d%d",&n,&m,&p);register int i,j,k;
    for(i=1;i<=n;++i)scanf("%d%d%d%d",&x1[i],&y1[i],&lim[i],&cd[i]);
    for(i=1;i<=m;++i)scanf("%d%d",&x2[i],&y2[i]);
    for(i=1;i<=p;++i)scanf("%d%d%d",&ox[i],&oy[i],&r[i]);
     
    int a,b,c;
    for(i=1;i<=n;++i)for(j=1;j<=m;++j)if(sqr(x1[i]-x2[j])+sqr(y1[i]-y2[j])<=sqr(lim[i])){
        bool ok=1;
        for(k=1;k<=p&&ok;++k){
            a=y1[i]-y2[j],b=x2[j]-x1[i],c=(x1[i]-x2[j])*y1[i]-(y1[i]-y2[j])*x1[i];
            if((LL)(a*ox[k]+b*oy[k]+c)*(a*ox[k]+b*oy[k]+c)<(LL)r[k]*r[k]*(a*a+b*b))ok=0;
        }
        if(ok)G[i][j]=1;
    }
     
    int L=0,R=1<<30,mid;
    while(L<R){
        mid=(L+R)>>1;
        Stg.reset();
        for(i=1;i<=n;++i)Stg.make(0,i,mid/cd[i]+1);
        for(i=1;i<=m;++i)Stg.make(n+i,n+m+1,1);
        for(i=1;i<=n;++i)for(j=1;j<=m;++j)if(G[i][j])Stg.make(i,n+j,1);
        if(Stg.Maxflow(0,n+m+1)==m)R=mid;else L=mid+1;
    }
     
    if(L==1<<30)puts("-1");else printf("%d",L);
    return 0;
}

Tags: 二分计算几何网络流
Posted in BZOJ | 0 Comments

BZOJ3774:最优选择网络流

10 年前

思路:

首先由于是一个二分图,我们分为左右两部分.

...然后具体的建模自己看代码吧,真的是好神奇的思路...

我居然连这都想不出来真是混不下去了.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
  
static const int INF=0x3f3f3f3f;
struct MaxflowSolver{
    static const int V=5010;
    static const int E=80010;
    int head[V],next[E],end[E],flow[E],ind;
    int d[V];
    inline void reset(){ind=0,memset(head,-1,sizeof head);}
    inline void addedge(int a,int b,int f){int q=ind++;end[q]=b,next[q]=head[a],head[a]=q,flow[q]=f;}
    inline void make(int a,int b,int f){addedge(a,b,f),addedge(b,a,0);}
    inline bool bfs(int S,int T){
        static int q[V];int fr=0,ta=0;
        memset(d,-1,sizeof d),d[S]=0,q[ta++]=S;
        while(fr^ta){
            int i=q[fr++];for(int j=head[i];j!=-1;j=next[j])if(flow[j]&&d[end[j]]==-1)d[end[j]]=d[i]+1,q[ta++]=end[j];
        }return d[T]!=-1;
    }
    inline int dinic(int p,int T,int Maxflow){
        if(p==T)return Maxflow;
        int last=Maxflow;
        for(int j=head[p];j!=-1;j=next[j])if(flow[j]&&d[p]+1==d[end[j]]){
            int to=dinic(end[j],T,last>flow[j]?flow[j]:last);if(to)flow[j]-=to,flow[j^1]+=to,last-=to;
            if(!last)return Maxflow;
        }
        d[p]=-1;return Maxflow-last;
    }
    inline int Maxflow(int S,int T){
        int res=0;
        while(bfs(S,T))res+=dinic(S,T,INF);
        return res;
    }
}Stg;
  
int lab[51][51][2],a[51][51],b[51][51];
  
const int dx[]={-1,1,0,0},dy[]={0,0,-1,1};
  
int main(){
    int n,m;scanf("%d%d",&n,&m);register int i,j,k;int x,res=0;
      
    int id=0;for(i=1;i<=n;++i)for(j=1;j<=m;++j)lab[i][j][0]=++id,lab[i][j][1]=++id;
    for(i=1;i<=n;++i)for(j=1;j<=m;++j)scanf("%d",&a[i][j]);
    for(i=1;i<=n;++i)for(j=1;j<=m;++j)scanf("%d",&b[i][j]),res+=b[i][j];
      
    int S=0,T=id+1;
      
    Stg.reset();
    for(i=1;i<=n;++i)for(j=1;j<=m;++j){
        if((i+j)&1)Stg.make(S,lab[i][j][0],a[i][j]),Stg.make(lab[i][j][0],lab[i][j][1],b[i][j]);
        else Stg.make(lab[i][j][1],lab[i][j][0],b[i][j]),Stg.make(lab[i][j][0],T,a[i][j]);
        for(k=0;k<4;++k){
            int nowx=i+dx[k],nowy=j+dy[k];
            if(nowx>=1&&nowx<=n&&nowy>=1&&nowy<=m){
                if((i+j)&1)Stg.make(lab[i][j][0],lab[nowx][nowy][1],INF);
                else Stg.make(lab[nowx][nowy][1],lab[i][j][0],INF);
            }
        }
    }
      
    printf("%d",res-Stg.Maxflow(S,T));
      
    return 0;
}

Tags: 网络流
Posted in BZOJ | 0 Comments

BZOJ2673: [Wf2011]Chips Challenge 网络流+费用流

Codechef 14.12 RIN 网络流+最小割

Codechef 14.6 TWOCOMP 树链求交+网络流

BZOJ4177: Mike的农场最小割+网络流

BZOJ4205: 卡牌配对

BZOJ1443: [JSOI2009]游戏Game 二分图+博弈论+网络流

BZOJ1570:[JSOI2008]Blue Mary的旅行暴力+网络流

BZOJ1189:[HNOI2007]紧急疏散evacuate 二分+最大流

BZOJ1822:[JSOI2010]Frozen Nova 冷冻波二分+计算几何+网络流

BZOJ3774:最优选择网络流

search

lastest comments

friend links

visitor counter

search

tags

lastest comments

friend links

visitor counter