BZOJ 1834 [ZJOI2010]network 网络扩容

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1834

题意：n 个点有向图，m 条边，每条边有一个边权和一个单位扩容费用。两个问题，问题 1 求出最大流，问题 2 求出将最大流增加 K 所需要的最小扩容费用...

当做模板题了，对于问题 1，直接求最大流即可。

问题 2 是需要考虑一下的，我们采用如下做法：方 (tou) 便 (tan) 起见，以 SS，TT 指代超级源汇点，S，T 指代源汇点

对于跑完问题 1 的残量网络，在 SS 和 S 间连一条容量为 K，费用为 0 的边，在原图的每条边间连一条容量为 inf，费用为扩容费用的边，然后跑最小费用流即可。

为什么这么做呢，很显然，因为我们加入了大量容量为 inf 的边，新图中唯一能制约流量的限制就是 SS 和 S 间的边，这样新图的最大流一定是 K，跑费用流一定能跑到它。那么流量合理了，费用呢？我们可以这样的去感性认识一下：跑完最大流后的残量网络中有些边已经跑满了，有些边还可以跑，跑满的边只能通过扩容来继续跑了，扩容是没有限制的所以流量设为 inf，当一条边可以不扩容的时候，由于旧边费用为 0，所以肯定会先跑满剩余的流量再去扩容，这样这么做的正确性就是比较显然的了。

