先强制流过l的流量。说一下生上下界的网络流。

算法

先上板

无源汇上下界可行流

图片 1

 

 先强制流过l的流量

起s到每个正权点连流量为l的流量

 从每个负权点向t连-l的流量

如若容量也0,则未连边

图片 2图片 3

发源汇上下界最要命流动

去丢下界

图片 4

先行要来可行流

双重要S到T的极致深流动

 

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<vector>
const int maxn=2050;
const int INF=1e9;
using namespace std;
int ans,n,m,xx,yy,cur[maxn],ad[maxn],s=0,t=201,dis[maxn];
struct edge{
    int from,to,flow,cup;
    edge(int from,int to,int flow,int cup):from(from),to(to),flow(flow),cup(cup){}
};
vector<edge>edges;
vector<int>g[maxn];
void add(int u,int v,int w){
   edges.push_back(edge(u,v,0,w));
   edges.push_back(edge(v,u,0,0));
   int t=edges.size();
   g[u].push_back(t-2);
   g[v].push_back(t-1);
} 
queue<int>que;
int bfs(int s,int t){
  memset(dis,0,sizeof(dis));
  dis[s]=1;
  que.push(s);
  while(!que.empty() ){
    int x=que.front();que.pop() ;
    for(int i=0;i<g[x].size();i++){
      edge t=edges[g[x][i]];
      if(!dis[t.to]&&t.cup>t.flow){
        dis[t.to]=dis[x]+1;
        que.push(t.to);
      }
    }
  }
  return dis[t];
}
int dfs(int x,int a){
    if(x==t||a==0) return a;
    int fl=0,c;
    for(int &i=cur[x];i<g[x].size();i++){
       edge &t=edges[g[x][i]];
       if(dis[t.to]==dis[x]+1&&(c=dfs(t.to,min(a,t.cup-t.flow)))){
            t.flow+=c;
            edges[g[x][i]^1].flow-=c;
         fl+=c;
            a-=c;
       } 
       if(a==0) break;
    }
    return fl;
}
void Dinic(int s,int t){
    while(bfs(s,t)){
     memset(cur,0,sizeof(cur));
     ans+=dfs(s,INF);
    }
}
int main()
{
   scanf("%d%d",&m,&n);
   for(;;){
     scanf("%d%d",&xx,&yy);
     if(xx==-1&&yy==-1) break;
     yy+=100;
     if(!ad[xx]) add(s,xx,1),ad[xx]=1;
     add(xx,yy,1);
     if(!ad[yy]) add(yy,t,1),ad[yy]=2;
   }
   Dinic(s,t);
     printf("%d\n",ans);
     for(int i=0;i<edges.size();i++){
     edge x=edges[i];
     if(x.from !=s&&x.to !=t&&x.cup&&x.flow==x.cup){
         printf("%d %d\n",x.from,x.to-100);
     }
   }
   return 0;
}

发出源汇上下界最小流

图片 5

 

Dinic模板
当前弧优化

一直行使

图片 6图片 7

poj1149

图片 8

自家之思绪

修建一个点S,到每个消费者,连INF的边,每个顾客

正解

1.用岔图,建n*m个点

2.直接从S向每个人连边,记录下每个猪圈打开的人数的次序顺寻,先来之人头往新兴的人头连边

 

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<vector>
const int maxn=100000+10; 
using namespace std;
int ans,flow,from,to,cup,n,m,s,t,a[maxn],p[maxn];
struct Edge{
    int from,to,cup,flow;
    Edge(int from,int to,int cup,int flow):from(from),to(to),cup(cup),flow(flow){}
};
vector<Edge>edges;
vector<int> G[maxn];
void add(int from,int to,int cup){
    edges.push_back(Edge(from,to,cup,0));
    edges.push_back(Edge(to,from,0,0));
    int m=edges.size() ;
    G[from].push_back(m-2);
    G[from].push_back(m-1); 
}
queue<int>que;
int bfs(int s,int t){
    //memset(p,-1,sizeof(p));
    memset(a,0,sizeof(a));
    while(!que.empty()) que.pop();
    que.push(s);
    a[s]=1e9;
    while(!que.empty() ){
        int x=que.front();que.pop();
        for(int i=0;i<G[x].size() ;i++){
            Edge tep=edges[G[x][i]];
            if(!a[tep.to ]&&tep.cup >tep.flow ){
            a[tep.to ]=min(a[x],tep.cup -tep.flow );
            p[tep.to ]=G[x][i];
                que.push(tep.to );
            }
        }
        if(a[t]) return 1;
    } 
    return 0;
}
int EK(int s,int t){
    ans=0;
    while(bfs(s,t)){
        for(int i=t;i!=s;i=edges[p[i]].from){
            edges[p[i]].flow+=a[t];
            edges[p[i]^1].flow-=a[t];
        }
        ans+=a[t];
    }
    return ans;
}
int main()
{
  scanf("%d%d%d%d",&n,&m,&s,&t);
  for(int i=1;i<=m;i++){
      scanf("%d%d%d",&from,&to,&cup);
      add(from,to,cup);
  } 
  printf("%d\n",EK(s,t));
   return 0;
}

BZOJ2406

图片 9

Solution

图片 10

图片 11

 图片 12

EK模板
(洛谷3376)

路覆盖模型

路线覆盖无交集

链覆盖好有混合

图片 13

起点,终点的度数都为1

最小化$n-\sum{d}$=最大化$\sum{d}$d为入度

拿原图的触发都进行拆点

 

路覆盖:

若i,j有边,则从i到j’连边

拥有边的边权均为1

 

链覆盖:

为此floyd求传递闭包

起一个接触向它能够抵的点都连边

 

因而最为小流解决

