BZOJ 1834 [ZJOI2010]network 网络扩容

网络流裸体 

第一问最大流跑一跑

第二问新建一个点连边到1 容量k费用0 再对所有的边复制一条边出来 容量为inf 费用为w

然后跑最小费用最大流

这题最大流用ek可过

#include <cstdio>
#include <algorithm>
#include <cstring>
#define clr(x) memset(x,0,sizeof(x))
using namespace std;
void read(int &x){
	char c;
	while((c=getchar())<'0' || c>'9');x=c-'0';
	while((c=getchar())>='0' && c<='9') x=x*10+c-'0';
}
const int N=100010,inf=308888888;
struct Ask{
	int u,v,c,w;
	void read2(){read(u),read(v);read(c);read(w);}
}ask[N];
int n,m,c[N],to[N],nxt[N],now[N],cap[N],tail=1,q[N],from[N],dis[N],inq[N],k,ans;
void add(int u,int v,int ci,int capi){
	to[++tail]=v;nxt[tail]=now[u];now[u]=tail;c[tail]=ci;cap[tail]=capi;
	to[++tail]=u;nxt[tail]=now[v];now[v]=tail;c[tail]=-ci;cap[tail]=0;
}
bool spfa(int s,int t){
	int l=0,r=0;
	clr(from);clr(inq);
	for(int i=1;i<=n+2;i++) dis[i]=inf;
	q[++r]=s;dis[s]=0;inq[s]=1;
	while(l<r){
		int u=q[(++l)%N];inq[u]=0;
		for(int i=now[u];i;i=nxt[i]) if(cap[i]>0 && dis[to[i]]>dis[u]+c[i]){
			int v=to[i];
			dis[v]=dis[u]+c[i];
			from[v]=i;
			if(!inq[v]) q[(++r)%N]=v;
		}
	}
	return dis[t]!=inf;
}
int augument(int s,int t,int type){
	int fl=inf,ret=0;
	for(int tmp=t;tmp!=s;){
		int e=from[tmp];
		fl=min(cap[e],fl);
		tmp=to[e^1];
	}
	for(int tmp=t;tmp!=s;){
		int e=from[tmp];
		cap[e]-=fl;cap[e^1]+=fl;
		ret+=fl*c[e];
		tmp=to[e^1];
	}
	return type?ret:fl;
}
int main(){
	//freopen("1834.in","r",stdin);freopen("1834.out","w",stdout);
	read(n);read(m);read(k);
	for(int i=1;i<=m;i++) {
		ask[i].read2();
		add(ask[i].u,ask[i].v,0,ask[i].c);
	}
	while(spfa(1,n)) ans+=augument(1,n,0);
	printf("%d ",ans);ans=0;
	for(int i=1;i<=m;i++) add(ask[i].u,ask[i].v,ask[i].w,inf);
	add(n+1,1,0,k);
	while(spfa(n+1,n)) 	ans+=augument(n+1,n,1);
	printf("%d",ans);
}

网络流 Comments(0) 2016年5月02日 14:41

BZOJ 1066: [SCOI2007]蜥蜴

这种限制节点经过次数的估计就是网络流了

新建源汇s t

把一个点拆成两个，中间连接一条容量为经过次数的边

对于每一个蜥蜴，从s向这个点的入点连边，容量为1，表示有一条蜥蜴。对于每一个点可达的点从出点连边，容量正无穷，能跳出的向t连边，容量正无穷。跑最大流即可

