1.最大流入门题
m条边,np个源点，nc个汇点 #include <stdio.h>
#include <iostream>
using namespace std;
const int oo=1e9;
const int mm=111111;
const int mn=999;
int node ,scr,dest,edge;
int ver[mm],flow[mm],next[mm];
int head[mn],work[mn],dis[mn],q[mn];
void prepare(int _node,int _scr,int _dest)
{
node=_node,scr=_scr,dest=_dest;
for(int i=0; i<node; ++i)
head[i]=-1;
edge=0;
}
void addedge(int u,int v,int c)
{
ver[edge]=v,flow[edge]=c,next[edge]=head[u],head[u]=edge++;
ver[edge]=u,flow[edge]=0,next[edge]=head[v],head[v]=edge++;
}
bool Dinic_bfs()
{
int i,u,v,l,r=0;
for(i=0; i<node; i++)
dis[i]=-1;
dis[q[r++]=scr]=0;
for(l=0; l<r; ++l)
{
for(i=head[u=q[l]]; i>=0; i=next[i])
{
if(flow[i]&&dis[v=ver[i]]<0)
{
dis[q[r++]=v]=dis[u]+1;
if(v==dest)
return 1;
}
}
}
return 0;
}
int Dinic_dfs(int u,int exp)
{
if(u==dest)
return exp;
for(int &i=work[u],v,tmp; i>=0; i=next[i])
if(flow[i]&&dis[v=ver[i]]==dis[u]+1&&(tmp=Dinic_dfs(v,min(exp,flow[i])))>0)
{
flow[i]-=tmp;
flow[i^1]+=tmp;
return tmp;
}
return 0;
}
int Dinic_flow()
{
int i,ret=0,delta;
while(Dinic_bfs())
{
for(i=0; i<node; i++)
work[i]=head[i];
while(delta=Dinic_dfs(scr,oo))
ret+=delta;
}
return ret;
}
int main()
{
//freopen("cin.txt","r",stdin);
int n,np,nc,m,z,u,v;
char str;
while(~scanf("%d%d%d%d",&n,&np,&nc,&m))
{
// printf("%d %d %d %d\n",n,np,nc,m);
prepare(n+3,0,n+1);
for(int i=0;i<m;i++)
{
while(getchar()!='(');
scanf("%d,%d)%d",&u,&v,&z);
// printf("%d %d %d\n",u,v,z);
addedge(u+1,v+1,z);
}
for(int i=0;i<np;i++)
{
while(getchar()!='(');
scanf("%d)%d",&u,&z);
//printf("%d %d\n",u,z);
addedge(0,u+1,z);
}
for(int i=0;i<nc;i++)
{
while(getchar()!='(');
scanf("%d)%d",&u,&z);
// printf("%d %d\n",u,z);
addedge(u+1,n+1,z);
}
printf("%d\n",Dinic_flow());
}
return 0;
} 2.最小割
在一个无向图中小偷要偷东西..小偷从s点出发..要偷的东在点e...警察可以用一些警力封锁一些点让小偷无论如何都不能到达e
把一个点拆成两个 原来点上的权变成拆成两点间流的大小，求最大流即最小割
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=100000;
const int maxe=1000000;
int sum,s,e,head[maxn],level[maxn],que[maxn],n,m;
struct node{
int w,to,next;
}edge[maxe];
inline void add(int u,int v,int c)
{
edge[sum].to=v;
edge[sum].w=c;
edge[sum].next=head[u];
head[u]=sum++;
edge[sum].to=u;
edge[sum].w=0;
edge[sum].next=head[v];
head[v]=sum++;
}
inline bool bfs()
{
memset(level,0,sizeof(level));
int p=0;
que[p++]=s;
level[s]=1;
for(int i=0;i<p;i++)
{
int temp=que[i];
for(int k=head[temp];k>-1;k=edge[k].next)
if(edge[k].w && (!level[edge[k].to])){
que[p++]=edge[k].to;
level[edge[k].to]=level[temp]+1;
}
}
return level[e];
}
int dfs(int now,int maxf)
{
if(now==e)return maxf;
int ret=0;
for(int i=head[now];i>-1 && ret<maxf; i=edge[i].next)
if(edge[i].w && (level[edge[i].to]==level[now]+1))
{
int temp=dfs(edge[i].to,min(maxf-ret,edge[i].w));
edge[i].w-=temp;
edge[i^1].w+=temp;
ret+=temp;
}
if(ret==0)level[now]=0;
return ret;
}
inline int dinic()
{
int ans=0;
while(bfs())ans+=dfs(s,inf);
return ans;
}
int main()
{
//freopen("cin.txt","r",stdin);
int k,w,a,b;
while(~scanf("%d",&k))
{
sum=0;
memset(head,-1,sizeof(head));
scanf("%d%d%d%d",&n,&m,&s,&e);
s=s<<1|1;
e=e<<1;
for(int i=1;i<=n;i++)
{
scanf("%d",&w);
add(i<<1,i<<1|1,w);
add(i<<1|1,i<<1,w);
}
for(int i=0;i<m;i++)
{
scanf("%d%d",&a,&b);
add(a<<1|1,b<<1,inf);
add(b<<1|1,a<<1,inf);
}
if(dinic()<=k && s!=e+1 && s!=e-1 && s!=e) puts("YES");
else puts("NO");
}
return 0;
} 3.最大权闭合图模板题
最大权闭合图 hdu 3879 Base Station 有模板！
和网络流与线性规划第二题太空飞行一样，最大权闭合图虽然是有正的点，有负的点，但是也是要把中间的边保留，负值取绝对值，之前所有正值得点和减去最大流即为所求 #include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=100000;
const int maxe=1000000;
int sum,s,e,head[maxn],level[maxn],que[maxn];
struct node{
int w,to,next;
}edge[maxe];
void add(int u,int v,int c)
{
edge[sum].to=v;
edge[sum].w=c;
edge[sum].next=head[u];
head[u]=sum++;
edge[sum].to=u;
edge[sum].w=0;
edge[sum].next=head[v];
head[v]=sum++;
}
bool bfs()
{
memset(level,0,sizeof(level));
int p=0;
que[p++]=s;
level[s]=1;
for(int i=0;i<p;i++)
{
int temp=que[i];
for(int k=head[temp];k>-1;k=edge[k].next)
if(edge[k].w && (!level[edge[k].to])){
que[p++]=edge[k].to;
level[edge[k].to]=level[temp]+1;
}
}
return level[e];
}
int dfs(int now,int maxf)
{
if(now==e)return maxf;
int ret=0;
for(int i=head[now];i>-1 && ret<maxf; i=edge[i].next)
if(edge[i].w && (level[edge[i].to]==level[now]+1))
{
int temp=dfs(edge[i].to,min(maxf-ret,edge[i].w));
edge[i].w-=temp;
edge[i^1].w+=temp;
ret+=temp;
}
if(ret==0)level[now]=0;
return ret;
}
int dinic()
{
int ans=0;
while(bfs())ans+=dfs(s,inf);
return ans;
}
int main()
{
//freopen("cin.txt","r",stdin);
int n,m,x;
while(~scanf("%d%d",&n,&m)){
sum=0;
memset(head,-1,sizeof(head));
s=0,e=n+m+1;
for(int i=1;i<=n;i++){
scanf("%d",&x);
add(i+m,e,x);
}
int count=0;
for(int i=1;i<=m;i++){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
add(i,a+m,inf);
add(i,b+m,inf);
add(s,i,c);
count+=c;
}
//cout<<dinic()<<endl;
printf("%d\n",count-dinic());
}
return 0;
} 4.最小费用流
1、从S向每个Xi连一条容量为ri，费用为0的有向边。
2、从每个Yi向T连一条容量为ri，费用为0的有向边。
3、从S向每个Yi连一条容量为无穷大，费用为p的有向边。
4、从每个Xi向Xi+1(i+1<=N)连一条容量为无穷大，费用为0的有向边。
5、从每个Xi向Yi+m(i+m<=N)连一条容量为无穷大，费用为f的有向边。
6、从每个Xi向Yi+n(i+n<=N)连一条容量为无穷大，费用为s的有向边。
#include <iostream>
#include <cstdio>
using namespace std;
const int oo=1e9;//无穷大
const int maxm=1111111;//边的最大数量，为原图的两倍
const int maxn=2222;//点的最大数量
int node,src,dest,edge;//node节点数，src源点，dest汇点，edge边数
int head[maxn],p[maxn],dis[maxn],q[maxn],vis[maxn];//head链表头，p记录可行流上节点对应的反向边，dis计算距离
struct edgenode
{
int to;//边的指向
int flow;//边的容量
int cost;//边的费用
int next;//链表的下一条边
} edges[maxm];
void prepare(int _node,int _src,int _dest);
void addedge(int u,int v,int f,int c);
bool spfa();
inline int min(int a,int b)
{
return a<b?a:b;
}
inline void prepare(int _node,int _src,int _dest)
{
node=_node;
src=_src;
dest=_dest;
for (int i=0; i<node; i++)
{
head[i]=-1;
vis[i]=false;
}
edge=0;
}
void addedge(int u,int v,int f,int c)
{
edges[edge].flow=f;
edges[edge].cost=c;
edges[edge].to=v;
edges[edge].next=head[u];
head[u]=edge++;
edges[edge].flow=0;
edges[edge].cost=-c;
edges[edge].to=u;
edges[edge].next=head[v];
head[v]=edge++;
}
bool spfa()
{
int i,u,v,l,r=0,tmp;
for (i=0; i<node; i++) dis[i]=oo;
dis[q[r++]=src]=0;
p[src]=p[dest]=-1;
for (l=0; l!=r; ((++l>=maxn)?l=0:1))
{
for (i=head[u=q[l]],vis[u]=false; i!=-1; i=edges[i].next)
{
if (edges[i].flow&&dis[v=edges[i].to]>(tmp=dis[u]+edges[i].cost))
{
dis[v]=tmp;
p[v]=i^1;
if (vis[v]) continue;
vis[q[r++]=v]=true;
if (r>=maxn) r=0;
}
}
}
return p[dest]>=0;
}
int spfaflow()
{
int i,ret=0,delta;
while (spfa())
{
//按记录原路返回求流量
for (i=p[dest],delta=oo; i>=0; i=p[edges[i].to])
{
delta=min(delta,edges[i^1].flow);
}
for (int i=p[dest]; i>=0; i=p[edges[i].to])
{
edges[i].flow+=delta;
edges[i^1].flow-=delta;
}
ret+=delta*dis[dest];
}
return ret;
}
int main()
{
// freopen("cin.txt","r",stdin);
int N,p,m,f,n,s;
while(~scanf("%d%d%d%d%d%d",&N,&p,&m,&f,&n,&s))
{
prepare(N*2+2,0,N*2+1);
for(int i=1;i<=N;i++)
{
int r;
scanf("%d",&r);
addedge(src,i,r,0);
if(i!=N)
addedge(i,i+1,oo,0);
addedge(i+N,dest,r,0);
addedge(src,i+N,oo,p);
if(i+m<=N)
addedge(i,i+m+N,oo,f);
if(i+n<=N)
addedge(i,i+n+N,oo,s);
}
printf("%d\n",spfaflow());
}
return 0;
} 5.最大费用最大流
1、对于每个顶点i，j为i东边或南边相邻的一个节点，连接节点i与节点j一条容量为1，费用为该边价值的有向边。2、对于每个顶点i，j为i东边或南边相邻的一个节点，连接节点i与节点j一条容量为无穷大，费用为0的有向边。（可以多走，但是价值没有）
3、从S到每个出发点i连接一条容量为该点出发的机器人数量，费用为0的有向边。
4、从每个目标点i到T连接一条容量为可以到达该点的机器人数量，费用为0的有向边。
求最大费用最大流，最大费用流值就采集到的生物标本的最高总价值。
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int oo=1e9;//无穷大
const int maxm=1111111;//边的最大数量，为原图的两倍
const int maxn=2222;//点的最大数量
int node,src,dest,edge;//node节点数，src源点，dest汇点，edge边数
int head[maxn],p[maxn],dis[maxn],q[maxn],vis[maxn];//head链表头，p记录可行流上节点对应的反向边，dis计算距离
struct edgenode
{
int to;//边的指向
int flow;//边的容量
int cost;//边的费用
int next;//链表的下一条边
} edges[maxm];
void prepare(int _node,int _src,int _dest);
void addedge(int u,int v,int f,int c);
bool spfa();
inline int min(int a,int b)
{
return a<b?a:b;
}
inline void prepare(int _node,int _src,int _dest)
{
node=_node;
src=_src;
dest=_dest;
for (int i=0; i<node; i++)
{
head[i]=-1;
vis[i]=false;
}
edge=0;
}
void addedge(int u,int v,int f,int c)
{
edges[edge].flow=f;
edges[edge].cost=c;
edges[edge].to=v;
edges[edge].next=head[u];
head[u]=edge++;
edges[edge].flow=0;
edges[edge].cost=-c;
edges[edge].to=u;
edges[edge].next=head[v];
head[v]=edge++;
}
bool spfa()
{
int i,u,v,l,r=0,tmp;
for (i=0; i<node; i++) dis[i]=oo;
dis[q[r++]=src]=0;
p[src]=p[dest]=-1;
for (l=0; l!=r; ((++l>=maxn)?l=0:1))
{
for (i=head[u=q[l]],vis[u]=false; i!=-1; i=edges[i].next)
{
if (edges[i].flow&&dis[v=edges[i].to]>(tmp=dis[u]+edges[i].cost))
{
dis[v]=tmp;
p[v]=i^1;
if (vis[v]) continue;
vis[q[r++]=v]=true;
if (r>=maxn) r=0;
}
}
}
return p[dest]>=0;
}
int spfaflow()
{
int i,ret=0,delta;
while (spfa())
{
//按记录原路返回求流量
for (i=p[dest],delta=oo; i>=0; i=p[edges[i].to])
{
delta=min(delta,edges[i^1].flow);
}
for (int i=p[dest]; i>=0; i=p[edges[i].to])
{
edges[i].flow+=delta;
edges[i^1].flow-=delta;
}
ret+=delta*dis[dest];
}
return ret;
}
int main()
{
//freopen("cin.txt","r",stdin);
int a,b,p,q,tmp,u,v;
while(~scanf("%d%d",&a,&b))
{
scanf("%d%d",&p,&q);
p++,q++;
prepare(p*q+2,0,p*q+1);
for(int i=0;i<p;i++)
for(int j=1;j<q;j++)
{
u=i*q+j;
v=u+1;
scanf("%d",&tmp);
addedge(u,v,1,-tmp);
addedge(u,v,oo,0);
}
for(int j=1;j<=q;j++)
for(int i=0;i<p-1;i++)
{
u=i*q+j;
v=u+q;
scanf("%d",&tmp);
addedge(u,v,1,-tmp);
addedge(u,v,oo,0);
}
int x,y,c;
while(a--)
{
scanf("%d%d%d",&c,&x,&y);
addedge(0,x*q+y+1,c,0);
}
while(b--)
{
scanf("%d%d%d",&c,&x,&y);
addedge(x*q+y+1,dest,c,0);
}
printf("%d\n",-spfaflow());
}
return 0;
}
<span style="font-size:14px;">
</span>6.分层图：
1.求最长上升子序列的大小 ，dp搞定2.不重叠最长上升子序列的个数：之前求出了每个点的dp值，从源点是dp=0开始连接每次dp加1而且在它后面而且值比它大的边，最后和汇点连接的是所有dp=max的点，当然因为限制每个点只用一次，所以要拆点。
3.方法同2，但是用于1,n两个点可用多次，故与之相连的边流量不是1而是正无穷
[cpp] view plain copy
print?
#include<cstdio>
#include<iostream>
using namespace std;
const int oo=1e9;
/**oo 表示无穷大*/
const int mm=111111;
/**mm 表示边的最大数量，记住要是原图的两倍，在加边的时候都是双向的*/
const int mn=999;
/*mn 表示点的最大数量*/
int node,src,dest,edge;
/*node 表示节点数，src 表示源点，dest 表示汇点，edge 统计边数*/
int ver[mm],flow[mm],next[mm];
/*ver 边指向的节点，flow 边的容量，next 链表的下一条边*/
int head[mn],work[mn],dis[mn],q[mn];
/*head 节点的链表头，work 用于算法中的临时链表头，dis 计算距离*/
/*初始化链表及图的信息*/
void prepare(int _node,int _src,int _dest)
{
node=_node,src=_src,dest=_dest;
for(int i=0; i<node; ++i)head[i]=-1;
edge=0;
}
/*增加一条u 到v 容量为c 的边*/
void addedge(int u,int v,int c)
{
ver[edge]=v,flow[edge]=c,next[edge]=head[u],head[u]=edge++;
ver[edge]=u,flow[edge]=0,next[edge]=head[v],head[v]=edge++;
}
/*广搜计算出每个点与源点的最短距离，如果不能到达汇点说明算法结束*/
bool Dinic_bfs()
{
int i,u,v,l,r=0;
for(i=0; i<node; ++i)dis[i]=-1;
dis[q[r++]=src]=0;
for(l=0; l<r; ++l)
for(i=head[u=q[l]]; i>=0; i=next[i])
if(flow[i]&&dis[v=ver[i]]<0)
{
/*这条边必须有剩余容量*/
dis[q[r++]=v]=dis[u]+1;
if(v==dest)return 1;
}
return 0;
}
/**寻找可行流的增广路算法，按节点的距离来找，加快速度*/
int Dinic_dfs(int u,int exp)
{
if(u==dest)return exp;
/**work 是临时链表头，这里用i 引用它，这样寻找过的边不再寻找*/
for(int &i=work[u],v,tmp; i>=0; i=next[i])
if(flow[i]&&dis[v=ver[i]]==dis[u]+1&&(tmp=Dinic_dfs(v,min(exp,flow[i])))>0)
{
flow[i]-=tmp;
flow[i^1]+=tmp;
/**正反向边容量改变*/
return tmp;
}
return 0;
}
int Dinic_flow()
{
int i,ret=0,delta;
while(Dinic_bfs())
{
for(i=0; i<node; ++i)work[i]=head[i];
while(delta=Dinic_dfs(src,oo))ret+=delta;
}
return ret;
}
int a[10005],f[10005],F[10005];
int main()
{
int n,s;
while(~scanf("%d",&n))
{
for (int i=1; i<=n; i++)
{
scanf("%d",&a[i]);
}
s=-1;
for (int i=1; i<=n; i++)
{
f[i]=1;
for (int j=1; j<i; j++)
{
if (f[j]+1>f[i]&&a[j]<a[i])
{
f[i]=f[j]+1;
}
}
if (f[i]>s) s=f[i];
}
cout << s<< endl;
prepare(n+n+2,0,n+n+1);
for(int i=1;i<=n;i++)
{
if(f[i]==s)
addedge(i+n,dest,1);
if(f[i]==1)
addedge(src,i,1);
addedge(i,i+n,1);
}
for(int i=1;i<=n;i++)
for(int j=1;j<i;j++)
{
if(f[j]+1==f[i]&&a[i]>a[j])
{
addedge(j+n,i,1);
}
}
int ans1=Dinic_flow();
cout<<ans1<<endl;
prepare(n*2+2,0,n*2+1);
for (int i=1; i<=n; i++)
{
if (i==1||i==n)
{
addedge(i,i+n,oo);
if (f[i]==1) addedge(src,i,oo);
if (f[i]==s) addedge(i+n,dest,oo);
}
else
{
addedge(i,i+n,1);
if (f[i]==1) addedge(src,i,1);
if (f[i]==s) addedge(i+n,dest,1);
}
for (int j=1; j<i; j++)
{
if (f[j]+1==f[i]&&a[i]>a[j]) addedge(j+n,i,1);
}
}
int ans2=Dinic_flow();
if (ans2>oo)//至于这里为什么加这么一个判断，是因为如果有两个节点的时候我们视为只有一种（这么说有点牵强，是题目不严谨==）
cout<<ans1<<endl;
else
cout<<ans2<<endl;
}
return 0;
}
<span style="font-size:14px;">
</span>7.二分图点权最大独立集
nefu482方格取数【最大点权独立集】网络流24题
最大点权独立集=总值-最小边权覆盖=总值-最大流 当然了是得建二分图的== #include <stdio.h>
#include<cstring>
#include <iostream>
using namespace std;
const int oo=0x3f3f3f3f;
const int mm=111111;
const int mn=2000;
int node ,scr,dest,edge;
int ver[mm],flow[mm],next[mm];
int head[mn],work[mn],dis[mn],q[mn];
void prepare(int _node,int _scr,int _dest)
{
node=_node,scr=_scr,dest=_dest;
for(int i=0; i<node; ++i)
head[i]=-1;
edge=0;
}
void addedge(int u,int v,int c)
{
ver[edge]=v,flow[edge]=c,next[edge]=head[u],head[u]=edge++;
ver[edge]=u,flow[edge]=0,next[edge]=head[v],head[v]=edge++;
}
bool Dinic_bfs()
{
int i,u,v,l,r=0;
for(i=0; i<node; i++)
dis[i]=-1;
dis[q[r++]=scr]=0;
for(l=0; l<r; ++l)
{
for(i=head[u=q[l]]; i>=0; i=next[i])
{
if(flow[i]&&dis[v=ver[i]]<0)
{
dis[q[r++]=v]=dis[u]+1;
if(v==dest)
return 1;
}
}
}
return 0;
}
int Dinic_dfs(int u,int exp)
{
if(u==dest)
return exp;
for(int &i=work[u],v,tmp; i>=0; i=next[i])
if(flow[i]&&dis[v=ver[i]]==dis[u]+1&&(tmp=Dinic_dfs(v,min(exp,flow[i])))>0)
{
flow[i]-=tmp;
flow[i^1]+=tmp;
return tmp;
}
return 0;
}
int Dinic_flow()
{
int i,ret=0,delta;
while(Dinic_bfs())
{
for(i=0; i<node; i++)
work[i]=head[i];
while(delta=Dinic_dfs(scr,oo))
ret+=delta;
}
return ret;
}
int num,dir[4][2]={0,1,1,0,0,-1,-1,0};
int main()
{
freopen("cin.txt","r",stdin);
int n,m,sum,cnt;
while(~scanf("%d%d",&m,&n))
{
sum=0;
bool flag=1;
prepare(n*m+3,0,n*m+1);
// memset(col,0,sizeof(col));
for(int i=1;i<=m;i++)
{
flag=i&1;///
for(int j=1;j<=n;j++)
{
scanf("%d",&num);
sum+=num;
if(flag) addedge(scr,(i-1)*n+j,num);
else addedge((i-1)*n+j,dest,num);
flag=1-flag;
}
}
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
if ((i+j)%2==0)///
for(int k=0;k<4;k++)
if(i+dir[k][0]>=1&&i+dir[k][0]<=m&&j+dir[k][1]>=1&&j+dir[k][1]<=n)
addedge((i-1)*n+j,(i+dir[k][0]-1)*n+j+dir[k][1],oo);
printf("%d\n",sum-Dinic_flow());
}
return 0;
} 8. 最大权不相交路径问题==>最大费用最大流
nefu495最长k可重区间集问题【最大权不相交路径】网络流24题
题意：给出一堆开区间，要求取出一些区间使得重叠次数最多是k,求取出的区间长度最长是多少？
简易做法：（复杂度高）
正常的拆点限制流量和费用，在源点前面再加一个超级源点两个相连，限制k。
高效做法：
其实只是比上面的方法多了一步离散化==
离散化所有区间的端点，把每个端点看做一个顶点，建立附加源S汇T。
1、从S到顶点1（最左边顶点）连接一条容量为K，费用为0的有向边。
2、从顶点2N（最右边顶点）到T连接一条容量为K，费用为0的有向边。
3、从顶点i到顶点i+1(i+1<=2N)，连接一条容量为无穷大，费用为0的有向边。
4、对于每个区间[a,b]，从a对应的顶点i到b对应的顶点j连接一条容量为1，费用为区间长度的有向边。
#include<cstdio>
#include<algorithm>
using namespace std;
const int mm=3333;
const int mn=1111;
const int oo=1000000000;
int node,src,dest,edge;
int reach[mm],flow[mm],cost[mm],next[mm];
int head[mn],dis[mn],q[mn],p[mn],a[mn],x[mn],y[mn];
bool vis[mn];
inline void prepare(int _node,int _src,int _dest)
{
node=_node,src=_src,dest=_dest;
for(int i=0;i<node;++i)head[i]=-1;
edge=0;
}
inline void addedge(int u,int v,int f,int c)
{
reach[edge]=v,flow[edge]=f,cost[edge]=c,next[edge]=head[u],head[u]=edge++;
reach[edge]=u,flow[edge]=0,cost[edge]=-c,next[edge]=head[v],head[v]=edge++;
}
bool spfa()
{
int i,u,v,l,r=0,tmp;
for(i=0;i<node;++i)dis[i]=oo;
dis[q[r++]=src]=0;
p[src]=p[dest]=-1;
for(l=0;l!=r;(++l==mn)?l=0:1)
for(i=head[u=q[l]],vis[u]=0;i>=0;i=next[i])
if(flow[i]&&dis[v=reach[i]]>(tmp=dis[u]+cost[i]))
{
dis[v]=tmp;
p[v]=i^1;
if(vis[v])continue;
vis[q[r++]=v]=1;
if(r==mn)r=0;
}
return p[dest]>=0;
}
int SpfaFlow()
{
int i,ret=0,delta;
while(spfa())
{
for(i=p[dest],delta=oo;i>=0;i=p[reach[i]])
if(delta>flow[i^1])delta=flow[i^1];
for(i=p[dest];i>=0;i=p[reach[i]])
flow[i]+=delta,flow[i^1]-=delta;
ret-=delta*dis[dest];
}
return ret;
}
int find(int x,int m)
{
int l=0,r=m;
while(l<r)
{
m=(l+r)>>1;
if(a[m]==x)return m;
if(a[m]>x)r=m-1;
else l=m+1;
}
return l;
}
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
int i,u,v,n,k,m;
while(scanf("%d%d",&n,&k)!=-1)
{
for(m=i=0;i<n;++i)scanf("%d%d",&x[i],&y[i]),a[m++]=x[i],a[m++]=y[i];
sort(a,a+m);
for(v=0,u=1;u<m;++u)
if(a[u]>a[v])a[++v]=a[u];
m=v+1;
prepare(m+2,0,m+1);
addedge(src,1,k,0);
addedge(m,dest,k,0);
for(u=1;u<m;++u)addedge(u,u+1,oo,0);
for(i=0;i<n;++i)
addedge(find(x[i],m-1)+1,find(y[i],m-1)+1,1,x[i]-y[i]);
printf("%d\n",SpfaFlow());
}
return 0;
}
9.有向无环图最小路径覆盖并输出
nefu486魔术球问题【有向无环图最小路径覆盖】
路径覆盖是指：有那么一条路径可以覆盖其边上的点，最少路径覆盖是指：最少需要多少条边可以覆盖所有点，这里注意一个问题，它不是二分图……做法：假定0,1分别是源点和汇点（因为个数不定啊……）根据和等于平方数先把1-n加进去，逐渐加边，直到 ans>Dinic_flow()+n ans表示现有点的个数,n表示柱子个数（即路径个数）
#include<cstdio>
using namespace std;
const int mm=1111111;
const int mn=11111;
const int oo=1000000000;
int node,src,dest,edge,ret;
int reach[mm],cap[mm],flow[mm],next[mm];
int head[mn],work[mn],dis[mn],q[mn];
bool square[mn]={0};
inline int min(int a,int b)
{
return a<b?a:b;
}
inline void prepare(int _node,int _src,int _dest)
{
node=_node,src=_src,dest=_dest;
for(int i=0;i<node;++i)head[i]=-1;
edge=ret=0;
}
inline void addedge(int u,int v,int c)
{
reach[edge]=v,cap[edge]=c,flow[edge]=0,next[edge]=head[u],head[u]=edge++;
reach[edge]=u,cap[edge]=0,flow[edge]=0,next[edge]=head[v],head[v]=edge++;
}
bool Dinic_bfs()
{
int i,u,v,l,r=0;
for(i=0;i<node;++i)dis[i]=-1;
dis[q[r++]=src]=0;
for(l=0;l<r;++l)
for(i=head[u=q[l]];i>=0;i=next[i])
if(flow[i]<cap[i]&&dis[v=reach[i]]<0)
{
dis[q[r++]=v]=dis[u]+1;
if(v==dest)return 1;
}
return 0;
}
int Dinic_dfs(int u,int exp)
{
if(u==dest)return exp;
for(int &i=work[u],v,tmp;i>=0;i=next[i])
if(flow[i]<cap[i]&&dis[v=reach[i]]==dis[u]+1&&(tmp=Dinic_dfs(v,min(exp,cap[i]-flow[i])))>0)
{
flow[i]+=tmp;
flow[i^1]-=tmp;
return tmp;
}
return 0;
}
int Dinic_flow()
{
int i,delta;
while(Dinic_bfs())
{
for(i=0;i<node;++i)work[i]=head[i];
while((delta=Dinic_dfs(src,oo)))ret+=delta;
}
return ret;
}
void output(int u)
{
q[u>>1]=1;
for(int i=head[u],v;i>=0;i=next[i])
if(q[v=reach[i]>>1]==0&&flow[i]==1)printf(" %d",v),output(v<<1);
}
int main()
{
//freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
int i,n,u,v,ans;
for(i=1;i*i<mn;++i)square[i*i]=1;
while(scanf("%d",&n)!=-1)
{
ans=n;
prepare(n+n+2,0,1);
for(u=2;u<n+n+2;++u)
if(u&1)addedge(u,dest,1);
else addedge(src,u,1);
for(u=1;u<=n;++u)
for(v=u+1;v<=n;++v)
if(square[u+v])addedge(u<<1,(v<<1)+1,1);
while(ans<=Dinic_flow()+n)
{
++ans;
head[u=node++]=-1;
head[v=node++]=-1;
addedge(0,u,1);
addedge(v,1,1);
for(u=1;u<ans;++u)
if(square[u+ans])addedge(u<<1,v,1);
}
printf("%d\n",ans-1);
n=ans-1;
/* prepare(n+n+2,0,1);
for(u=2;u<n+n+2;++u)
if(u&1)addedge(u,dest,1);
else addedge(src,u,1);
for(u=1;u<=n;++u)
for(v=u+1;v<=n;++v)
if(square[u+v])addedge(u<<1,(v<<1)+1,1);
Dinic_flow();
for(u=1;u<ans;++u)q[u]=0;
for(u=1;u<ans;++u)
if(!q[u])
{
printf("%d",u);
output(u<<1);
printf("\n");
}*/
}
} 10.二分图多重匹配并输出
圆桌问题【二分图多重匹配】网络流24题
对于一个二分图，每个顶点可以有多个匹配顶点，称这类问题为二分图多重匹配问题。X，Y集合之间的边容量全部是1，保证两个点只能匹配一次（一个餐桌上只能有一个单位的一个人），源汇的连边限制了每个点匹配的个数 #include<cstdio>
using namespace std;
const int mm=555555;
const int mn=555;
const int oo=1000000000;
int node,src,dest,edge;
int reach[mm],flow[mm],next[mm];
int head[mn],work[mn],dis[mn],q[mn];
inline int min(int a,int b)
{
return a<b?a:b;
}
inline void prepare(int _node,int _src,int _dest)
{
node=_node,src=_src,dest=_dest;
for(int i=0;i<node;++i)head[i]=-1;
edge=0;
}
inline void addedge(int u,int v,int c)
{
reach[edge]=v,flow[edge]=c,next[edge]=head[u],head[u]=edge++;
reach[edge]=u,flow[edge]=0,next[edge]=head[v],head[v]=edge++;
}
bool Dinic_bfs()
{
int i,u,v,l,r=0;
for(i=0;i<node;++i)dis[i]=-1;
dis[q[r++]=src]=0;
for(l=0;l<r;++l)
for(i=head[u=q[l]];i>=0;i=next[i])
if(flow[i]&&dis[v=reach[i]]<0)
{
dis[q[r++]=v]=dis[u]+1;
if(v==dest)return 1;
}
return 0;
}
int Dinic_dfs(int u,int exp)
{
if(u==dest)return exp;
for(int &i=work[u],v,tmp;i>=0;i=next[i])
if(flow[i]&&dis[v=reach[i]]==dis[u]+1&&(tmp=Dinic_dfs(v,min(exp,flow[i])))>0)
{
flow[i]-=tmp;
flow[i^1]+=tmp;
return tmp;
}
return 0;
}
int Dinic_flow()
{
int i,ret=0,delta;
while(Dinic_bfs())
{
for(i=0;i<node;++i)work[i]=head[i];
while((delta=Dinic_dfs(src,oo)))ret+=delta;
}
return ret;
}
int main()
{
freopen("cin.txt","r",stdin);
// freopen("output.txt","w",stdout);
int m,n,u,v,c,sum;
while(scanf("%d%d",&m,&n)&&n)
{
prepare(m+n+2,0,m+n+1);
sum=0;
for(u=1;u<=m;++u)scanf("%d",&c),addedge(src,u,c),sum+=c;
for(v=1;v<=n;++v)scanf("%d",&c),addedge(v+m,dest,c);
for(u=1;u<=m;++u)
for(v=n;v>0;--v)addedge(u,v+m,1);
if(Dinic_flow()==sum)
{
printf("1\n");
for(u=1;u<=m;printf("\n"),++u)
for(c=head[u];c>=0;c=next[c])
if(flow[c^1])printf("%d ",reach[c]-m);
}
else printf("0\n");
}
} 11.2015多校联合第一场
hdu5294Tricks Device【最短路+网络流】
从1开始到n结束，给出双向道路，问至少去掉多少边最短路不是原始最短路长度，至多去掉多少条边最短路长度不变既然说问到的是与最短路有关的，那我是一定要求一遍最短路的，关于怎么求出已知的某个边是否在起点与终点之间的最短路上：求一遍dist1[]表示从1到1-n的最短路，dist2[]表示n到1-n的最短路，枚举每个边：左边最短路+此边长+右边最短路是否等于1到n的最短路即可。给这对点建网络流的边，流量是1，跑网络流是第一问答案。why?最大流等于最小割，最小割就是去掉多少边破坏原来的最短路。
依旧是利用在最短路上的边建边，这次建立最短路，边长=1，dist[n]是最短路的最少边长，那么总边数-dist[n]就是答案
#include <iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int inf=0x3f3f;
const int maxn=2111;
int n,m;
struct Edge
{
int v,cost;
Edge(int _v=0,int _cost=0):v(_v),cost(_cost){}
};
vector<Edge>E[maxn];
void addedge(int u,int v,int w)
{
E[u].push_back(Edge(v,w));
}
bool vis[maxn];
int cnt[maxn];
int dist[maxn],dist1[maxn];
bool spfa(int start,int n)
{
memset(vis,false,sizeof(vis));
memset(dist,inf,sizeof(dist));
vis[start]=true;
dist[start]=0;
queue<int>que;
while(!que.empty()) que.pop();
que.push(start);
memset(cnt,0,sizeof(cnt));
cnt[start]=1;
while(!que.empty())
{
int u=que.front();
que.pop();
vis[u]=false;
for(int i=0;i<E[u].size();i++)
{
int v=E[u][i].v;
if(dist[v]>dist[u]+E[u][i].cost)
{
dist[v]=dist[u]+E[u][i].cost;
if(!vis[v])
{
vis[v]=true;
que.push(v);
if(++cnt[v]>n) return false;
}
}
}
}
return true;
}
int w[60009],u[60009],v[60009];
////////////////////////////////////////
const int mm=161111;
const int mn=600009;
const int oo=1000000000;
int node,src,dest,edge;
int reach[mm],flow[mm],nxt[mm];
int head[mn],work[mn],dis[mn],q[mn];
inline int min(int a,int b)
{
return a<b?a:b;
}
inline void prepare(int _node,int _src,int _dest)
{
node=_node,src=_src,dest=_dest;
for(int i=0;i<node;++i)head[i]=-1;
edge=0;
}
inline void addedge(int u,int v,int c1,int c2)
{
reach[edge]=v,flow[edge]=c1,nxt[edge]=head[u],head[u]=edge++;
reach[edge]=u,flow[edge]=c2,nxt[edge]=head[v],head[v]=edge++;
}
bool Dinic_bfs()
{
int i,u,v,l,r=0;
for(i=0;i<node;++i)dis[i]=-1;
dis[q[r++]=src]=0;
for(l=0;l<r;++l)
for(i=head[u=q[l]];i>=0;i=nxt[i])
if(flow[i]&&dis[v=reach[i]]<0)
{
dis[q[r++]=v]=dis[u]+1;
if(v==dest)return 1;
}
return 0;
}
int Dinic_dfs(int u,int exp)
{
if(u==dest)return exp;
for(int &i=work[u],v,tmp;i>=0;i=nxt[i])
if(flow[i]&&dis[v=reach[i]]==dis[u]+1&&(tmp=Dinic_dfs(v,min(exp,flow[i])))>0)
{
flow[i]-=tmp;
flow[i^1]+=tmp;
return tmp;
}dis[u]--;
return 0;
}
int Dinic_flow()
{
int i,ret=0,delta;
while(Dinic_bfs())
{
for(i=0;i<node;++i)work[i]=head[i];
while(delta=Dinic_dfs(src,oo))ret+=delta;
}
return ret;
}
int bb[mn][2],dist2[mn];
int main()
{
// freopen("cin.txt","r",stdin);
while(~scanf("%d%d",&n,&m))
{
for(int i=0;i<=n;i++) E[i].clear();
for(int i=0;i<m;i++)
{
scanf("%d%d%d",&u[i],&v[i],&w[i]);
addedge(u[i],v[i],w[i]);
addedge(v[i],u[i],w[i]);
}
spfa(1,n);
memcpy(dist2,dist,sizeof(dist));
spfa(n,n);
int k=0;
for(int i=0;i<m;i++)
{
if(dist2[u[i]]>dist2[v[i]])swap(u[i],v[i]);
if(dist[v[i]]+w[i]+dist2[u[i]]==dist2[n])
{
bb[k][0]=u[i];
bb[k++][1]=v[i];
}
}
prepare(n+1,1,n);
for(int i=0;i<k;i++)
{
addedge(bb[i][0],bb[i][1],1,0);
// addedge(bb[i][1],bb[i][0],1);
}
int x=Dinic_flow();
for(int i=0;i<=n;i++) E[i].clear();
for(int i=0;i<k;i++)
{
addedge(bb[i][0],bb[i][1],1);
addedge(bb[i][1],bb[i][0],1);
}
spfa(1,n);
printf("%d %d\n",x,m-dist[n]);
}
return 0;
} 12.
hdu4975A simple Gaussian elimination problem.【网络流判断是否解唯一】
刚刚才理解明白
- bool dfs(int u,int pre)
- {
- int biu=-1;
- mark[u]=true;
- for(int i=head[u];i!=-1;i=nxt[i])
- {
- int v=reach[i];
- if(pre==v)continue;
- if(flow[i]>0)
- {
- if(mark[v])return true;
- if(dfs(v,u))return true;
- }
- if(biu==-1) head[u]=nxt[i];
- else nxt[biu]=nxt[i];
- biu=i;
- }
- mark[u]=false;
- return false;
- }
当中if ...else...是咋意思：既然是链式前向星，就是以head为开头以此往下接的，然而在本题中是要将遍历过的&&没有正环的截掉，如果不是开头那么next接next，如果当前是从某点开头的，那么接的是head
#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int mm=1000000;
const int mn=505*505*3;
const int oo=1000000000;
int node,src,dest,edge;
int reach[mm],flow[mm],nxt[mm];
int head[mn],work[mn],dis[mn],q[mn];
inline int min(int a,int b)
{
return a<b?a:b;
}
inline void prepare(int _node,int _src,int _dest)
{
node=_node,src=_src,dest=_dest;
for(int i=0;i<node;++i)head[i]=-1;
edge=0;
}
inline void addedge(int u,int v,int c1,int c2)
{
reach[edge]=v,flow[edge]=c1,nxt[edge]=head[u],head[u]=edge++;
reach[edge]=u,flow[edge]=c2,nxt[edge]=head[v],head[v]=edge++;
}
bool Dinic_bfs()
{
int i,u,v,l,r=0;
for(i=0;i<node;++i)dis[i]=-1;
dis[q[r++]=src]=0;
for(l=0;l<r;++l)
for(i=head[u=q[l]];i>=0;i=nxt[i])
if(flow[i]&&dis[v=reach[i]]<0)
{
dis[q[r++]=v]=dis[u]+1;
if(v==dest)return 1;
}
return 0;
}
int Dinic_dfs(int u,int exp)
{
if(u==dest)return exp;
for(int &i=work[u],v,tmp;i>=0;i=nxt[i])
if(flow[i]&&dis[v=reach[i]]==dis[u]+1&&(tmp=Dinic_dfs(v,min(exp,flow[i])))>0)
{
flow[i]-=tmp;
flow[i^1]+=tmp;
return tmp;
}dis[u]--;
return 0;
}
int Dinic_flow()
{
int i,ret=0,delta;
while(Dinic_bfs())
{
for(i=0;i<node;++i)work[i]=head[i];
while(delta=Dinic_dfs(src,oo))ret+=delta;
}
return ret;
}
///====================
int mark[mn];
bool dfs(int u,int pre)
{
int biu=-1;
mark[u]=true;
for(int i=head[u];i!=-1;i=nxt[i])
{
int v=reach[i];
if(pre==v)continue;
if(flow[i]>0)
{
if(mark[v])return true;
if(dfs(v,u))return true;
}
if(biu==-1) head[u]=nxt[i];
else nxt[biu]=nxt[i];
biu=i;
}
mark[u]=false;
return false;
}
bool judge()
{
memset(mark,false,sizeof(mark));
for(int i=1;i<=node;i++)
if(dfs(i,-1))return true;
return false;
}
///====================
int main()
{
// freopen("cin.txt","r",stdin);
int n,m,t,cas=1;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
prepare(n+m+2,0,n+m+1);
int sum=0;
for(int i=1;i<=n;i++)
{
int a;
scanf("%d",&a);
sum+=a;
addedge(0,i,a,0);
}
for(int i=1+n;i<=n+m;i++)
{
int a;
scanf("%d",&a);
addedge(i,n+m+1,a,0);
}
for(int i=1;i<=n;i++)
for(int j=n+1;j<=n+m;j++)
addedge(i,j,9,0);
int total=Dinic_flow();
if(sum!=total)
printf("Case #%d: So naive!\n",cas++);
else if(judge())
printf("Case #%d: So young!\n",cas++);
else printf("Case #%d: So simple!\n",cas++);
}
return 0;
}
13.同第二题：
HDU 4289Control【最大流已知点权拆点】
#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int mm=220005;
const int mn=22222;
const int oo=1000000000;
int node,src,dest,edge;
int reach[mm],flow[mm],nxt[mm];
int head[mn],work[mn],dis[mn],q[mn];
inline int min(int a,int b)
{
return a<b?a:b;
}
inline void prepare(int _node,int _src,int _dest)
{
node=_node,src=_src,dest=_dest;
memset(head,-1,sizeof(head));
edge=0;
}
inline void addedge(int u,int v,int c1,int c2)
{
reach[edge]=v,flow[edge]=c1,nxt[edge]=head[u],head[u]=edge++;
reach[edge]=u,flow[edge]=c2,nxt[edge]=head[v],head[v]=edge++;
}
bool Dinic_bfs()
{
int i,u,v,l,r=0;
for(i=0;i<node;++i)dis[i]=-1;
dis[q[r++]=src]=0;
for(l=0;l<r;++l)
for(i=head[u=q[l]];i>=0;i=nxt[i])
if(flow[i]&&dis[v=reach[i]]<0)
{
dis[q[r++]=v]=dis[u]+1;
if(v==dest)return 1;
}
return 0;
}
int Dinic_dfs(int u,int exp)
{
if(u==dest)return exp;
for(int &i=work[u],v,tmp;i>=0;i=nxt[i])
if(flow[i]&&dis[v=reach[i]]==dis[u]+1&&(tmp=Dinic_dfs(v,min(exp,flow[i])))>0)
{
flow[i]-=tmp;
flow[i^1]+=tmp;
return tmp;
}dis[u]--;
return 0;
}
int Dinic_flow()
{
int i,ret=0,delta;
while(Dinic_bfs())
{
for(i=0;i<node;++i)work[i]=head[i];
while(delta=Dinic_dfs(src,oo))ret+=delta;
}
return ret;
}
int main()
{
// freopen("cin.txt","r",stdin);
int n,m,s,d;
while(~scanf("%d%d",&n,&m))
{
scanf("%d%d",&s,&d);
//s--;d--;
prepare(n*2+1,s,d+n);
for(int i=1;i<=n;i++)
{
int w;
scanf("%d",&w);
// addedge(i<<1|1,i<<1,w,0);
addedge(i,i+n,w,0);
}
for(int i=0;i<m;i++)
{
int a,b;
scanf("%d%d",&a,&b);
//a--;b--;
addedge(a+n,b,oo,0);
addedge(b+n,a,oo,0);
}
printf("%d\n",Dinic_flow());
}
return 0;
} 14.依旧还是警察抓坏蛋
hdu4411Arrest【最小费用最大流 拆点】
题意：给定某些点之间的距离，每个点都有坏蛋，警察分批抓，但是必须先抓编号小的，最后再回到原点，问最小距离做法：由于给定点之间距离，那么就一定要算一下两点之间最短距离。最短距离就变成了花费，流量1.拆点了的费用呢？设一个比较大的值，最后刨出去n*这个数就好啦
#include <iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
int n,m,k;
const int mm=66666;
const int mn=5555;
const int oo=1e9;
int src,dest,node,edge;
int dx[]={0,0,-1,1};
int dy[]={-1,1,0,0};
int ver[mm],cost[mm],flow[mm],nxt[mm];
int head[mn],dis[mn],p[mn],q[mn];
int h[55][55];
bool vis[mn]={0};
void prepare(int _node,int _src,int _dest)
{
node=_node,src=_src,dest=_dest;
for(int i=0;i<node;++i)head[i]=-1;
edge=0;
}
void addedge(int u,int v,int f,int c)
{
ver[edge]=v,flow[edge]=f,cost[edge]=c,nxt[edge]=head[u],head[u]=edge++;
ver[edge]=u,flow[edge]=0,cost[edge]=-c,nxt[edge]=head[v],head[v]=edge++;
}
bool Spfa()
{
int i,u,v,l,r=0,tmp;
for(i=0;i<node;++i)dis[i]=oo;
dis[q[r++]=src]=0;
p[src]=p[dest]=-1;
for(l=0;l!=r;(++l==mn)?l=0:l)
for(i=head[u=q[l]],vis[u]=0;i>=0;i=nxt[i])
if(flow[i]&&dis[v=ver[i]]>(tmp=dis[u]+cost[i]))
{
dis[v]=tmp;
p[v]=i^1;
if(vis[v])continue;
vis[q[r++]=v]=1;
if(r==mn)r=0;
}
return p[dest]>-1;
}
int Spfaflow()
{
int i,delta,ret=0;
while(Spfa())
{
for(i=p[dest],delta=oo;i>=0;i=p[ver[i]])
if(flow[i^1]<delta)delta=flow[i^1];
for(i=p[dest];i>=0;i=p[ver[i]])
flow[i]+=delta,flow[i^1]-=delta;
ret-=delta*dis[dest];
}
return ret;
}
int dist[110][110];
int main()
{
//freopen("cin.txt","r",stdin);
while(~scanf("%d%d%d",&n,&m,&k))
{
if(n==0&&m==0&&k==0) break;
prepare(2*n+3,2*n+1,2*n+2);
memset(dist,0x3f3f3f3f,sizeof(dist));
for(int i=0;i<m;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
if(w<dist[u][v])
dist[u][v]=dist[v][u]=w;
}
for(int i=0;i<=n;i++)
for(int j=0;j<=n;j++)
for(int k=0;k<=n;k++)
if(dist[j][i]+dist[i][k]<dist[j][k])
dist[j][k]=dist[j][i]+dist[i][k];
addedge(src,0,k,0);
addedge(0,dest,k,0);
for(int i=1;i<=n;i++)
{
addedge(0,i,1,dist[0][i]);
addedge(i,i+n,1,-100000);
addedge(i+n,dest,1,dist[i][0]);
}
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++)
addedge(i+n,j,1,dist[i][j]);
}
printf("%d\n",-Spfaflow()+n*100000);
}
return 0;
} 15.
hdu4971A simple brute force problem.【最大权闭合图】
约等于就是裸的题，与第三个题不同的多了一个限制条件：解决问题有前后依赖。很显然是题目给什么条件就怎么建边…… #include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int mm=220005;
const int mn=22222;
const int oo=1000000000;
int node,src,dest,edge;
int reach[mm],flow[mm],nxt[mm];
int head[mn],work[mn],dis[mn],q[mn];
inline int min(int a,int b)
{
return a<b?a:b;
}
inline void prepare(int _node,int _src,int _dest)
{
node=_node,src=_src,dest=_dest;
memset(head,-1,sizeof(head));
edge=0;
}
inline void addedge(int u,int v,int c1)
{
reach[edge]=v,flow[edge]=c1,nxt[edge]=head[u],head[u]=edge++;
reach[edge]=u,flow[edge]=0,nxt[edge]=head[v],head[v]=edge++;
}
bool Dinic_bfs()
{
int i,u,v,l,r=0;
for(i=0;i<node;++i)dis[i]=-1;
dis[q[r++]=src]=0;
for(l=0;l<r;++l)
for(i=head[u=q[l]];i>=0;i=nxt[i])
if(flow[i]&&dis[v=reach[i]]<0)
{
dis[q[r++]=v]=dis[u]+1;
if(v==dest)return 1;
}
return 0;
}
int Dinic_dfs(int u,int exp)
{
if(u==dest)return exp;
for(int &i=work[u],v,tmp;i>=0;i=nxt[i])
if(flow[i]&&dis[v=reach[i]]==dis[u]+1&&(tmp=Dinic_dfs(v,min(exp,flow[i])))>0)
{
flow[i]-=tmp;
flow[i^1]+=tmp;
return tmp;
}dis[u]--;
return 0;
}
int Dinic_flow()
{
int i,ret=0,delta;
while(Dinic_bfs())
{
for(i=0;i<node;++i)work[i]=head[i];
while(delta=Dinic_dfs(src,oo))ret+=delta;
}
return ret;
}
int main()
{
// freopen("cin.txt","r",stdin);
int t,n,m,cas=1;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
prepare(n+m+2,0,n+m+1);
int count=0;
for(int i=1;i<=n;i++)
{
int c;
scanf("%d",&c);
addedge(src,i,c);
count+=c;
}
for(int i=1;i<=m;i++)
{
int c;
scanf("%d",&c);
addedge(n+i,dest,c);
}
for(int i=1;i<=n;i++)
{
int k;
scanf("%d",&k);
while(k--)
{
int c;
scanf("%d",&c);
addedge(i,n+c+1,oo);
}
}
for(int i=1;i<=m;i++)
{
for(int j=1;j<=m;j++)
{
int c;
scanf("%d",&c);
if(c)addedge(n+i,n+j,oo);
}
}
printf("Case #%d: %d\n",cas++,count-Dinic_flow());
}
return 0;
} 16. 这个是有上下界限制的最简单的一类题，具体做法是：上下界的差值作为此边流量，下界限制作为边的起始点与汇点和源点与边的终点的流量。
我们知道flow[]是成对出现的，前一个等于给定流量（最开始是d-c)，后一个是现在的流量（最开始是0）。后一边流量最后取得的最大值+c就是所求。
联系之前的链接分析这个图的建图，由于A->B的流量由d变成了d-c，为了保持流经两个点的流量不变，那么人为加入c的流量
#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int mm=1000000;
const int mn=505*505*3;
const int oo=1000000000;
int node,src,dest,edge;
int reach[mm],flow[mm],nxt[mm];
int head[mn],work[mn],dis[mn],q[mn];
inline int min(int a,int b)
{
return a<b?a:b;
}
inline void prepare(int _node,int _src,int _dest)
{
node=_node,src=_src,dest=_dest;
for(int i=0;i<node;++i)head[i]=-1;
edge=0;
}
inline void addedge(int u,int v,int c1,int c2=0)
{
reach[edge]=v,flow[edge]=c1,nxt[edge]=head[u],head[u]=edge++;
reach[edge]=u,flow[edge]=c2,nxt[edge]=head[v],head[v]=edge++;
}
bool Dinic_bfs()
{
int i,u,v,l,r=0;
for(i=0;i<node;++i)dis[i]=-1;
dis[q[r++]=src]=0;
for(l=0;l<r;++l)
for(i=head[u=q[l]];i>=0;i=nxt[i])
if(flow[i]&&dis[v=reach[i]]<0)
{
dis[q[r++]=v]=dis[u]+1;
if(v==dest)return 1;
}
return 0;
}
int Dinic_dfs(int u,int exp)
{
if(u==dest)return exp;
for(int &i=work[u],v,tmp;i>=0;i=nxt[i])
if(flow[i]&&dis[v=reach[i]]==dis[u]+1&&(tmp=Dinic_dfs(v,min(exp,flow[i])))>0)
{
flow[i]-=tmp;
flow[i^1]+=tmp;
return tmp;
}dis[u]--;
return 0;
}
int Dinic_flow()
{
int i,ret=0,delta;
while(Dinic_bfs())
{
for(i=0;i<node;++i)work[i]=head[i];
while(delta=Dinic_dfs(src,oo))ret+=delta;
}
return ret;
}
int Edge[40000],Flow[40000];
int main()
{
// freopen("cin.txt","r",stdin);
int n,m;
while(~scanf("%d%d",&n,&m))
{
prepare(n+2,0,n+1);
int sum=0;
for(int i=0;i<m;i++)
{
int a,b,c,d;
scanf("%d%d%d%d",&a,&b,&c,&d);
sum+=c;
addedge(src,b,c);
addedge(a,dest,c);
Edge[i]=edge;
Flow[i]=c;
addedge(a,b,d-c);
}
if(sum!=Dinic_flow())
{
puts("NO");
continue;
}
else
{
puts("YES");
for(int i=0;i<m;i++){
printf("%d\n",flow[Edge[i]^1]+Flow[i]);
}
}
}
return 0;
} 17.插座与电源的问题
题意：会议室里面有n种插座，有m种（个）电器需要充电（即每种只有一个），有k种转换器（无限量，而且可以互相插）。问最少有多少电器没地方插。
做法：电器在左边，插座类型在右边（这个题好像不仅有n种插座，电器和转换器都会出现新的插座类型）。电器的点连源点，流量1,；电器与它的插座类型连边，流量1；会议室的插座类型连汇点，流量1；转换器的类型连有向边，流量oo
#include <iostream>
#include<cstdio>
#include<cstring>
#include<map>
using namespace std;
const int mm=220005;
const int mn=22222;
const int oo=1000000000;
int node,src,dest,edge;
int reach[mm],flow[mm],nxt[mm];
int head[mn],work[mn],dis[mn],q[mn];
inline int min(int a,int b)
{
return a<b?a:b;
}
inline void prepare(int _node,int _src,int _dest)
{
node=_node,src=_src,dest=_dest;
memset(head,-1,sizeof(head));
edge=0;
}
inline void addedge(int u,int v,int c1)
{
reach[edge]=v,flow[edge]=c1,nxt[edge]=head[u],head[u]=edge++;
reach[edge]=u,flow[edge]=0,nxt[edge]=head[v],head[v]=edge++;
}
bool Dinic_bfs()
{
int i,u,v,l,r=0;
for(i=0;i<node;++i)dis[i]=-1;
dis[q[r++]=src]=0;
for(l=0;l<r;++l)
for(i=head[u=q[l]];i>=0;i=nxt[i])
if(flow[i]&&dis[v=reach[i]]<0)
{
dis[q[r++]=v]=dis[u]+1;
if(v==dest)return 1;
}
return 0;
}
int Dinic_dfs(int u,int exp)
{
if(u==dest)return exp;
for(int &i=work[u],v,tmp;i>=0;i=nxt[i])
if(flow[i]&&dis[v=reach[i]]==dis[u]+1&&(tmp=Dinic_dfs(v,min(exp,flow[i])))>0)
{
flow[i]-=tmp;
flow[i^1]+=tmp;
return tmp;
}dis[u]--;
return 0;
}
int Dinic_flow()
{
int i,ret=0,delta;
while(Dinic_bfs())
{
for(i=0;i<node;++i)work[i]=head[i];
while(delta=Dinic_dfs(src,oo))ret+=delta;
}
return ret;
}
int receptacles[200],plug[200][2],adapters[200][2];
int main()
{
// freopen("cin.txt","r",stdin);
int n,m,k,ind=0;
map<string,int>M;
string str1,str2;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>str1;
if(!M[str1])M[str1]=++ind;
receptacles[i]=M[str1];
}
cin>>m;
for(int i=1;i<=m;i++)
{
cin>>str1>>str2;
// if(!M[str1])M[str1]=++ind;
if(!M[str2])M[str2]=++ind;
plug[i][0]=i;
plug[i][1]=M[str2];
}
cin>>k;
for(int i=1;i<=k;i++)
{
cin>>str1>>str2;
if(!M[str1])M[str1]=++ind;
if(!M[str2])M[str2]=++ind;
adapters[i][0]=M[str1];
adapters[i][1]=M[str2];
}
prepare(ind+2+m,0,m+ind+1);
for(int i=1;i<=m;i++)
{
addedge(0,i,1);
addedge(i,m+plug[i][1],1);
}
for(int i=1;i<=n;i++)
addedge(receptacles[i]+m,dest,1);
for(int i=1;i<=k;i++)
addedge(adapters[i][0]+m,m+adapters[i][1],oo);
cout<<m-Dinic_flow()<<endl;
return 0;
} 18.
nefu500网购【二分+网络流】
既然是求最大边的最小值，二分找出这个值，大于它的都不要，跑网络流即可 #include <iostream>
#include<cstdio>
#include<cstring>
#include<map>
using namespace std;
const int mm=220005;
const int mn=22222;
const int oo=1000000000;
int node,src,dest,edge;
int reach[mm],flow[mm],nxt[mm];
int head[mn],work[mn],dis[mn],q[mn];
inline int min(int a,int b)
{
return a<b?a:b;
}
inline void prepare(int _node,int _src,int _dest)
{
node=_node,src=_src,dest=_dest;
memset(head,-1,sizeof(head));
edge=0;
}
inline void addedge(int u,int v,int c1)
{
reach[edge]=v,flow[edge]=c1,nxt[edge]=head[u],head[u]=edge++;
reach[edge]=u,flow[edge]=0,nxt[edge]=head[v],head[v]=edge++;
}
bool Dinic_bfs()
{
int i,u,v,l,r=0;
for(i=0;i<node;++i)dis[i]=-1;
dis[q[r++]=src]=0;
for(l=0;l<r;++l)
for(i=head[u=q[l]];i>=0;i=nxt[i])
if(flow[i]&&dis[v=reach[i]]<0)
{
dis[q[r++]=v]=dis[u]+1;
if(v==dest)return 1;
}
return 0;
}
int Dinic_dfs(int u,int exp)
{
if(u==dest)return exp;
for(int &i=work[u],v,tmp;i>=0;i=nxt[i])
if(flow[i]&&dis[v=reach[i]]==dis[u]+1&&(tmp=Dinic_dfs(v,min(exp,flow[i])))>0)
{
flow[i]-=tmp;
flow[i^1]+=tmp;
return tmp;
}dis[u]--;
return 0;
}
int Dinic_flow()
{
int i,ret=0,delta;
while(Dinic_bfs())
{
for(i=0;i<node;++i)work[i]=head[i];
while(delta=Dinic_dfs(src,oo))ret+=delta;
}
return ret;
}
int sum,need[mn],cost[mm],cap[mm],uu[mm],vv[mm];
int n,m;
bool judge(int value)
{
prepare(n+2,0,n+1);
for(int i=1;i<=m;i++)
if(cost[i]<=value)
addedge(uu[i],vv[i],cap[i]);
addedge(src,1,sum);
for(int i=1;i<=n;i++) addedge(i,dest,need[i]);
if(sum==Dinic_flow()) return true;
return false;
}
int main()
{
// freopen("cin.txt","r",stdin);
while(~scanf("%d%d",&n,&m))
{
sum=0;
for(int i=1;i<=n;i++){
scanf("%d",&need[i]);
sum+=need[i];
}
int maxcost=0;
int mincost=10000001;
for(int i=1;i<=m;i++){
scanf("%d%d%d%d",&uu[i],&vv[i],&cost[i],&cap[i]);
if(cost[i]>maxcost) maxcost=cost[i];
if(cost[i]<mincost) mincost=cost[i];
}
int l=0,r=maxcost+1,mid,ans;
bool flag=0;
while(l<=r)
{
mid=(r+l)/2;
if(judge(mid)) {ans=mid;r=mid-1;flag=1;}
else l=mid+1;
}
if(!flag) puts("-1");
else printf("%d\n",ans);
}
return 0;
} 拖了两周的网络流总结篇终于写完了==
京公网安备 11010502036488号