图片 14

 

链覆盖把每个点之上限改吗INF

 

 

图片 15图片 16

魔术球问题

图片 17

 

 

Solution

 

 图片 18

 

//Twenty
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<vector>
const int maxn=5005;
const int maxm=50005;
int a[maxn],vis[maxn],dis[maxn],ansf,ansv,u,v,c,w,n,m,s,t,pre[maxm];
using namespace std;
struct edge{
    int from,to,cup,flow,val;
    edge(int from,int to,int cup,int flow,int val):from(from),to(to),cup(cup),flow(flow),val(val){}
};
vector<int>g[maxn];
vector<edge>edges;
void add(int from,int to,int cup,int val){
    edges.push_back(edge(from,to,cup,0,val));
    edges.push_back(edge(to,from,0,0,-val));
    int x=edges.size();
    g[from].push_back(x-2);
    g[to].push_back(x-1); 
}
queue<int>que;
int spfa(int s,int t){
    memset(vis,0,sizeof(vis));
    memset(dis,127,sizeof(dis));
    memset(a,0,sizeof(a));
    que.push(s); vis[s]=1;dis[s]=0;a[s]=1e9;
    while(!que.empty() ){
        int x=que.front() ;que.pop() ;
        vis[x]=0;
        for(int i=0;i<g[x].size();i++){
            edge now=edges[g[x][i]];
            if(now.flow<now.cup&&dis[now.to ]>dis[now.from ]+now.val ){
                dis[now.to ]=dis[now.from ]+now.val ;
                a[now.to]=min(a[now.from],now.cup-now.flow); 
                pre[now.to]=g[x][i];
                if(!vis[now.to ]){
                    vis[now.to]=1;
                    que.push(now.to); 
                }
            }
        }
    }
    return a[t];     
}
void EK(int s,int t)
{
    while(spfa(s,t)){
        for(int i=t;i!=s;i=edges[pre[i]].from){
           edges[pre[i]].flow+=a[t];
           ansv+=a[t]*edges[pre[i]].val;
           edges[pre[i]^1].flow-=a[t];
        }
        ansf+=a[t];
    }
}
int main()
{
   scanf("%d%d%d%d",&n,&m,&s,&t);
   for(int i=1;i<=m;i++){
       scanf("%d%d%d%d",&u,&v,&c,&w);
       add(u,v,c,w);}
       EK(s,t);
       printf("%d %d",ansf,ansv);
   return 0;
}

CTSC2006

图片 19

 最小链覆盖

图片 20

 

 

 

顶小费用最老流动模板

Dilworth定理

图片 21

例如<=号

自反性:x<=x

反对称性:x<=y , y<=x
—>x==y

传递性:x<=y,y<=z—>x<=z

(<,>不饱偏序关系,不满足第二长达性质)

(DAG满足偏序关系,有于图不满足)

图片 22

反链:两沾里未克互相到达

 

定理:

图片 23

 

图片 24图片 25

TJOI2016XX数学

图片 26

 

暴力

拆成n*m个接触,每个点之权值下界为加的权值,上界为INF

优化

图片 27

对负有点选择同久点权和最好要命之

自从错误下至右上DP

 