dinic的时候不要忘记重置cur数组，一直死循环…………

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
//点ij为2*(c*(i-1)+j)入和2*(c*(i-1)+j)+1出 s=r*c*2+2 t=r*c*2+3
const int N=200010,INF=209999999;
int to[N],from[N],fl[N],tail=1,pre[N],now[N],ans,d[N],vis[N],q[N*2],L,R,cur[N],r,c,di,tmp,g[50][50],xiyi;
inline int o(int i,int j){return 2*(c*(i-1)+j);}
void add(int u,int v,int f){
	to[++tail]=v;pre[tail]=now[u];now[u]=tail;fl[tail]=f;
	to[++tail]=u;pre[tail]=now[v];now[v]=tail;fl[tail]=0;
}
bool bfs(int s,int t){
	memset(vis,0,sizeof(vis));
	L=R=0;q[++R]=s;vis[s]=1;d[s]=0;
	for(int x=q[++L];L<=R;x=q[++L])
		for(int i=now[x];i;i=pre[i]) if(fl[i]>0 && !vis[to[i]]) d[to[i]]=d[x]+1,vis[to[i]]=1,q[++R]=to[i];
	return vis[t];
}
int dfs(int x,int t,int a){
	if(x==t || a==0) return a;
	int flow=0,f;
	for(int &i=cur[x];i;i=pre[i]) if(d[to[i]]==d[x]+1 && (f=dfs(to[i],t,min(a,fl[i])))>0){
		fl[i]-=f;fl[i^1]+=f;flow+=f;a-=f;
		if(a==0) break;
	}
	return flow;
}
int main(){
	//freopen("1066.in","r",stdin);freopen("1066.out","w",stdout);
	scanf("%d%d%d\n",&r,&c,&di);
	for(int i=1;i<=r;i++){
		for(int j=1;j<=c;j++) {
			g[i][j]=getchar()-'0';
			if(g[i][j]) add(o(i,j),o(i,j)^1,g[i][j]);
		}
		getchar();
	}
	for(int i=1;i<=r;i++)
		for(int j=1;j<=c;j++) if(g[i][j])
			for(int x=-di;x<=di;x++)
				for(int y=-di;y<=di;y++) if(abs(x)+abs(y)<=di && i+x>0 && i+x<=r && j+y>0 && j+y<=c && g[i+x][j+y] && ((i+x)!=i || (j+y)!=j)) add(o(i,j)^1,o(i+x,j+y),INF);
	for(int i=1;i<=r;i++){
		for(int j=1;j<=c;j++){
			tmp=getchar();
			if(tmp=='L') xiyi++,add(2*r*c+2,o(i,j),1);
		}
		getchar();
	}
	for(int i=1;i<=r;i++)
		for(int j=1;j<=c;j++) if(g[i][j] && min(min(r+1-i,i),min(c+1-j,j)) <= di) 	add(o(i,j)+1,2*r*c+3,INF);
	while(bfs(2*r*c+2,2*r*c+3)) {
		for(int i=1;i<=2*r*c+3;i++) cur[i]=now[i];
		ans+=dfs(2*r*c+2,2*r*c+3,INF);
	}
	ans=xiyi-ans;
	printf("%d",ans);
	return 0;
}

网络流 Comments(0) 2016年2月27日 17:42

BZOJ 1070 [SCOI2007]修车

今天看到这题，这TM不是上星期BC的最后一题吗！！！！！！！！于是整个人都不好了，为什么我没有早点开始做BZOJ！！

于是用上星期在题解里看到的方法A了这题

这道题的思路是拆点

由于每一个人的选择 只会对后边来修车的人有影响 我们只要考虑这个人是倒数第几个人来修车的就好了

新建s，t。

将每个店员拆成n个点，其中第t个点代表倒数第t个修。比如 我是第一个人 是倒数第二个人来修车的，那么我这个选择就会让我自己和我后面的人总共等2*T[i][j]的时间，所以只要连一条容量为1的边，费用为倒数第k个 k*T[i][j]就好了。剩下来就是 s连到每个人容量1费用0，店员连到t，容量1，费用0就好了

巧妙的构图 考试的时候根本没想到。

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N=100010,INF=1049999654;
LL n,m,to[N*4],from[N*4],pre[N*4],now[N*2],cost[N*4],flow[N*4],tail=1,prev[N],dis[N],ans,inq[N],l,r,q[N],tmp;
void add(int u,int v,int f,int co){
	to[++tail]=v;from[tail]=u;flow[tail]=f;pre[tail]=now[u];now[u]=tail;cost[tail]=co;
	to[++tail]=u;from[tail]=v;flow[tail]=0;pre[tail]=now[v];now[v]=tail;cost[tail]=-co;
}
bool spfa(int s,int t){
	for(int i=1;i<=n+m*n+2;i++) inq[i]=0,dis[i]=INF,prev[i]=0;
	l=r=0;dis[s]=0;q[++r]=s;inq[s]=1;
	while(l<r){
		int x=q[(++l)%N];inq[x]=0;
		for(int i=now[x];i;i=pre[i]) if(flow[i]>0 && dis[to[i]]>dis[x]+cost[i]){
			dis[to[i]]=dis[x]+cost[i];prev[to[i]]=i;
			if(!inq[to[i]]) q[(++r)%N]=to[i],inq[to[i]]=1;
		}
	}
	return dis[t]!=INF;
}
void zg(int s,int t){
	LL f=INF;
	for(int i=t;i!=s;i=from[prev[i]]) f=min(f,flow[prev[i]]);
	for(int i=t;i!=s;i=from[prev[i]]) {flow[prev[i]]-=f;flow[prev[i]^1]+=f;ans+=f*cost[prev[i]];}
}
int main(){
	scanf("%lld%lld",&m,&n);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++) {
			scanf("%lld",&tmp);
			for(int T=1;T<=n;T++) add(i,j*n+T,1,T*tmp);
		}
	}
	for(int i=n+1;i<=n+m*n;i++) add(i,n+m*n+2,1,0);
	for(int i=1;i<=n;i++) add(n+m*n+1,i,1,0);
	while(spfa(n+m*n+1,n+m*n+2)) zg(n+m*n+1,n+m*n+2);
	printf("%.2lf",(double)ans/n);
}