下面给出代码 qwq

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#define N 1010
#define M 200010
#define inf 1000000000
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
struct zgz
{
	int next,to,val,cost;
}edge[M];
int cnt=2,head[M];
void add(int from,int to,int val,int cost)
{
    edge[cnt].cost=cost;
    edge[cnt].to=to;
    edge[cnt].val=val;
    edge[cnt].next=head[from];
    head[from]=cnt++;
}
void insert(int from,int to,int val,int cost)
{add(from,to,val,cost);add(to,from,0,-cost);}
int n,m,k,SS=0,TT,S,T,w[M],c[M],v[M],u[M],anscost;
int d[N],ans;
queue<int> q;
bool bfs()
{
	memset(d,0,sizeof(d));
	d[S]=1;
	q.push(S);
	while(!q.empty())
	{
		int tp=q.front();
		q.pop();
		for(int i=head[tp];i;i=edge[i].next)
		{
			int to=edge[i].to,val=edge[i].val;
			if(!d[to]&&val)
			{
				d[to]=d[tp]+1;
				q.push(to);
			}
		}
	}
	if(d[T])return 1;
	return 0;
}
int dfs(int x,int v)
{
	if(x==T||v==0)return v;
	int ret=0;
	for(int i=head[x];i;i=edge[i].next)
	{
		int to=edge[i].to,val=edge[i].val;
		if(d[to]==d[x]+1)
		{
			int f=dfs(to,min(v,val));
			edge[i].val-=f,edge[i^1].val+=f;
			v-=f;ret+=f;
			if(v==0)break;
		}
	}
	if(ret==0)d[x]=-1;
	return ret;
}
void dinic()
{
	while(bfs())ans+=dfs(S,inf);
	printf("%d ",ans);
}
int dis[N],vis[N],pre[N];
bool spfa()
{
	memset(dis,0x3f,sizeof(dis));
	memset(vis,0,sizeof(vis));
	memset(pre,-1,sizeof(pre));
	dis[SS]=0,vis[SS]=1;
	q.push(SS);
	while(!q.empty())
	{
		int tp=q.front();
		q.pop();
		vis[tp]=0;
		for(int i=head[tp];i;i=edge[i].next)
		{
			int to=edge[i].to,val=edge[i].val,cost=edge[i].cost;
			if(dis[to]>dis[tp]+cost&&val)
			{
				dis[to]=dis[tp]+cost;
				pre[to]=i;
				if(!vis[to])
				{
					vis[to]=1;
					q.push(to);
				}
			}
		}
	}
	return pre[TT]!=-1;
}
void MCMF()
{
	int mn=inf;
	for(int i=pre[TT];i!=-1;i=pre[edge[i^1].to])
	mn=min(mn,edge[i].val);
	for(int i=pre[TT];i!=-1;i=pre[edge[i^1].to])
	{
		edge[i].val-=mn,edge[i^1].val+=mn;
		anscost+=edge[i].cost*mn;
	}
}
int main()
{
	n=read(),m=read(),k=read();
	S=1,T=n;TT=T;
	for(int i=1;i<=m;i++)
	{
 		u[i]=read(),v[i]=read(),c[i]=read(),w[i]=read();
		insert(u[i],v[i],c[i],0);	
	}
	dinic();
	insert(SS,S,k,0);
	for(int i=1;i<=m;i++)
	insert(u[i],v[i],inf,w[i]);
	while(spfa())MCMF();
	printf("%d",anscost);
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

#include <iostream>

#include <cstdio>

#include <cstring>

#include <queue>

#include <algorithm>

#define N 1010

#define M 200010

#define inf 1000000000

using namespace std;

inline int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

struct zgz

{

int next,to,val,cost;

}edge[M];

int cnt=2,head[M];

void add(int from,int to,int val,int cost)

{

edge[cnt].cost=cost;

edge[cnt].to=to;

edge[cnt].val=val;

edge[cnt].next=head[from];

head[from]=cnt++;

}

void insert(int from,int to,int val,int cost)

{add(from,to,val,cost);add(to,from,0,-cost);}

int n,m,k,SS=0,TT,S,T,w[M],c[M],v[M],u[M],anscost;

int d[N],ans;

queue<int> q;

bool bfs()

{

memset(d,0,sizeof(d));

d[S]=1;

q.push(S);

while(!q.empty())

{

int tp=q.front();

q.pop();

for(int i=head[tp];i;i=edge[i].next)

{

int to=edge[i].to,val=edge[i].val;

if(!d[to]&&val)

{

d[to]=d[tp]+1;

q.push(to);

}

if(d[T])return 1;

return 0;

}

int dfs(int x,int v)

{

if(x==T||v==0)return v;

int ret=0;

for(int i=head[x];i;i=edge[i].next)

{

int to=edge[i].to,val=edge[i].val;

if(d[to]==d[x]+1)

{

int f=dfs(to,min(v,val));

edge[i].val-=f,edge[i^1].val+=f;

v-=f;ret+=f;

if(v==0)break;

}

if(ret==0)d[x]=-1;

return ret;

}

void dinic()

{

while(bfs())ans+=dfs(S,inf);

printf("%d ",ans);

}

int dis[N],vis[N],pre[N];

bool spfa()

{

memset(dis,0x3f,sizeof(dis));

memset(vis,0,sizeof(vis));

memset(pre,-1,sizeof(pre));

dis[SS]=0,vis[SS]=1;

q.push(SS);

while(!q.empty())

{

int tp=q.front();

q.pop();

vis[tp]=0;

for(int i=head[tp];i;i=edge[i].next)

{

int to=edge[i].to,val=edge[i].val,cost=edge[i].cost;

if(dis[to]>dis[tp]+cost&&val)

{

dis[to]=dis[tp]+cost;

pre[to]=i;

if(!vis[to])

{

vis[to]=1;

q.push(to);

}

return pre[TT]!=-1;

}

void MCMF()

{

int mn=inf;

for(int i=pre[TT];i!=-1;i=pre[edge[i^1].to])

mn=min(mn,edge[i].val);

for(int i=pre[TT];i!=-1;i=pre[edge[i^1].to])

{

edge[i].val-=mn,edge[i^1].val+=mn;

anscost+=edge[i].cost*mn;

}

int main()

{

n=read(),m=read(),k=read();

S=1,T=n;TT=T;

for(int i=1;i<=m;i++)

{

u[i]=read(),v[i]=read(),c[i]=read(),w[i]=read();

insert(u[i],v[i],c[i],0);

}

dinic();

insert(SS,S,k,0);

for(int i=1;i<=m;i++)

insert(u[i],v[i],inf,w[i]);

while(spfa())MCMF();

printf("%d",anscost);

}

zgz233

BZOJ 1834 [ZJOI2010]network 网络扩容

BZOJ 1927 [Sdoi2010] 星际竞速

BZOJ 1877 [SDOI2009] 晨跑

l1ll5

Comments | NOTHING

zgz233