//Twenty
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<vector>
const int maxn=299*299; 
const int INF=0x7fffffff;
int n,m,dis[maxn],s,t,cur[maxn],ans,du[maxn],x,y,d,u,dow[maxn];
using namespace std;
struct edge{
    int from,to,flow,cup;
    edge(int from,int to,int flow,int cup):from(from),to(to),flow(flow),cup(cup){}
};
vector<int>tmp;
vector<edge>edges;
vector<int>g[maxn];
void add(int u,int v,int w){
   edges.push_back(edge(u,v,0,w));
   edges.push_back(edge(v,u,0,0));
   int t=edges.size();
   g[u].push_back(t-2);
   g[v].push_back(t-1);
} 
queue<int>que;
int bfs(int s,int t){
  memset(dis,0,sizeof(dis));
  dis[s]=1;
  que.push(s);
  while(!que.empty() ){
    int x=que.front();que.pop() ;
    for(int i=0;i<g[x].size();i++){
      edge t=edges[g[x][i]];
      if(!dis[t.to]&&t.cup>t.flow){
        dis[t.to]=dis[x]+1;
        que.push(t.to);
      }
    }
  }
  return dis[t];
}
int dfs(int x,int a){
    if(x==t||a==0) return a;
    int fl=0,c;
    for(int &i=cur[x];i<g[x].size();i++){
       edge &t=edges[g[x][i]];
       if(dis[t.to]==dis[x]+1&&(c=dfs(t.to,min(a,t.cup-t.flow)))){
            t.flow+=c;
            edges[g[x][i]^1].flow-=c;
         fl+=c;
            a-=c;
       } 
       if(a==0) break;
    }
    return fl;
}
void Dinic(int s,int t){
    while(bfs(s,t)){
     memset(cur,0,sizeof(cur));
     ans+=dfs(s,INF);
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    s=0; t=n+1;
    for(int i=1;i<=m;i++){
        scanf("%d%d%d%d",&x,&y,&d,&u);
        add(x,y,u-d);
        tmp.push_back(edges.size()-2);
        dow[i]=d;
        du[y]+=d; du[x]-=d;
    }
    for(int i=1;i<=n;i++){
        if(du[i]>0) add(s,i,du[i]);
        else add(i,t,-du[i]);
    }
    Dinic(s,t);
    int hhh=g[0].size(),flag=1;
    for(int i=0;i<hhh;i++){
        edge ee=edges[g[0][i]];
        if(ee.flow<ee.cup ) {flag=0;break;}  
    }
    if(!flag) printf("NO\n");
    else{
        printf("YES\n");
        hhh=tmp.size(); int cnt=0;
        for(int i=0;i<hhh;i++){
        edge ee=edges[tmp[i]];
        printf("%d\n",ee.flow+dow[++cnt]);
        }
    }
    return 0;
}

时间分

图片 28

 

发上下界网络流模板 sgu 194

网络流24题星际XXXX

图片 29

图片 30

 

当极酷流为k的时节了

图片 31

 

 

 [HNOI2007]迫切疏散

图片 32

 

 图片 33

 

 

说一下生出上下界的网络流

回路限制

咱俩嫌下界麻烦,就使拿它们将掉(YK说),于是我们把各条弧的容量变成上界减下界

POI2010

图片 34

 

solution

 图片 35

深受各国条边定向&&判断是否衔接

列条边定向后会见使一个沾之入度加1,会如一个点的入度减1

 

先凭定向并保留一涂鸦反为机会

图片 36

可以将每次反向看成一长长的权值为2之增广路

图片 37

拿点权预先除为老二,验证图是否能够满流

图片 38

 

今后为了满足流量守稳定理,我个人的明白是,一久由u到v的弧,u点还可流进down那么基本上,就从源点到它们加相同长条容量为down的弧,v点还得流出down,就起其为汇点流加一漫长容量也-down的弧

 

下一场做法是对于每个点先把她流出的同注入的down统计一下,最后还加弧

BZOJ4215

图片 39

 

 

对一个网格进行是非染色,搞成二区划图

故流量为2的底限去限制度数也2

 

假使图满流,那么就是在有蛇都成环的方案

查找方案的时节看咋样边满流了

 

比方蛇不构成环,

对边界上的触及,设置其权值为[1,2],对于未边界上的点,其权值为[2,2]

告最好老流动

图片 40

 

 

极端深权闭合子图

图片 41图片 42

模型

图片 43

怀有与S相连的点视为不选择

有着和T相连的点视为挑选

有环的状好无缩点,(缩点也堪)

 

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<vector>
const int maxn=2050;
const int INF=1e9+7;
int f,s=0,t=201,ans,n,m,a,b,pre[maxn],fl[maxn],ad[maxn];
using namespace std;
struct edge{
    int from,to,cup,flow;
    edge(int from,int to,int cup,int flow):from(from),to(to),cup(cup),flow(flow){}
};
vector<edge>edges;
vector<int>g[202];
void add(int u,int v,int c){
    edges.push_back(edge(u,v,c,0));
    edges.push_back(edge(v,u,0,0));
    int t=edges.size();
    g[u].push_back(t-2);
    g[v].push_back(t-1);   
}
queue<int>que;
int bfs(int s,int e){
    while(!que.empty() ) que.pop() ;
    memset(fl,0,sizeof(fl));
    fl[s]=INF;
    que.push(s);
    while(!que.empty() ){
    int x=que.front();que.pop();
     for(int i=0;i<g[x].size();i++){
         int xxx=g[x][i];
        edge t=edges[g[x][i]];
        if(!fl[t.to]&&t.flow<t.cup ){
          fl[t.to]=min(fl[x],t.cup-t.flow);
          pre[t.to]=g[x][i];
          if(fl[e]) return fl[e];
          que.push(t.to);
        }        
      }
    }
    return 0;
}
void EK(){
    while(f=bfs(s,t)){
       ans+=f;
       for(int i=pre[t];;i=pre[edges[i].from]){
          edges[i].flow+=f;
          edges[i^1].flow-=f;
          int l=edges[2].from;
          if(edges[i].from==s) break;
       }
         /*for(int i=0;i<edges.size();i++){
   cout<<i<<":"<<" ";
   int o=edges[i].from; cout<<o<<" ";
   o=edges[i].to; cout<<o<<" ";
   o=edges[i].cup; cout<<o<" ";
   o=edges[i].flow; cout<<""<<o<<endl;
   }
    int aa;
    aa++;*/
    }
}
int main()
{
   scanf("%d%d",&m,&n);
   for(;;){
     scanf("%d%d",&a,&b);
     if(a==-1&&b==-1) break;
     if(!ad[a]) add(s,a,1),ad[a]=1; 
     add(a,b+100,1);
     if(!ad[b+100]) add(b+100,t,1),ad[b+100]=1;
   }/*
   for(int i=0;i<edges.size();i++){
   cout<<i<<":"<<" ";
   int o=edges[i].from; cout<<o<<" ";
   o=edges[i].to; cout<<o<<" ";
   o=edges[i].cup; cout<<o<" ";
   o=edges[i].flow; cout<<o<<endl;
   }*/
   EK();
   printf("%d\n",ans);
   for(int i=0;i<edges.size();i++){
     edge x=edges[i];
     if(x.from !=s&&x.to !=t&&x.cup&&x.flow==x.cup){
         printf("%d %d\n",x.from,x.to-100);
     }
   }
   return 0;
}

TJOI2015 线性代数

图片 44

Bij*Ai*Aj

Ci*Ai

 

 

 图片 45

 

模板
飞行员配对问题

COdefoeceXXX

图片 46

 

若果无考虑限法

图片 47

 

 

 限制条件

图片 48

打S向新加的点连Wi边

起新加之点向中间的老三只点并INF的尽头

 

 

CEOI?

 图片 49

图片 50

图片 51

转车为最小割

 

图片 52图片 53

BZOJ3774

图片 54

图片 55

图片 56

 

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn=420;
const int INF=0x7fffffff;
int inline read(){
    char ch=getchar(); int f=1,ret=0;
    while(ch>'9'||ch<'0') {if(ch=='-') f=-1; ch=getchar();}
    for(;ch>='0'&&ch<='9';ch=getchar()) ret=ret*10+ch-'0';
    return ret*f;
}
struct edge{
    int v,w,next;
}e[maxn];
int n,m,fir[maxn],dis[maxn];
int cnt=0;
int add(int u,int v,int w){
    e[cnt].v =v;e[cnt].w =w; e[cnt].next =fir[u]; fir[u]=cnt++;
    e[cnt].v =u;e[cnt].w =0; e[cnt].next =fir[v]; fir[v]=cnt++;
}
queue<int>q;
int bfs(){
    memset(dis,0,sizeof(dis));
    dis[1]=1; q.push(1);
    while(!q.empty()){
        int u=q.front() ;q.pop();
        for(int i=fir[u];i!=-1;i=e[i].next ){
            if(dis[e[i].v ]==0&&e[i].w ){
                dis[e[i].v]=dis[u]+1;
                q.push(e[i].v);
            }
        }
    }
    return dis[n];
}

int dfs(int s,int limit){
    if(s==n) return limit;
    int cost=0,tmp=0;
    for(int i=fir[s];i!=-1;i=e[i].next ){
        if(e[i].w &&dis[e[i].v]==dis[s]+1){
             tmp=dfs(e[i].v ,min(limit-cost,e[i].w));
             if(tmp!=0){
                 e[i].w -=tmp;e[i^1].w+=tmp;cost+=tmp;if(cost==limit) break;
          }
          else dis[e[i].v ]=-1;
        }
    }
    return cost;
}

int dinic(){
    int ans=0;
    while(bfs())
      ans+=dfs(1,INF);
    return ans;
}

int main()
{
    memset(fir,-1,sizeof(fir));
    m=read(); n=read();
    for(int i=1;i<=m;i++){
        int u,v,w;
        u=read();v=read();w=read();
        add(u,v,w);
    }
    printf("%d",dinic());    
    return 0;
}

平面图对偶图

图片 57

 

模板
草地排水

狼抓兔子

图片 58

 

NOI2010海拔

图片 59

 

 

图片 60

一定给S和T之前要最好小割

图片 61

 

 

 

相距限制

图片 62

 

一些题

HNOI拍照

图片 63

 

 图片 64

1.最小割 tyvj P1338 QQ农场

变形

图片 65

 

 图片 66

 

http://www.tyvj.cn/p/1338

CTSC2009

图片 67

冲曼哈顿相差的性

分别最优化横纵坐标

图片 68

图片 69

 

 

对每个点选择它便无可知选择它周围四个,可以肯定看出这是一个次之区划图,然后sum-最小割就是答案。

Hall定理

图片 70

图片 71图片 72

k-完备匹配

图片 73

先是,贪心的检索最可怜匹配然后删除是不言而喻不对的

图片 74

证明

顾念只要说明k-正则二分叉图,只需要证明k-1是否是

一经不设有

左侧的m*k条边设分给右侧<m条边,则生相同长边的度过数不为1

 

做法

图片 75

如若原图不设有k-正则二分割图则无解

 

//Twenty
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
const int maxn=299*299;
const int INF=0x7fffffff;
int ans,s=0,sum,t,n,a[maxn],dis[maxn],cur[maxn],x,y;
struct edge{
    int from,to,flow,cup;
    edge(int from,int to,int flow,int cup):from(from),to(to),flow(flow),cup(cup){}
};
vector<edge>edges;
vector<int>g[maxn];
void add(int u,int v,int w){
   edges.push_back(edge(u,v,0,w));
   edges.push_back(edge(v,u,0,0));
   int t=edges.size();
   g[u].push_back(t-2);
   g[v].push_back(t-1);
} 
queue<int>que;
int bfs(int s,int t){
  memset(dis,0,sizeof(dis));
  dis[s]=1;
  que.push(s);
  while(!que.empty() ){
    int x=que.front();que.pop() ;
    for(int i=0;i<g[x].size();i++){
      edge t=edges[g[x][i]];
      if(!dis[t.to]&&t.cup>t.flow){
        dis[t.to]=dis[x]+1;
        que.push(t.to);
      }
    }
  }
  return dis[t];
}
int dfs(int x,int a){
    if(x==t||a==0) return a;
    int fl=0,c;
    for(int &i=cur[x];i<g[x].size();i++){
       edge &t=edges[g[x][i]];
       if(dis[t.to]==dis[x]+1&&(c=dfs(t.to,min(a,t.cup-t.flow)))){
            t.flow+=c;
            edges[g[x][i]^1].flow-=c;
         fl+=c;
            a-=c;
       } 
       if(a==0) break;
    }
    return fl;
}
void Dinic(int s,int t){
    while(bfs(s,t)){
     memset(cur,0,sizeof(cur));
     ans+=dfs(s,INF);
    }
}
int check(int i,int j){
    y=(i-1)*n+j;
    return (i>=1&&i<=n&&j>=1&&j<=n);
}
int main()
{
    scanf("%d",&n);
    t=n*n+1;
    for(int i=1;i<=n;i++){
        int flag=i;
    for(int j=1;j<=n;j++){
        x=(i-1)*n+j;
        scanf("%d",&a[x]);
        sum+=a[x];
        if(flag%2){
        if(check(i+1,j)) 
         add(x,y,INF); 
        if(check(i-1,j)) 
         add(x,y,INF);
        if(check(i,j+1)) 
         add(x,y,INF);
        if(check(i,j-1)) 
         add(x,y,INF);
         add(s,x,a[x]);
        }
        else add(x,t,a[x]);
        ++flag;
    }
    }
    Dinic(s,t);
    printf("%d\n",sum-ans);
    return 0;
}

POI2009 Lyz

图片 76

图片 77

tyvj P1338
QQ农场.cpp

tag

 

 

 

【CERC2016】Bipartite Blanket

2.BZOJ 1834网络扩容

 图片 78

先行要来尽可怜流动,然后每条弧上再加同长条容量为INF费用吗扩容费用的弧,从源点流入需要扩容的轻重缓急,跑同尽费用流。

solution

图片 79

证明

图片 80

 图片 81

图片 82

时复杂度

$2^n*n+2^n*log n$

 

图片 83图片 84

//Twenty
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
const int INF=0x7fffffff;
const int maxn=(5000+29)*2; 
int nowfl,aa,b,c,d,n,m,k,dis[maxn],cur[maxn],s,t,ans1,ans2,vis[maxn],woc;
int ps[maxn][3],a[maxn],pre[maxn];
struct edge{
    int from,to,flow,cup,cost;
    edge(int from,int to,int flow,int cup,int cost):from(from),to(to),flow(flow),cup(cup),cost(cost){}
};
vector<edge>edges;
vector<int>g[maxn];
void add(int u,int v,int w,int cost){
   edges.push_back(edge(u,v,0,w,cost));
   edges.push_back(edge(v,u,0,0,-cost));
   int t=edges.size();
   g[u].push_back(t-2);
   g[v].push_back(t-1);
} 
queue<int>que;
int bfs(int s,int t){
  memset(dis,0,sizeof(dis));
  dis[s]=1;
  que.push(s);
  while(!que.empty() ){
    int x=que.front();que.pop() ;
    for(int i=0;i<g[x].size();i++){
      edge t=edges[g[x][i]];
      if(!dis[t.to]&&t.cup>t.flow){
        dis[t.to]=dis[x]+1;
        que.push(t.to);
      }
    }
  }
  return dis[t];
}
int dfs(int x,int a){
    if(x==t||a==0) return a;
    int fl=0,c;
    for(int &i=cur[x];i<g[x].size();i++){
       edge &t=edges[g[x][i]];
       if(dis[t.to]==dis[x]+1&&(c=dfs(t.to,min(a,t.cup-t.flow)))){
            t.flow+=c;
            edges[g[x][i]^1].flow-=c;
         fl+=c;
            a-=c;
       } 
       if(a==0) break;
    }
    return fl;
}
void Dinic(int s,int t){
    while(bfs(s,t)){
     memset(cur,0,sizeof(cur));
     ans1+=dfs(s,INF);
    }
}
int spfa(int s,int t){
    memset(vis,0,sizeof(vis));
    memset(dis,127,sizeof(dis));
    memset(a,0,sizeof(a));
    que.push(s); vis[s]=1; dis[s]=0; a[s]=woc;
    while(!que.empty() ){
        int x=que.front() ;que.pop() ;
        vis[x]=0;
        for(int i=0;i<g[x].size();i++){
            edge now=edges[g[x][i]];
            if(now.flow<now.cup&&dis[now.to ]>dis[now.from ]+now.cost ){
                dis[now.to ]=dis[now.from ]+now.cost ;
                a[now.to]=min(a[now.from],now.cup-now.flow); 
                pre[now.to]=g[x][i];
                if(!vis[now.to ]){
                    vis[now.to]=1;
                    que.push(now.to); 
                }
            }
        }
    }
    return a[t];     
}
void EK(int s,int t)
{
    woc=k;
    while(woc&&spfa(s,t)){
        for(int i=t;i!=s;i=edges[pre[i]].from){
           edges[pre[i]].flow+=a[t];
           edges[pre[i]^1].flow-=a[t];
        }
        woc-=a[t];
        ans2+=(dis[t]*a[t]);
    }
}
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    s=1,t=n;
    for(int i=1;i<=m;i++){
    scanf("%d%d%d%d",&aa,&b,&c,&d);
    ps[i][0]=aa; ps[i][1]=b; ps[i][2]=d;
    add(aa,b,c,0);
    }
    Dinic(s,t);
    printf("%d ",ans1);
    for(int i=1;i<=m;i++)
    add(ps[i][0],ps[i][1],INF,ps[i][2]);
    EK(s,t);
    printf("%d\n",ans2);
    return 0;
}