网络流 Comments(0) 2016年2月03日 19:24

BZOJ1061 [NOI2008]志愿者招募

听说这道题可以用线性规划的方法水过去，但是这是一道网络流题

以下引用自百度

设每个时间i都需要有至少Ai个志愿者，设每种志愿者i使用了xi个，那么我们对于每个时间点都可以列出一个不等式：x1+x2+x3+...+xn>=Ai（其中如果第i类志愿者不能在该区间工作则xi固定为0）。

最后要求最小化w1*x1+w2*x2+x3*x3+...+wn*xn（其中wi是第i种志愿者的单位价格）。

这正是一个线性规划的问题。

那么我们是否可以转化为网络流来求解呢？

当然是可以哒~

现在我们将每个点的Ai取反，变成-Ai，这样他就成了一个“坑”了（相对于y=0而言），我们从源点S给最左边的时间点引流，流的大小为U（U为大整数），然后每个时间点i向时间点i+1建边（i，i+1，U-Ai，0），最后设汇点为最右端的时间点。

现在，如果所有时间点的Ai都为0，那么显然，汇点的流量恰好等于U。

问题来了，现在我们有的Ai不等于0了，那么显然源点到汇点的流量被这些“坑”所截断了，怎么解决这一个问题？

假设志愿者工作的时间为【Li，Ri】，且该种志愿者单位花费为Ci，则我们建边（Li，Ri+1，INF，Ci），表示我们雇佣了一些志愿者“填坑”来了，如果雇佣了xi个志愿者，则说明将该区间内的所有“坑”的深度填掉了xi（当然可能有的坑在“填坑”行动后高于y=0，那也无所谓了嘛，多多益善~）。

那么现在是不是看起来思路有一点清晰了？

于是志愿者的作用就是一个人可以填一个区间的“坑”（好厉害！），然后需要每种志愿者选择一些使得花费最小的情况下填掉所有的“坑”，就是这样~

最后就是让费用流帮我们选择志愿者的时候了~

于是我们按照上面的方法跑完一遍最小费用最大流，如果流量等于U，则说明满流（志愿者们成功填掉了所有的坑，同志们辛苦了~），此时的记录的cost就是最小值（cost为算法记录的最小费用）。如果流量不等于U则无解。

这时我们又收获了一种费用流的模型：初始给一道大流，然后将有至少覆盖次数限制的点（边）的权值取反变成“坑”，最后区间覆盖就等于“填坑”，只要最后的流量等于大流的流量，就有解。

或者看这个题解 http://blog.csdn.net/fzhvampire/article/details/50889187

接下来是代码

#include <cstdio>
#include <algorithm>
using namespace std;
const int N=100010,INF=1000000000;
int to[N*2],from[N*2],pre[N*2],cost[N*2],flow[N],q[N],l,r,inq[N],dis[N],now[N],prev[N],tail=1,n,m,a,s,t,c,left=INF,ans;
void add(int u,int v,int cap,int co){to[++tail]=v;from[tail]=u;pre[tail]=now[u];now[u]=tail;cost[tail]=co;flow[tail]=cap;}
bool spfa(int s,int t){
	for(int i=1;i<=n+2;i++) dis[i]=INF;
	l=r=0;q[++r]=s;inq[s]=1;dis[s]=0;
	while(l<r){
		int x=q[(++l)%N];inq[x]=0;
		for(int i=now[x];i;i=pre[i]) if(flow[i]>0){
			if(dis[to[i]] > dis[x] + cost[i]) {
				dis[to[i]]=dis[x]+cost[i],prev[to[i]]=i;
				if(!inq[to[i]]) q[(++r)%N]=to[i],inq[to[i]]=1;
			}
		}
	}
	return dis[t]!=INF;
}
int zg(int s,int t){
	int f=INF,sum=0;
	for(int i=t;i!=s;i=from[prev[i]]) f=min(f,flow[prev[i]]);
	for(int i=t;i!=s;i=from[prev[i]]) flow[prev[i]]-=f,flow[prev[i]^1]+=f,sum+=cost[prev[i]]*f;
	return sum;
}
int main(){
	//freopen("1061.in","r",stdin);freopen("1061.out","w",stdout);
	scanf("%d%d",&n,&m);
	add(n+2,1,INF,0);add(1,n+2,0,0);
	for(int i=1;i<=n;i++) scanf("%d",&a),add(i,i+1,INF-a,0),add(i+1,i,0,0);
	for(int i=1;i<=m;i++) scanf("%d%d%d",&s,&t,&c),add(s,t+1,INF*2,c),add(t+1,s,0,-c);
	while(spfa(n+2,n+1)) 
	ans+=zg(n+2,n+1);
	printf("%d",ans);
	return 0;
}

