先强制流过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

相关文章