BZOJ 1834
网络扩容

 

3.codevs 1227 方格取数

太可怜费流

要求获得m次,拆点,每个点望虚点之间并两长边,一漫长控制联通,容量为INF,费用为0,一漫漫控制支出,容量也1,。然后每个点向能抵的点连容量为m的限,源点向起点连容量为m的度。

图片 85图片 86

//Twenty
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<vector>
const int INF=0x7fffffff;
const int maxn=105*105;
using namespace std;
int b[maxn],n,m,xx,yy,zz,cur[maxn],s,t,dis[maxn],vis[maxn],a[maxn],pre[maxn];
int vv,ansv,ansf;
using namespace std;
struct edge{
    int from,to,cup,flow,val;
    edge(int from,int to,int cup,int flow,int val):from(from),to(to),cup(cup),flow(flow),val(val){}
};
vector<int>g[maxn];
vector<edge>edges;
void add(int from,int to,int cup,int val){
    edges.push_back(edge(from,to,cup,0,val));
    edges.push_back(edge(to,from,0,0,-val));
    int x=edges.size();
    g[from].push_back(x-2);
    g[to].push_back(x-1); 
}
queue<int>que;
int spfa(int s,int t){
    memset(vis,0,sizeof(vis));
    memset(dis,127,sizeof(dis));
    memset(a,0,sizeof(a));
    que.push(s); vis[s]=1;dis[s]=0;a[s]=1e9;
    while(!que.empty() ){
        int x=que.front() ;que.pop() ;
        vis[x]=0;
        for(int i=0;i<g[x].size();i++){
            edge now=edges[g[x][i]];
            if(now.flow<now.cup&&dis[now.to ]>dis[now.from ]+now.val ){
                dis[now.to ]=dis[now.from ]+now.val ;
                a[now.to]=min(a[now.from],now.cup-now.flow); 
                pre[now.to]=g[x][i];
                if(!vis[now.to ]){
                    vis[now.to]=1;
                    que.push(now.to); 
                }
            }
        }
    }
    return a[t];     
}
void EK(int s,int t)
{
    while(spfa(s,t)){
        for(int i=t;i!=s;i=edges[pre[i]].from){
           edge &ee=edges[pre[i]];
           ee.flow+=a[t];
           edges[pre[i]^1].flow-=a[t];
        }
        ansv+=(dis[t]*a[t]);
    }
}
int check(int i,int j){
    vv=(i-1)*n+j;
    return (i>=1&&i<=n&&j>=1&&j<=n);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++){
        scanf("%d",&b[(i-1)*n+j]);
        b[(i-1)*n+j]*=-1;
    }
    s=1,t=n*n+n*n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            {
                int uu=(i-1)*n+j;
                if(uu==1) add(uu,uu+n*n,m,0);
                else {add(uu,uu+n*n,INF,0);
                add(uu,uu+n*n,1,b[uu]);}
                if(check(i+1,j)) 
                    add(uu+n*n,vv,m,0);
                if(check(i,j+1)) 
                    add(uu+n*n,vv,m,0);
            }
    EK(s,t);
    if(m==0) printf("0\n");
    else
    printf("%d\n",(ansv+b[1])*-1);
    return 0;
}