网络流 Comments(0) 2016年1月24日 11:31

bzoj 1497 【NOI2006】最大获利 题解

 
原来不会做 看了论文才会写的 是2007年胡伯涛的集训队论文 国家集训队2007论文集7.胡伯涛《最小割模型》.pdf
显然 我们发现这是一个图论模型 考虑网络流
要最大化的是 取的用户值-建的中转站的值
变形一下 所有用户值-不取的用户-建的中转站的值
要最小化的就是 不取的用户+建的中转站的值
构图 新建源汇s,t 将s连向所有的用户 容量为获利 所有的中转站连向t 容量为费用 用户指向两个需求 容量为﹢∞
我们只要求一个最小割，再用所有的用户值减去这个割的大小即可
去掉的边中 s与用户相连的边 表示这个用户不选
           t与中转站相连的边 表示这个中转站要建
下证明 最小割对应一个取的方案 可以使所有用户都满足
假设存在一条通路 设这条通路 上用户为a 中转站为b 那么 由上述定义 我们要选择 a用户 又不建这个中转站 显然这是不正确的 又这个割是最小的 那么一定符合题目要求 <-这句话就是瞎扯淡的
我证明的有问题 详情还是要看一下论文的
 
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=200000;
int e[N*2],pre[N*2],c[N*2],flow[N*2],now[N],d[N],vis[N],tail=1,cur[N],n,m,q[N],v,ans,a,b;
void add(int u,int v,int cap){e[++tail]=v;c[tail]=cap;pre[tail]=now[u];now[u]=cur[u]=tail;}
bool bfs(int s,int t){
	int l=0,r=0;
	memset(vis,0,sizeof(vis));
	q[++r]=s;d[s]=0;vis[s]=1;
	while(l<r){
		int x=q[++l];
		for(int i=now[x];i;i=pre[i]) if(!vis[e[i]] && c[i]>0) {
			q[++r]=e[i];vis[e[i]]=1;d[e[i]]=d[x]+1;
		}
	}
	return vis[t];
}
int dfs(int x,int a){
	if(x==n+m+2 || a==0) return a;
	int flow=0,f;
	for(int &i=cur[x];i;i=pre[i]) 
		if(d[x]+1==d[e[i]] && (f=dfs(e[i],min(a,c[i])))>0){
			c[i]-=f;c[i^1]+=f;flow+=f;a-=f;
			if(a==0) break;
		}
	return flow;
}
void print(int a){
	printf("Edges of %d :",a);
	for(int i=now[a];i;i=pre[i]) if(c[i]) printf("%d(%d) ",e[i],c[i]);printf("\n");
}
int main(){
	freopen("1497.in","r",stdin);freopen("1497.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&v),add(i,n+m+2,v),add(n+m+2,i,0);
	for(int i=1;i<=m;i++) {
		scanf("%d%d%d",&a,&b,&v);
		add(n+m+1,i+n,v);
		add(i+n,n+m+1,0);
		add(i+n,a,2099999999+1);add(a,i+n,0);
		add(i+n,b,2099999999+1);add(b,i+n,0);
		ans+=v;
	}
	//print(11);for(int i=6;i<=10;i++) print(i);for(int i=1;i<=5;i++) print(i);print(12);
	while(bfs(n+m+1,n+m+2)) {
		for(int i=1;i<=n+m+2;i++) cur[i]=now[i];
		ans-=dfs(n+m+1,2099999999);
	}
	printf("%d",ans);
	return 0;
}

 

网络流 Comments(0) 2016年1月23日 14:31