葡京娱乐注册Day五网络流

算法

先上板

无源汇上下界可行流

葡京娱乐注册 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

自作者的思绪

建3个点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

起源,终点的度数都为一

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

把原图的点都开始展览拆点

 

途径覆盖:

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

装有边的边权均为一

 

链覆盖:

用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 1玖四

网络流24题星际XXXX

葡京娱乐注册 29

葡京娱乐注册 30

 

当最大流为k的时候甘休

葡京娱乐注册 31

 

 

 [HNOI2007]加急疏散

葡京娱乐注册 32

 

 葡京娱乐注册 33

 

 

说一下有上下界的网络流

回路限制

咱俩嫌下界麻烦,就要把它弄掉(YK说),于是大家把每条弧的体量变成上界减下界

POI2010

葡京娱乐注册 34

 

solution

 葡京娱乐注册 35

给每条边定向&&判断是或不是衔接

每条边定向后会使1个点的入度加一,会使四个点的入度减一

 

先随便定向并保留一遍反向机会

葡京娱乐注册 36

能够把每一遍反向看成一条权值为2的增广路

葡京娱乐注册 37

把点权预先除以贰,验证图是或不是能满流

葡京娱乐注册 38

 

今后为了满意流量守恒定理,小编个人的精晓是,一条从u到v的弧,u点还足以流进down那么多,就从源点到它加一条体积为down的弧,v点仍是能够流出down,就从它向汇点流加一条体积为-down的弧

 

接下来做法是对于各个点先把它流出的和注入的down总结一下,最终再加弧

BZOJ4215

葡京娱乐注册 39

 

 

对一个网格举办是非染色,搞成二分图

用流量为二的边去限制度数为二

 

若果图满流,那么就存在全部蛇都整合环的方案

找方案的时候看怎么边满流了

 

设若蛇不结合环,

对于边界上的点,设置其权值为[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;
}

TJOI20壹5 线性代数

葡京娱乐注册 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条边,则有一条边的度数不为一

 

做法

葡京娱乐注册 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

二.BZOJ 183四网络扩大体量

 葡京娱乐注册 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网络扩大体量

 

三.codevs 12二柒 方格取数

最大支出流

务求取m次,拆点,每一个点向虚点之间连两条边,一条控制联通,体积为INF,开支为0,一条控制支出,容积为一,。然后每一个点向能到达的点连体量为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 122七方格取数

 

 

葡京娱乐注册, 

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的边。相互欣赏的真男孩连向真女孩体量为一的边。

然后二分答案,二分三个最大能够跳的场数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

很经典的文科理科分科难题,一开头瘦学长直接抬出了3个图,10分懵逼,后来问了YYH大神才懂了

率先那是3个二分图,然后这是1个微细割,因为能够简单地意识照旧同选文,要么同选理,要么一文1理,所以A选文
A选理 B选文 B选理 同选文
同选理陆条边中大家要割去部分边,并且使得割去的边之和微小,正是三个非常小割模型了。

那么哪些建图呢,

YYH 说
我们绝不去考虑它剩下的是什么,只考虑割去的是怎么样。(也就其中间要建成双向边)

就有了如下的图,能够自个儿沿着所以可行的割割二回,

葡京娱乐注册 93(注:多少个文三个理其实是二个点
起点和汇点)

 

实操的时候,大家把边的体量都乘以二,最终再除以二得出答案。

 

葡京娱乐注册 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