codevs 1227
方格取数

 

 

 

4.codevs 1022 覆盖

http://codevs.cn/problem/1022/

其次区划图匹配水题 显然图是第二分开图
每个点判断一下可是不行掩盖(是未是水塘)。

图片 87图片 88

//Twenty
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
const int maxn=105*105;
const int INF=0x7fffffff;
int s=0,t,n,m,k,a[maxn],ans,dis[maxn],cur[maxn],x,y,u,v,flag;
struct edge{
    int from,to,flow,cup;
    edge(int from,int to,int flow,int cup):from(from),to(to),flow(flow),cup(cup){}
};
vector<edge>edges;
vector<int>g[maxn];
void add(int u,int v,int w){
   edges.push_back(edge(u,v,0,w));
   edges.push_back(edge(v,u,0,0));
   int t=edges.size();
   g[u].push_back(t-2);
   g[v].push_back(t-1);
} 
queue<int>que;
int bfs(int s,int t){
  memset(dis,0,sizeof(dis));
  dis[s]=1;
  que.push(s);
  while(!que.empty() ){
    int x=que.front();que.pop() ;
    for(int i=0;i<g[x].size();i++){
      edge t=edges[g[x][i]];
      if(!dis[t.to]&&t.cup>t.flow){
        dis[t.to]=dis[x]+1;
        que.push(t.to);
      }
    }
  }
  return dis[t];
}
int dfs(int x,int a){
    if(x==t||a==0) return a;
    int fl=0,c;
    for(int &i=cur[x];i<g[x].size();i++){
       edge &t=edges[g[x][i]];
       if(dis[t.to]==dis[x]+1&&(c=dfs(t.to,min(a,t.cup-t.flow)))){
            t.flow+=c;
            edges[g[x][i]^1].flow-=c;
         fl+=c;
            a-=c;
       } 
       if(a==0) break;
    }
    return fl;
}
void Dinic(int s,int t){
    while(bfs(s,t)){
     memset(cur,0,sizeof(cur));
     ans+=dfs(s,INF);
    }
}
int check(int i,int j){
    v=(i-1)*m+j;
    return (!a[v]&&i>=1&&i<=n&&j>=1&&j<=n);
}
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    t=n*m+1;
    for(int i=1;i<=k;i++){
        scanf("%d%d",&x,&y);
        a[(x-1)*m+y]=1;
    } 
    for(int i=1;i<=n;i++)
     {flag=i;
     for(int j=1;j<=m;j++){
        u=(i-1)*m+j;
        if(!a[u]&&flag%2){
          if(check(i+1,j)) 
             add(u,v,INF); 
          if(check(i-1,j)) 
             add(u,v,INF);
          if(check(i,j+1)) 
             add(u,v,INF);
          if(check(i,j-1)) 
             add(u,v,INF);
          add(s,u,1);
        }
        else if(!a[u]) 
            add(u,t,1);
        ++flag;
     }
     }
    Dinic(s,t);
    printf("%d\n",ans);
    return 0;
}

codevs 1022
覆盖

 

5.太小路径覆盖问题

优先拿每个点单独为同长达路子,将点滴长长的途径连起来便足以减一长条路径,考虑以如何点并起来,把所有点增加一个,分为两份,就改为了亚瓜分图匹配问题,就可以为此网络流搞了。

图片 89图片 90

//Twenty
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
const int maxn=30000+5;
const int INF=0x7fffffff;
int ans,n,m,x,y,cur[maxn],s,t,dis[maxn],ts,in[maxn],p[maxn];
int a[maxn],nx[maxn],qq[maxn];
struct edge{
    int from,to,flow,cup;
    edge(int from,int to,int flow,int cup):from(from),to(to),flow(flow),cup(cup){}
};
vector<edge>edges;
vector<int>g[maxn];
void add(int u,int v,int w){
   edges.push_back(edge(u,v,0,w));
   edges.push_back(edge(v,u,0,0));
   int t=edges.size();
   g[u].push_back(t-2);
   g[v].push_back(t-1);
   edge ee=edges[t-1];
   int xxxx=1;
   xxxx++;
} 
queue<int>que;
int bfs(int s,int t){
    memset(a,0,sizeof(a));
    while(!que.empty()) que.pop();
    que.push(s);
    a[s]=1e9;
    while(!que.empty() ){
        int x=que.front();que.pop();
        for(int i=0;i<g[x].size() ;i++){
            edge tep=edges[g[x][i]];
            if(!a[tep.to ]&&tep.cup >tep.flow ){
            a[tep.to ]=min(a[x],tep.cup -tep.flow );
            p[tep.to ]=g[x][i];
                que.push(tep.to );
            }
        }
        if(a[t]) return 1;
    } 
    return 0;
}
int EK(int s,int t){
    ans=0;
    while(bfs(s,t)){
        for(int i=t;i!=s;i=edges[p[i]].from){
            edges[p[i]].flow+=a[t];
            edges[p[i]^1].flow-=a[t];
        }
        ans+=a[t];
    }
    return ans;
}
void printedge(){
    for(int i=0;i<edges.size();i++){
        edge ee=edges[i];
        printf("【%d】\n",i+1);
        printf("from: %d\n",ee.from);
        printf("to: %d\n",ee.to);
        printf("flow: %d\n",ee.flow);
        printf("cup: %d\n",ee.cup);
    }
} 
void print(){
    int hhh=edges.size();
    for(int i=0;i<hhh;i++){
        edge ee=edges[i];
        if(ee.from>=1&&ee.from<=n&&ee.to>=n+1&&ee.to<=n+n&&ee.flow==1){
            nx[ee.from]=ee.to-n;
            in[ee.to-n]++;
        }
    }
    for(int i=1;i<=n;i++)
        if(!in[i]){
            int tmp=i;
            printf("%d ",tmp);
            while(nx[tmp]){
                 printf("%d ",nx[tmp]);
                 tmp=nx[tmp];
            }
            printf("\n");
        }
}
int main()
{
    scanf("%d%d",&n,&m);
    s=0;t=n*n+1;
    for(int i=1;i<=n;i++)
    {add(s,i,1);
    add(i+n,t,1);}
    for(int i=1;i<=m;i++){
    scanf("%d%d",&x,&y);
    add(x,y+n,1); 
    }
    EK(s,t);
    ts=n-ans;
    print();
    printf("%d\n",ts);
    return 0;
}

不过小路径覆盖问题

 

6.BZOJ 1305 Dance跳舞

http://www.lydsy.com/JudgeOnline/problem.php?id=1305

率先男生女生可以用作一个亚私分图,每个人发爱的总人口同免喜欢的人数,显然可以拆点,我们将好的叫真的接触,不欣赏的叫假的触及。

每个人无比老可经不喜欢的食指的个数m,从每个真男孩往假男孩连容量为m的点,从每个假女孩于真正女孩并容量为m的度。相互欣赏的真男孩连于真正女孩容量也1底界限。

然后二分叉答案,二细分一个极其特别可以超越的场数k,从源点向每个真男孩连容量为k的限,每个真女孩为汇点连容量为k的度,跑同一遍最老流动,检查各级条并于汇点的尽头是否满流。

图片 91图片 92

//Twenty
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<vector>
const int maxn=205*205;
const int INF=0x7fffffff;
int n,k,a[55][55],l=0,r=50;
char ch[maxn];
using namespace std;
int s,t,ans,cur[maxn],dis[maxn],cs;
struct edge{
    int from,to,flow,cup;
    edge(int from,int to,int flow,int cup):from(from),to(to),flow(flow),cup(cup){}
};
vector<edge>edges;
vector<int>g[maxn];
void add(int u,int v,int w){
   edges.push_back(edge(u,v,0,w));
   edges.push_back(edge(v,u,0,0));
   int t=edges.size();
   g[u].push_back(t-2);
   g[v].push_back(t-1);
} 
queue<int>que;
int bfs(int s,int t){
  memset(dis,0,sizeof(dis));
  dis[s]=1;
  que.push(s);
  while(!que.empty() ){
    int x=que.front();que.pop() ;
    for(int i=0;i<g[x].size();i++){
      edge t=edges[g[x][i]];
      if(!dis[t.to]&&t.cup>t.flow){
        dis[t.to]=dis[x]+1;
        que.push(t.to);
      }
    }
  }
  return dis[t];
}
int dfs(int x,int a){
    if(x==t||a==0) return a;
    int fl=0,c;
    for(int &i=cur[x];i<g[x].size();i++){
       edge &t=edges[g[x][i]];
       if(dis[t.to]==dis[x]+1&&(c=dfs(t.to,min(a,t.cup-t.flow)))){
            t.flow+=c;
            edges[g[x][i]^1].flow-=c;
         fl+=c;
            a-=c;
       } 
       if(a==0) break;
    }
    return fl;
}
void Dinic(int s,int t){
    while(bfs(s,t)){
     memset(cur,0,sizeof(cur));
     ans+=dfs(s,INF);
    }
}
int check(int x){
    int hhh=edges.size() ;
    for(int i=0;i<hhh;i++){
        edge &ee=edges[i];
        ee.flow=0;
        if(ee.from==s) {
            if(ee.to<=n)
                ee.cup=x;
            else ee.cup=0;
        }
        if(ee.to==t) {
            if(ee.from>=2*n+1&&ee.from<=3*n)
                {ee.cup=x;
                 int debugg=1;
                 debugg++;
                 }
            else ee.cup=0;
        }
    }
    ans=0;
    Dinic(s,t);
    return (ans>=n*x);
}
int main()
{
    scanf("%d%d",&n,&k);
    t=n*4+1;
    for(int i=1;i<=n;i++){
        scanf("%s",ch);
        for(int j=0;j<n;j++)
            if(ch[j]=='Y') a[i][j+1]=1; 
    }
    for(int i=1;i<=n;i++){
        add(s,i,0);   
        add(i,n+i,k); //1~n 真男孩 n~2n 假男孩 
        add(2*n+i,t,0); 
        add(3*n+i,2*n+i,k); //2n~3n 真女孩 3n~4n 假女孩 
        for(int j=1;j<=n;j++){
            if(a[i][j]) add(i,2*n+j,1);   
            else add(n+i,3*n+j,1);
        }
    }
    //if(!check(1)) printf("0\n");
    //else{
        while(l<=r){
            int mid=(l+r)>>1;
            if(check(mid)) cs=mid,l=mid+1;
            else r=mid-1;
        //}
        }
    printf("%d\n",cs);    
    return 0;
}

BZOJ 1305
Dance跳舞

 

7.BZOJ 2127 happiness

http://www.lydsy.com/JudgeOnline/problem.php?id=2127

大经典的文理分科问题,一开始瘦学长直接抬来了一个图,非常懵逼,后来提问了YYH大神才知晓了

率先这是一个次分割图,然后随即是一个极端小割,因为好好地觉察要同选文,要么同选理,要么一和一料理,所以A选文
A选理 B选文 B选理 同选文
同选理6长长的边中我们只要割去部分限,并且使割去的尽头的与无限小,就是一个极致小割模型了。

那么什么样建图呢,

YYH 说
我们决不错过考虑它剩下的凡什么,只考虑割去之是啊。(也因而中间要建成双向边)

就发了如下的觊觎,可以团结沿着所以中之割割一总体,

图片 93(注:两只和两只理其实是一个沾
源点和汇点)

 

实际操作的下,我们把边的容量还乘以2,最后重复除为老二得有答案。

 

图片 94图片 95

//Twenty
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
const int maxn=105*105;
const int INF=0x7fffffff;
int n,m,x,s,t,cur[maxn],uu,vv;
int jz[7][maxn],ans,dis[maxn],sum;
struct edge{
    int from,to,flow,cup;
    edge(int from,int to,int flow,int cup):from(from),to(to),flow(flow),cup(cup){}
};
vector<edge>edges;
vector<int>g[maxn];
void add(int u,int v,int w){
   edges.push_back(edge(u,v,0,w));
   edges.push_back(edge(v,u,0,0));
   int t=edges.size();
   g[u].push_back(t-2);
   g[v].push_back(t-1);
} 
queue<int>que;
int bfs(int s,int t){
  memset(dis,0,sizeof(dis));
  dis[s]=1;
  que.push(s);
  while(!que.empty() ){
    int x=que.front();que.pop() ;
    for(int i=0;i<g[x].size();i++){
      edge t=edges[g[x][i]];
      if(!dis[t.to]&&t.cup>t.flow){
        dis[t.to]=dis[x]+1;
        que.push(t.to);
      }
    }
  }
  return dis[t];
}
int dfs(int x,int a){
    if(x==t||a==0) return a;
    int fl=0,c;
    for(int &i=cur[x];i<g[x].size();i++){
       edge &t=edges[g[x][i]];
       if(dis[t.to]==dis[x]+1&&(c=dfs(t.to,min(a,t.cup-t.flow)))){
            t.flow+=c;
            edges[g[x][i]^1].flow-=c;
         fl+=c;
            a-=c;
       } 
       if(a==0) break;
    }
    return fl;
}
void Dinic(int s,int t){
    while(bfs(s,t)){
     memset(cur,0,sizeof(cur));
     ans+=dfs(s,INF);
    }
}
int check(int i,int j){
    vv=(i-1)*n+j;
    return (i>=1&&i<=n&&j>=1&&j<=m);
}
int main()
{
    scanf("%d%d",&n,&m);
    s=0;t=n*m+1;
    for(int tt=1;tt<=6;tt++){
    for(int i=1;i<=n;i++){
    if((tt==3||tt==4)&&i==n) continue;
    for(int j=1;j<=m;j++){
        if((tt==5||tt==6)&&j==m) continue;
        int u=(i-1)*n+j;
        scanf("%d",&jz[tt][u]);
        sum+=jz[tt][u];
    }
    }
    }
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++){
        uu=(i-1)*n+j;
        int tw=0,tl=0;
        if(check(i+1,j)){
            int tmp=jz[3][uu]+jz[4][uu];
            add(uu,vv,tmp); 
            add(vv,uu,tmp); 
            tw+=jz[3][uu]; tl+=jz[4][uu];
        }
        if(check(i-1,j)){
            tw+=jz[3][vv]; tl+=jz[4][vv];
        }
        if(check(i,j+1)){
            int tmp=(jz[5][uu]+jz[6][uu]);
            add(uu,vv,tmp);
            add(vv,uu,tmp);
            tw+=jz[5][uu]; tl+=jz[6][uu];
        }
        if(check(i,j-1)){
            tw+=jz[5][vv]; tl+=jz[6][vv];
        }
        //if(i*j%2){
            //add(s,uu,jz[2][uu]+tl);
            //add(uu,t,jz[1][uu]+tw);
        //}
        //else{
            add(s,uu,jz[1][uu]*2+tw); 
            add(uu,t,jz[2][uu]*2+tl);
        //}
           //用Double会出问题,所以都乘2 
           //建图关键不在如何流而在割去的是什么 
           //sum为五部分之和,割去相应的边方案要合法 
    }
    Dinic(s,t);
    printf("%d",sum-ans/2);
    return 0;
}

BZOJ 2127 happiness

相关文章